재귀함수

재귀함수에 대해 알아보겠습니다.

재귀함수는 자기 자신을 호출하는 함수입니다.
함수 자신 안에서 자기 자신을 호출하고 그 안에서 다시 자기 자신을 호출하고.. 반복 또 반복..

재귀함수는 재귀를 멈추는 base case와 다시 자기 자신을 호출하는 recursive case로 나뉩니다.

아래의 코드는 재귀함수의 기본적인 템플릿(template)입니다.

재귀함수 템플릿

아래의 코드는 재귀함수의 기본 템플릿이라고 할 수 있습니다.

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

base case에서는 문제가 더 이상 쪼개지지 않을 경우 단순한 값이 리턴됩니다.
그렇지 않은 경우, 즉 전과 같은 연산이 이루어져야 하는 경우에는 다시 함수 자기 자신을 호출합니다. 그것이 바로 recursive case에서 일어납니다.

피보나치 수열

0번째 항은 0로, 1번째 항은 1로 두고, 2번째 항부터는 앞의 두 수를 더한 수로 놓는 수열.

재귀함수의 대표적인 예제 피보나치 수열을 살펴보겠습니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

아래의 코드는 피보나치 수열에서 num번째의 수를 찾는 코드입니다.

function fibonacci(num) {
  // 0번째와 1번째는 0, 1로 고정되어 있으므로, 숫자 자신을 리턴해줍니다.
  if (num <= 1) {
    return num;
  }
  
  // 2번째 부터는 본인 자신을 호출합니다.
  return fibonacci(num-2) + fibonacci(num-1);
}

하노이의 탑 재귀함수

재귀함수의 또 다른 예제 하노이의 탑 알고리즘입니다.
하노이의 탑 알고리즘은 [알고리즘] 탭에 다시 업로드하도록 하고,
아래에는 코드만 남겨놓도록 하겠습니다.

function hanoi(num, from, to, other) {
  if (num === 0) return;
  hanoi(num-1, from, other, to);
  console.log(`${from}번에서 ${to}로 옮긴다.`);
  hanoi(num-1, other, to, from);
}

hanoi(4, 0, 1, 2);