재귀

함수가 자기 자신을 호출하는 것

재귀를 이용하면 복잡한 문제를 간단하게 해결할 수 있다.

재귀 함수를 작성할 때는 먼저 종료 조건(Base Case)을 작성해야한다. 종료 조건은 함수가 호출되지 않고 바로 결과값을 반환해야 하는 경우를 뜻한다.
이후에는 재귀 호출을 이용하여 문제를 작은 단위로 분할하고, 이를 해결하는 과정을 반복한다.

팩토리얼, 피보나치 등의 문제가 있다.

예제

팩토리얼

function factorial(n) {
  if (n === 1) { // 기저 조건
    return 1;
  }
  return n * factorial(n - 1); // 재귀 호출
}

console.log(factorial(5)); // 5! = 120 출력

factorial 함수는 n의 팩토리얼을 구하는 함수입니다. 함수 내부에서는 n이 1일 경우에는 기저 조건으로 처리하여 1을 반환하고, 그 외의 경우에는 n과 factorial(n - 1)의 곱을 반환하는 재귀 호출을 수행합니다. 이렇게 재귀 호출을 반복하면서 n이 1이 될 때까지 작은 단위로 문제를 분할하여 해결하게 됩니다.

피보나치

피보나치 수열은 이전 두 항을 더하여 현재의 항을 만들어 나가는 수열입니다. 예를 들어, 0, 1, 1, 2, 3, 5, 8, 13, 21, ... 과 같은 수열입니다. n번째 피보나치 수를 반환하는 함수 fibonacci(n)을 작성하세요. 함수의 인자 n은 0 이상 30 이하의 정수입니다.

function fibonacci(n) {
  if (n === 0 || n === 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}
// 아예 줄인 것
function fibonacci(n) {
  n === 0 || n === 1 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

이 함수는 n번째 피보나치 수를 반환합니다. 이 함수는 재귀(Recursion)를 사용하여 문제를 해결합니다. 함수의 인자 n이 0이면, 0을 반환합니다. n이 1이면, 1을 반환합니다. 그 외의 경우, fibonacci(n - 1)과 fibonacci(n - 2)의 합을 반환합니다. 이렇게 함수를 재귀적으로 호출하여 피보나치 수열을 생성합니다.

이 알고리즘은 입력 크기가 커질수록 계산 시간이 지수적으로 증가하므로, 입력 크기가 커질 경우, 동적 계획법(Dynamic Programming) 등 다른 알고리즘을 사용하는 것이 더 효율적입니다.

// 동적 계획법: 메모이제이션
function fibonacci(n) {
  const memo = [0, 1];

  for (let i = 2; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2];
  }

  return memo[n];
}