[JavaScript] Recursion

재귀의 의미

어떠한 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀(recursion) 라고 한다.

재귀 호출

함수 실행 중 자기 자신을 호출하는 것을 재귀 호출 (recursive call) 이라고 한다.

재귀를 언제 사용해야 하는가

1. 주어진 문제를 구조가 비슷한 더 작은 문제로 나눌 수 있을 때
2. 중첩된 루프가 많거나 중첩의 정도 (number of loops) 를 미리 알 수 없는 경우
3. 알고리즘 테스트를 준비하기 위해 (재귀와 자료구조는 알고리즘 문제의 많은 부분을 차지한다.)

재귀적 사고 연습

1. 재귀 함수의 입력값과 출력값 정의
   예) factorial: number -> number

2. 문제를 쪼개고 경우의 수를 나눔

• factorial은 factorial(5) 와 factorial(4) 를 구하는 방법이 동일하다.
  문제의 입력값에 따라 경우의 수를 나눈다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈다.
• factorial은 입력값이 0 혹은 1인 경우와 그렇지 않은 경우로 나눌 수 있다.

3. 단순한 문제 해결하기
   문제를 여러 경우로 구분했다면 쉬운 문제부터 해결한다. 이를 재귀의 기초 (base case)라고 부른다. base case 는 재귀의 탈줄 조건을 구성하게 된다.

• factorial를 더 이상 쪼갤 수 없는 경우는 입력값이 0 혹은 1 이고, 이때 출력값은 1이다.

4. 복잡한 문제 해결하기
   2 이상의 수를 입력받은 경우 input x factorial(input - 1) 과 같다.

5. 코드 구현하기.

• 일반적인 재귀 함수의 템플릿 :

function resursive(...) {
// base case
  if (문제를 더 쪼갤 수 없을 경우)
    return 단순한 문제의 해답

// recursive case
  return 더 작은 문제로 새롭게 정의된 문제
}

Tree 구조에 재귀 함수 사용하기

기타

• 옛날에는 재귀함수의 스택이 많이 쌓일 경우 메모리에 부담이 갔지만 현대의 컴퓨터에서는 큰 부담이 없다. 같은 맥락에서 코드를 굳이 줄이려고 노력할 필요가 없다. 최대한 명시적이고 가독성 좋게 짜자.
• Short Circuit Evaluation (단축 평가 논리 계산) : 어떤 표현식의 값이 결정되었을 때 그 식의 평가를 중단하는 것을 말한다. 예를 들어 return a && b; 라고 쓸 경우 a 가 true 면 b 의 값을 확인하지 않고 바로 true를 반환한다.
• Tail Recursion Optimization (꼬리재귀 최적화) : 함수의 마지막 줄에 재귀 호출이 있는 경우를 tail recursion 이라고 한다. 이 경우 JS는 호출 스택을 추가하지 않고 처리한다. (만약 꼬리재귀가 아니고 재귀호출 후 더 코드가 있으면 비효율적일 수 있다)
• 재귀함수에서 중간에 return false 를 하여 함수가 끝나버리는 실수를 자주 한다. 함수의 맨 끝에 return false 를 하자. 혹은 if (재귀함수 = true) return true;
• memoization 기법 (이미 실행한 case 의 결과를 저장하는 기법) 으로 재귀함수의 시간복잡도를 줄일 수 있다.
• 무언가를 공부할 때 지금 필요한 것만 공부하면 된다. (문서의 링크를 일일이 누를 필요 없음)

Advanced

• 하노이의 탑 재귀 (js tower of hanoi in recursion)
• 조합 재귀함수 (js combination in recursion)