[JS] 재귀 함수

재귀 함수

자기 자신을 호출하는 함수를 말한다. 재귀 함수는 반복되는 처리를 위해 사용된다.

function countdown1(n) {
  for (var i = n; i >= 0; i--) console.log(i);
}

countdown1(10);

function countdown2(n) {
  if (n < 0) return;
  console.log(n);
  countdown2(n - 1); // 재귀 호출
}

countdown2(10);

반복문으로 구현한 함수 countdown1을 재귀 함수를 사용하면 countdown2처럼 작성할 수 있다. 대표적인 재귀 함수 유형인 팩토리얼을 구현해보자.

// 팩토리얼(계승)은 1부터 자신까지의 모든 양의 정수의 곱이다.
// n! = 1 * 2 * ... * (n-1) * n
function factorial(n) {
  // 탈출 조건: n이 1 이하일 때 재귀 호출을 멈춘다.
  if (n <= 1) return 1;
  // 재귀 호출
  return n * factorial(n - 1);
}

console.log(factorial(0)); // 0! = 1
console.log(factorial(1)); // 1! = 1
console.log(factorial(2)); // 2! = 2 * 1 = 2
console.log(factorial(3)); // 3! = 3 * 2 * 1 = 6
console.log(factorial(4)); // 4! = 4 * 3 * 1 * 1 = 24
console.log(factorial(5)); // 5! = 5 * 4 * 3 * 2 * 1 = 120

함수 표현식으로도 가능하다

var factorial = function foo(n) {
  // 탈출 조건: n이 1 이하일 때 재귀 호출을 멈춘다.
  if (n <= 1) return 1;
  // 함수를 가리키는 식별자로 자기 자신을 재귀 호출
  return n * factorial(n - 1);

  // 함수 이름으로 자기 자신을 재귀 호출할 수도 있다.
  // console.log(factorial === foo); // true
  // return n * foo(n - 1);
};

console.log(factorial(5)); // 5! = 5 * 4 * 3 * 2 * 1 = 120

당연히 for문이나 while문으로도 가능하다

function factorial(n) {
  if (n <= 1) return 1;

  var res = n;
  while (--n) res *= n;
  return res;
}

console.log(factorial(0)); // 0! = 1
console.log(factorial(1)); // 1! = 1
console.log(factorial(2)); // 2! = 2 * 1 = 2
console.log(factorial(3)); // 3! = 3 * 2 * 1 = 6
console.log(factorial(4)); // 4! = 4 * 3 * 1 * 1 = 24
console.log(factorial(5)); // 5! = 5 * 4 * 3 * 2 * 1 = 120

중요한 것은 반드시 탈출 조건을 만들어야 한다는 점이다. 탈출 조건이 없으면 함수가 무한 호출되어 스택오버플로 에러가 발생한다.

재귀 함수는 반복되는 처리를 반복문 없이 구현할 수 있따는 장점이 있지만, 무한 반복에 빠질 위험이 있고, 이로인해 스택오버플로 에러를 발생시킬 수 있으므로 주의해서 사용해야 한다. 따라서 재귀함수는 반복문을 사용하는 것보다 재귀 함수를 사용하는 편이 더 직관적으로 이해하기 쉬울때만 한정적으로 사용하는 것이 바람직하다.

더 공부할 주제들

• 재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)
• 꼬리 재귀 (tail recursion in js)
• 하노이의 탑 재귀 (js tower of hanoi in recursion)
• 조합 재귀 함수 (js combination in recursion)

참고 문서

모던 자바스크립트 Deep Dive