[JavaScript] 재귀

알고리즘 문제에 자주 등장하는 재귀에 대해 알아보자.

재귀(Recursion)

어떠한 것을 정의할 때 자기 자신을 참조하는 것 (출처: 위키백과)

재귀 함수(Recursive Function)

함수를 정의할 때 자기 자신을 호출하는 함수

재귀 함수는 언제 사용할까?

• 주어진 문제를 비슷한 구조의 작은 문제로 나눌 수 있을 때
• 반복문이 여러 번 중첩되며 그 횟수를 예측하기 어려울 때
• 반복문으로 작성한 코드를 간결하고 이해하기 쉽게 작성하고 싶을 때

재귀 함수의 형식

재귀 함수는 일반적으로 탈출 조건(base case)과 재귀 조건(recursive case)을 나누어 작성한다.
탈출 조건에서는 주어진 문제를 가장 작은 문제로 나누었을 때의 결과를 반환하고, 재귀 조건에서는 주어진 문제를 한 단계 작은 문제로 나누어 표현한 표현식을 반환한다.

그 형식을 일반화하면 다음과 같다.

const recursive = function(param1, param2, ...) {
  // 탈출 조건(base case)
  if (가장 작은 문제로 나누었을 때) {
    return 가장 작은 문제의 결괏값
  }
  
  // 재귀 조건(recursive case)
  return 주어진 문제를 작은 문제로 나누어 표현한 것
};

이 형식은 모든 재귀 문제에 적용되지는 않으므로 상황에 따라 적절히 변형해야 한다.

재귀 함수 사용 예제

팩토리얼

팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱이다. (출처: 위키백과)
예를 들어, 5! = 5 ✕ 4 ✕ 3 ✕ 2 ✕ 1을 의미한다.

팩토리얼을 JavaScript로 구현하면 다음과 같다.

const factorial = function(num) {
  if (num === 1) return 1;
  
  return num * factorial(num - 1);
};

// factorial(5)
// = 5 ✕ factorial(4)
// = 5 ✕ 4 ✕ factorial(3)
// = 5 ✕ 4 ✕ 3 ✕ factorial(2)
// = 5 ✕ 4 ✕ 3 ✕ 2 ✕ factorial(1)
// = 5 ✕ 4 ✕ 3 ✕ 2 ✕ 1
// = 120

피보나치 수열

피보나치 수열은 첫째 항과 둘째 항의 값은 1이고, 그 다음 항부터의 값은 이전 두 항의 합이 된다.
1, 1, 2, 3, 5, 8, 13, 21 ...

피보나치 수열의 num번째 항을 구하는 함수는 다음과 같다.

const fibonacci = function(num) {
  if (num === 1 || num === 2) return 1;
  
  return fibonacci(num - 1) + fibonacci(num - 2);
};

// fibonacci(5)
// = fibonacci(4) + fibonacci(3)
// = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
// = (fibonacci(2) + fibonacci(1) + 1) + (1 + 1)
// = (1 + 1 + 1) + (2)
// = 5

참고문헌

• 위키백과 - 재귀
• 위키백과 - 계승