재귀함수란 무엇인가

자기 자신을 호출하는 행위.. 재귀호출을 수행하는 함수를 뜻한다. 여기서 재귀호출은 함수가 자기 자신을 호출하는 것을 말한다. 재귀 함수는 반복되는 처리를 위해서 사용된다.

재귀란 무엇인가

어떤 문제가 있다고 가정하면 이 문제를 더 작은 문제로 나눌 수도 있고, 이 작은 문제를 해결함으로써 전체 문제를 해결하는 방법을 재귀라고 한다. 재귀를 사용한 코드는 대부분의 경우 더욱 간결하고 이해하기 쉽다는 장점이 있다.
그리고 알고리즘의 문제의 많은 부분을 차지한다.

재귀

• 재귀적으로 사고하는 법
  • 잘게 쪼개서 사고하는 법
  • 재귀적 사고 => 재귀적 사고 연습을 통해 재귀 함수를 base,recursive case 로 나눠서 작성할 수 있다.
  • 함수 자신의 재귀적 호출
  • 탈출 조건

• 재귀 함수의 활용
  • 트리 구조에 재귀 함수를 활용
  • JSON , DOM 구조에 재귀 함수를 활용

재귀를 사용하기 적합한 상황

1. 주어진 문제를 비숫한 구조로 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나, 반복문의 중첩 횟수를 예측하기 어려운 경우

재귀적으로 사고하기

재귀 함수의 입력값과 출력값 정의하기

재귀함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는데 도움을 준다. 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는 , 가장 단순하게 정의하는 것이다. 예를 들어 함수 arrSum의 경우 number type을 요소로 갖는 배열을 입력받고, number type을 리턴한다. 이를 단순하게 표현하면

• arrSum: [number] => number

문제를 쪼개고 경우의 수를 나누기

주어진 문제를 어떻게 쪼갤 것인지 고민해야한다. 문제를 쪼갤 기준을 정하고, 정한 기준에 따라서 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인해야한다. 일반적인 경우, 입력값으로 이 기준을 정한다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기이다. 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 된다. 그리고 구분된 문제를 푸는 방식이 순서나 크기에 상관없이 모두 같다면, 문제를 제대로 구분 한 것이다.

단순한 문제 해결하기

문제를 여러 경우로 구분한 다음, 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초 (base case) 라고 한다. 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건 (재귀 호출이 멈추는 조건)을 구성한다.

복잡한 문제 해결하기

남이있는 복잡한 경우를 해결한다.

코드 구현하기

function recursive(input1, input2, ...) {
	// Base Case: 문제를 더 이상 쪼갤 수 없는 경우
  if(문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
}
   // recursive Case
   // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제;
  // ex. someValue + recursive(inputChanged, inputChanged2)

기타

모든 재귀함수는 반복문 (while or for문)으로 표현할 수 있다.
slice = immutable? + spread operator = immutable

let [head, ...tails] = arr; 
let head = arr[0];
let tail = arr.slice(1);

코플릿 메모

function arrLength(arr) {
  if(arr.isEmpty() === true){
    return 0;
  }
  let head = 1;
  let tail = arr.slice(1);

  return head + arrLength(tail);
}

function arrLength(arr) {
  if(arr.isEmpty() === true){
    return 0;
  }
 
  let [head, ...tail] = arr;

  return 1 + arrLength(tail);
}

이 두가지 코드가 왜 같은지 좀 의문이다.