[JavaScript] 3. 재귀 알고리즘

1. 팩토리얼 (Factorial)

팩토리얼은 자연수 n에 대해 n! = n x (n-1) x (n-2) X ... X 1로 정의됩니다. 예를 들어, 5! = 5 X 4 X 3 X 2 X 1 = 120입니다.

function factorial(n) {
  // 기본 사례: 0! = 1, 1! = 1
  if (n === 0 || n === 1) {
    return 1;
  }
  // 재귀 호출
  return n * factorial(n - 1);
}

// 예제 사용
console.log(factorial(5)); // 출력: 120

 

재귀 호출이 깊어지면 스택 오버플로우가 발생할 수 있고, 큰 숫자의 팩토리얼을 계산할 때는 반복문을 사용하는 것이 더 안전할 수 있습니다.

---

2. 피보나치 수열 (Finbonacci Sequence)

피보나치 수열은 첫 두 수가 0과 1로 시작하고, 이후의 수는 이전 두 수의 합으로 정의됩니다. 즉, F(n) = F(n-1) + F(n-2)입니다, 예를 들어 수열은 다음과 같습니다.

• 0, 1, 1, 2, 3, 5, 8, 13, ...

재귀적 구현하기

function fibonacci(n) {
  // 기본 사례: F(0) = 0, F(1) = 1
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  }
  // 재귀 호출
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// 예제 사용
console.log(fibonacci(6)); // 출력: 8(0, 1, 1, 2, 3, 5 , 8)

 

위의 재귀적 구현은 중복 계산이 많아 성능이 좋지 않습니다 큰 n에 대해 매우 늘릴 수 있고, 이를 개선하기 위해 메모이제이션(memoization) 또는 반복적 방법을 사용할 수 있습니다.

const fibonacciWithMemo = (function () {
  const memo = {};

  function fib(n) {
    if (n in memo) {
      return memo[n];
    }
    if (n == 0) return 0;
    if (n == 1) return 1;

    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
  }
  return fib;
})();

console.log(fibonacciWithMemo(6)); // result: 8

---

 

GitHub - Koras02/javascript-algorithm