JavaScript - 재귀함수

재귀 함수란?

재귀 함수(Recursion)는 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법입니다.

반복문과 유사하지만, 특정 조건을 만족할 때까지 자기 자신을 계속 호출하는 것이 특징입니다.

---

📌 재귀 함수의 기본 구조

function recursiveFunction(param) {
    if (조건) { // 종료 조건 (Base Case)
        return 결과;
    }
    return recursiveFunction(새로운 값); // 자기 자신을 호출
}

💬 예제 1: 팩토리얼 계산

팩토리얼(n!)은 n × (n-1) × (n-2) × ... × 1로 정의됩니다.

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

console.log(factorial(5)); // 120 (5! = 5 × 4 × 3 × 2 × 1)

💬 예제 2: 피보나치 수열

피보나치 수열은 n번째 수 = (n-1)번째 수 + (n-2)번째 수의 규칙을 가집니다.

function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2); // 재귀 호출
}

console.log(fibonacci(6)); // 8 (0, 1, 1, 2, 3, 5, 8)

---

🚀 재귀 함수의 핵심 개념

➡️ 종료 조건(Base Case): 무한 루프를 방지하기 위해 반드시 필요합니다.

➡️ 재귀 호출(Recursive Call): 함수가 자기 자신을 호출하여 문제를 점진적으로 해결합니다.

➡️ 스택 메모리 관리: 재귀 호출이 많아지면 스택 오버플로우(Stack Overflow)가 발생할 수 있으므로 주의해야 합니다.

---

재귀 vs 반복문

💬 재귀 함수는 코드가 간결하지만, 스택을 많이 사용하므로 반복문(Loop)보다 비효율적일 수 있습니다. 따라서 작은 입력값에는 재귀를 사용해도 괜찮지만, 큰 입력값에는 반복문을 고려하는 것이 좋습니다.

// 반복문을 이용한 팩토리얼 계산
function factorialIterative(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

정리

재귀 함수는 알고리즘 문제에서 자주 사용되며, 특히 DFS(깊이 우선 탐색), 분할 정복(Divide and Conquer) 등에 활용됩니다. 하지만 종료 조건을 명확히 정의하고, 성능 문제를 고려하는 것이 중요합니다! 🚀