Recursive Functions

재귀함수(Recursive Functions)

재귀 함수는 실행하는 함수가 함수 내부에서 자신을 다시 호출하는 구조로 만들어진 함수를 의미한다.
재귀 함수는 반복문을 대신하여 사용할 수 있는데, while문과 같이 조건식(탈출조건)을 주지 않을 경우에 무한루프에 빠질 가능성이 있다.

사용방법

예시로 10부터 0까지 출력하는 함수를 구현해보면,

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

countdown(10)

위 처럼 반복문을 사용하여 구현할 수 있다.
하지만 반복문을 사용하지 않더라도 재귀 함수를 사용하여 위와 똑같은 결과를 가지고 올 수 있다.

function countdown(n) {
  if(n < 10) 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 = 2
console.log(factorial(3)) // 3! = 3 * 2 * 1 = 6
console.log(factorial(4)) // 4! = 4 * 3 * 2 * 1 = 24
console.log(factorial(5)) // 5! = 5 * 4 * 3 * 2 * 1 = 120

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

const factorial = function foo(n) {
  // 탈출 조건 : n이 1 이하일 때 재귀 호출을 멈춘다.
  if(n <= 1) return 1
  // 재귀 호출 
  return n * factorial(n - 1)
}

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

재귀 함수는 자신을 무한 재귀 호출한다.
따라서 반드시 탈출 조건을 만들어야 한다.
만약 탈출 조건이 없으면 함수가 무한 호출되어 스택 오버플로 에러가 발생한다.
대부분의 재귀 함수는 반복문으로 구현 가능하다.
위 팩토리얼 함수를 반복문으로 하면 아래와 같다.

function factorial(n) {
  if(n <= 1) return 1
  
  let 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 * 2 * 1 = 24
console.log(factorial(5)) // 5! = 5 * 4 * 3 * 2 * 1 = 120

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

출처 : 모던 자바스크립트 Deep Dive