Recursive Functions

함수가 자기 자신을 호출하는 것을 재귀 호출(recursive call)이라 한다.
재귀 함수(recursive function)는 재귀 호출을 수행하는 함수를 말한다.

재귀 함수는 반복되는 처리를 위해 사용한다.
예를 들어 10부터 0까지 출력하는 함수를 구현해보자.

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

countdown(10)

위 countdown 함수는 문제없이 잘 동작한다.
하지만 다음 코드와 같이
재귀함수를 사용하면 반복문 없이도 구현할 수 있다.

function countdown(n) {
	if ( n < 0 ) return;
  console.log(n)
  countdown( n - 1 );
}

countdown(10)

다음은 재귀함수로 팩토리얼 구현한 코드이다.

// 팩토리얼은 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
console.log(factorial(3)) // 3! = 3 * 2 * 1
console.log(factorial(4)) // 4! = 4 * 3 * 2 * 1
console.log(factorial(5)) // 5! = 5 * 4 * 3 * 2 * 1

factorial 함수 내부에서 자기 자신을 호출할 때 사용한 식별자 factorial은 함수이름이다.
함수 이름은 함수 몸체 내부에서만 유효하다.
따라서 함수 내부에서는 함수 이름을 사용해 자기 자신을 호출할 수 있다.
함수 표현식으로 정의한 함수 내부에서는 함수 이름은 물론 함수를 가리키는 식별자로도 자기 자신을 재귀호출할 수 있다.
단, 함수 외부에서 함수를 호출할 때는 반드시 함수를 가리키는 식별자로 해야 한다.

// 함수 표현식
let 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

재귀 함수는 자신을 무한 재귀 호출한다.
따라서 재귀 함수 내에는 재귀 호출을 멈출 수 있는 탈출 조건을 반드시 만들어야 한다.
위 예제의 경우 인수가 1 이하일 때 재귀 호출을 멈춘다.
탈출 조건이 없으면 함수가 무한 호출되어 스택 오버플로(stack overflow)에러가 발생한다.

대부분의 재귀 함수는 for 문이나 while 문으로 구현 가능하다.
위 팩토리얼 예제를 반복문으로 구현하면 다음과 같다.

function factorial(n) {
  if ( n <= 1 ) return 1;
  let res = n;
  while (--n) res *= n;
  return res
}
console.log(factorial(0)) // 0!
console.log(factorial(1)) // 1!
console.log(factorial(2)) // 2!
console.log(factorial(3)) // 3!
console.log(factorial(4)) // 4!
console.log(factorial(5)) // 5!

재귀 함수는 반복되는 처리를 반복문 없이 구현할 수 있다는 장점이 있지만
무한 반복에 빠질 위험이 있고, 이로 인해 스택 오버플로 에러를 발생시킬 수 있어
주의해서 사용해야 한다.

따라서 재귀 함수는 반복문을 사용하는 것보다 재귀 함수를 사용하는 편이
직관적으로 이해하기 쉬울 때만 한정적으로 사용하는 것이 바람직하다.

반복문으로 구현하면 가독성이 떨어져 유지보수가 힘들 것 같을 때 재귀함수를 사용하자!

참조 - 이웅모, 『모던 자바스크립트 Deep Dive 』, 위키북스(2020), p.179 ~ p.182.