알고리즘, 문제해결패턴, Recursion

재귀(Recursion)는 함수가 자기 자신을 호출하여 문제를 해결하는 기법입니다. 재귀는 문제를 작은 부분 문제로 나누어 해결할 때 특히 유용하며, Divide and Conquer와 같은 알고리즘 기법과 자주 결합됩니다. 재귀를 사용하려면 기본 조건(base case)과 재귀 조건(recursive case)을 정의해야 합니다.

기본 개념

1. 기본 조건 (Base Case): 재귀 호출을 멈추는 조건입니다. 더 이상 문제를 쪼갤 수 없을 때 기본 조건을 사용하여 결과를 반환합니다.
2. 재귀 조건 (Recursive Case): 함수가 자기 자신을 호출하는 부분입니다. 문제를 더 작은 부분으로 쪼개고, 그 부분을 해결하기 위해 다시 함수를 호출합니다.

예제

예제 1: 팩토리얼 계산

팩토리얼은 1부터 n까지의 정수를 모두 곱한 값입니다. 재귀를 사용하여 팩토리얼을 계산할 수 있습니다.

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

console.log(factorial(5)); // 120

예제 2: 피보나치 수열

피보나치 수열의 각 항은 앞의 두 항의 합입니다. 재귀를 사용하여 피보나치 수를 계산할 수 있습니다.

function fibonacci(n) {
    if (n <= 1) return n; // 기본 조건
    return fibonacci(n - 1) + fibonacci(n - 2); // 재귀 조건
}

console.log(fibonacci(7)); // 13

예제 3: 배열의 합 계산

재귀를 사용하여 배열의 합을 계산하는 예제입니다.

function sumArray(arr) {
    if (arr.length === 0) return 0; // 기본 조건
    return arr[0] + sumArray(arr.slice(1)); // 재귀 조건
}

let arr = [1, 2, 3, 4, 5];
console.log(sumArray(arr)); // 15

예제 4: 제곱근 만들기, helper 함수 사용

• 자바스크립트의 Math.prototype.pow()를 본따 함수를 선언합니다
• helper 함수는 재귀적이지 않은 외부 함수가 재귀적인 내부 함수를 호출하는 패턴입니다.

function power(number, cnt) {
  let result = 1;
  if (cnt === 0) return 1;

  function helper(number, cnt) {
    if (cnt === 0) return;

    result *= number;
    cnt--;

    helper(number, cnt);
  }
  helper(number, cnt);

  return result;
}

power(2,0) // 1
power(2,2) // 4
power(2,4) // 16

예제 5: 숫자 배열을 받아 모든 숫자의 곱을 반환하는 함수 만들기, helper 함수 사용

function productOfArray(arr) {
  let result = 1;
  if (arr.length === 0) return null;

  function helper(arr) {
    if (arr.length === 0) return;

    result *= arr[0];

    helper(arr.slice(1));
  }

  helper(arr);

  return result;
}

productOfArray([1,2,3]) // 6
productOfArray([1,2,3,10]) // 60

시간 복잡도

재귀 함수의 시간 복잡도는 함수의 호출 횟수와 각 호출당 작업의 양에 따라 다릅니다. 예를 들어, 피보나치 수열의 재귀 구현은 중복 계산이 많아 시간 복잡도가 O(2^n)으로 매우 비효율적입니다. 반면, 메모이제이션(memoization)을 사용하면 효율적으로 개선할 수 있습니다.

주의점

1. 기본 조건의 중요성: 기본 조건이 없으면 함수가 무한히 호출되어 스택 오버플로(stack overflow)가 발생합니다.
2. 재귀 깊이 제한: 대부분의 프로그래밍 언어는 재귀 호출의 최대 깊이를 제한합니다. 깊이가 너무 깊으면 스택 오버플로가 발생할 수 있습니다.
3. 메모이제이션: 중복 계산을 피하기 위해 메모이제이션을 사용하면 성능을 크게 향상시킬 수 있습니다.

활용 예시

재귀는 다음과 같은 다양한 문제에서 유용하게 사용됩니다:

• 트리 및 그래프 탐색 (예: DFS)
• 정렬 알고리즘 (예: 퀵 정렬, 병합 정렬)
• 조합론 문제 (예: 순열, 조합)
• 동적 계획법 문제에서 부분 문제 해결

재귀는 복잡한 문제를 단순화하고, 코드를 보다 직관적으로 작성하는 데 매우 유용한 도구입니다.