재귀함수(Recursion)

오늘은 자바스크립트에서 재귀 함수에 대해 알아보는 시간을 갖도록 하겠습니다. 재귀 함수란, 함수가 자기 자신을 호출하는 것을 말해요. 먼저 재귀 함수의 개념을 이해하고, 그 다음엔 간단한 예제를 통해 실제로 어떻게 사용되는지 알아볼게요.

재귀 함수의 개념 이해

일반적으로 함수는 특정 작업을 수행한 후 종료되지만, 재귀 함수는 다른 함수를 호출하는 대신 자기 자신을 호출하게 됩니다. 이렇게 되면 함수가 계속 호출되면서 일종의 루프를 형성하는데, 이를 재귀적 호출이라고 하죠. 재귀 함수는 알고리즘을 간결하게 표현할 수 있어서 유용한 경우가 많습니다만, 너무 많은 재귀 호출이 발생하면 스택 오버플로우로 인한 프로그램 종료가 발생할 수 있으니 주의해야 해요.

재귀 함수를 활용한 팩토리얼 예제

자, 그럼 간단한 팩토리얼 예제를 통해 재귀 함수를 어떻게 사용하는지 살펴볼까요? 팩토리얼은 1부터 어떤 자연수 n까지의 곱셈을 나타내는 수학적 개념입니다. 예를 들어, 5! = 5 x 4 x 3 x 2 x 1 입니다. 이러한 팩토리얼 계산을 자바스크립트의 재귀 함수를 사용해 구현해 보겠습니다.

function factorial(n) {
  if (n === 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(5)); // 결과: 120

위의 예제에서 factorial 함수는 인자 n이 1일 때, 1을 반환하고 그렇지 않을 경우 n과 factorial(n-1)을 곱한 값을 반환합니다. 이렇게 자기 자신을 호출하면서 n이 1이 될 때까지 반복되게 되죠. 결국 5! = 5 x 4 x 3 x 2 x 1 = 120 이라는 결과를 얻게 됩니다.

피보나치 수열 예제

다음으로는 피보나치 수열을 구하는 재귀 함수를 살펴보겠습니다. 피보나치 수열은 첫 번째 항과 두 번째 항이 각각 1이고, 이후의 항은 바로 앞의 두 항의 합으로 이루어진 수열입니다. 즉, 수열은 1, 1, 2, 3, 5, 8, 13, ... 과 같이 진행됩니다. 이 피보나치 수열을 구하는 재귀 함수를 자바스크립트로 구현해 보겠습니다.

function fibonacci(n) {
  if (n === 1 || n === 2) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

console.log(fibonacci(7)); // 결과: 13

위의 예제에서 fibonacci 함수는 인자 n이 1이나 2일 때, 1을 반환하고 그렇지 않을 경우 fibonacci(n-1)과 fibonacci(n-2)의 합을 반환합니다. 이렇게 자기 자신을 호출하면서 n이 1이나 2가 될 때까지 반복되게 되죠. 결국 피보나치 수열의 7번째 항은 13이라는 결과를 얻게 됩니다.

재귀 함수의 단점 및 해결 방법

앞서 언급했듯이, 재귀 함수는 알고리즘을 간결하게 표현할 수 있다는 장점이 있지만, 스택 오버플로우로 인한 프로그램 종료가 발생할 수 있다는 단점도 존재합니다. 이러한 단점을 해결하기 위한 방법 중 하나는 '메모이제이션(Memoization)'이라는 기법입니다.

메모이제이션은 이미 계산된 결과를 저장해 두고, 나중에 같은 계산이 필요할 때 저장된 값을 사용하는 방식입니다. 이를 통해 중복되는 계산을 줄이고, 프로그램의 성능을 개선할 수 있습니다. 아래는 피보나치 수열 예제에 메모이제이션을 적용한 예시입니다.

function memoize(fn) {
  const cache = {};
  return function (n) {
    if (n in cache) {
      return cache[n];
    } else {
      const result = fn(n);
      cache[n] = result;
      return result;
    }
  };
}

function fibonacci(n) {
  if (n === 1 || n === 2) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

const memoizedFibonacci = memoize(fibonacci);

console.log(memoizedFibonacci(7)); // 결과: 13

memoize 함수는 인자로 주어진 함수 fn의 결과를 캐시에 저장하고, 캐시에 값이 존재할 경우 캐시 값을 반환하는 함수를 반환합니다.
이렇게 메모이제이션 기법을 사용하면, 이미 계산된 결과를 재활용할 수 있어서 중복되는 계산을 피하고 성능 개선을 이룰 수 있습니다. 위 예제에서는 memoize 함수를 통해 fibonacci 함수의 결과를 캐시에 저장하고, 필요한 경우 저장된 값을 사용하여 피보나치 수열을 더 효율적으로 계산할 수 있게 되었습니다.

재귀 함수와 반복문의 비교

마지막으로 재귀 함수와 반복문을 비교해 보겠습니다. 재귀 함수는 알고리즘을 간결하게 표현할 수 있다는 장점이 있지만, 스택 오버플로우 위험이 있어 성능에 영향을 줄 수 있습니다. 반면, 반복문은 재귀 함수보다 코드가 길어질 수 있지만, 스택 오버플로우 위험이 없고 일반적으로 성능이 더 좋습니다.

어떤 경우에 재귀 함수를 사용할지, 반복문을 사용할지는 문제의 복잡성, 성능 요구 사항, 가독성 등 여러 요인을 고려해 결정해야 합니다. 가급적이면 성능에 크리티컬한 영향을 주지 않는 상황에서, 코드의 가독성을 높이는 데 재귀 함수를 활용하는 것이 좋습니다.