[알고리즘] 재귀(Recursion)

 

1. 재귀란 무엇인가?

재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법이다. 이는 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 방식으로, 수학의 귀납법과 유사한 개념이다.

재귀를 이해하기 위해 한 가지 이야기를 들어본다.

드래곤은 아래와 같은 숫자를 가지고 있다.

[2, 4, 6, 8, 9, 10]

우리의 주인공 마틴이, 드래곤에게 말한다.

"이 숫자 목록에 홀수가 있는지 확인해줘."

하지만 드래곤은 마법에 걸려서 오직 첫 번째 숫자만 확인할 수 있다. 그래서 마틴은 다음과 같이 생각한다.

1. 첫 번째 숫자가 홀수인지 확인한다. 아니라면 제거한다.
2. 남은 목록은 [4, 6, 8, 9, 10]이며, 다시 같은 방식으로 확인한다.
3. 4도 홀수가 아니므로 [6, 8, 9, 10]로 넘어간다.
4. 6도 홀수가 아니므로 [8, 9, 10]로 넘어간다.
5. 8도 홀수가 아니므로 [9, 10]으로 넘어간다.
6. 9는 홀수이므로, 목록에 홀수가 있다는 결론을 내린다.

이것이 바로 재귀적 사고이다. 큰 문제를 작은 문제로 나누어 해결하는 방식이다.

---

2. 재귀 함수의 핵심 요소

모든 재귀 함수는 반드시 다음 두 가지 요소를 가져야 한다.

1) 종료 조건 (Base Case)

재귀 호출이 멈추는 지점이다. 이것이 없으면 함수가 무한히 자기 자신을 호출하게 된다.

2) 재귀 호출 (Recursive Call)

함수가 자기 자신을 호출하되, 다른 입력값으로 호출해야 한다. 같은 입력값으로 계속 호출하면 무한 루프에 빠진다.

---

3. 호출 스택(Call Stack) 이해하기

재귀를 이해하려면 호출 스택의 개념을 이해해야 한다.

호출 스택이란?

호출 스택은 함수 호출을 관리하는 데이터 구조이다. 마치 책상 위의 종이 더미처럼 작동한다.

• 새로운 함수가 호출되면 스택의 맨 위에 추가된다.
• 함수가 종료되면 스택의 맨 위에서 제거된다.
• 가장 최근에 호출된 함수가 가장 먼저 처리된다 (LIFO: Last In, First Out).

호출 스택 예시

function wakeUp() {
    takeShower();
    eatBreakfast();
    console.log("Ok ready to go to work!");
}

function takeShower() {
    return "Showering!";
}

function eatBreakfast() {
    const meal = cookFood();
    return `Eating ${meal}`;
}

function cookFood() {
    const foods = ["Eggs", "Toast", "Protein Shake"];
    const randomFood = foods[Math.floor(Math.random() * foods.length)];
    return randomFood;
}

wakeUp();

호출 스택의 변화:

1. wakeUp() 호출 → 스택에 추가
2. takeShower() 호출 → 스택에 추가
3. takeShower() 완료 → 스택에서 제거
4. eatBreakfast() 호출 → 스택에 추가
5. cookFood() 호출 → 스택에 추가
6. cookFood() 완료 → 스택에서 제거
7. eatBreakfast() 완료 → 스택에서 제거
8. wakeUp() 완료 → 스택에서 제거

---

4. 첫 번째 재귀 함수 만들기

이제 실제로 재귀 함수를 작성해본다.

CountDown 함수

function countDown(num) {
    if (num <= 0) {
        console.log("All done!");
        return;
    }

    console.log(num);
    countDown(num - 1);
}

countDown(5);
// 출력:
// 5
// 4
// 3
// 2
// 1
// All done!

비재귀적 방법 (반복문)

function countDownIterative(num) {
    for (let i = num; i > 0; i--) {
        console.log(i);
    }
    console.log("All done!");
}

재귀 함수의 실행 과정

countDown(3)을 호출했을 때의 과정은 다음과 같다.

1. countDown(3) 호출
   • num = 3, 3 <= 0은 거짓이다.
   • console.log(3) 실행
   • countDown(2) 호출
2. countDown(2) 호출
   • num = 2, 2 <= 0은 거짓이다.
   • console.log(2) 실행
   • countDown(1) 호출
3. countDown(1) 호출
   • num = 1, 1 <= 0은 거짓이다.
   • console.log(1) 실행
   • countDown(0) 호출
4. countDown(0) 호출
   • num = 0, 0 <= 0은 참이다.
   • console.log("All done!") 실행
   • 함수 종료

---

5. 더 복잡한 재귀 예제

팩토리얼 계산

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

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

피보나치 수열

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

console.log(fibonacci(6)); // 8

배열 합계 구하기

function sumArray(arr) {
    if (arr.length === 0) {
        return 0;
    }
    return arr[0] + sumArray(arr.slice(1));
}

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

---

6. 재귀 함수 작성 시 주의사항

1) 무한 재귀 방지

function badRecursion(n) {
    console.log(n);
    badRecursion(n - 1); // 종료 조건 없음
}

function goodRecursion(n) {
    if (n <= 0) return;
    console.log(n);
    goodRecursion(n - 1);
}

2) 스택 오버플로우

factorial(10000); // RangeError: Maximum call stack size exceeded

3) 성능 고려사항

// 느린 피보나치
function fibonacciSlow(n) {
    if (n <= 1) return n;
    return fibonacciSlow(n - 1) + fibonacciSlow(n - 2);
}

// 빠른 피보나치 (메모이제이션)
function fibonacciFast(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) return n;

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

---

7. 재귀 vs 반복문

재귀의 장점

• 코드가 직관적이고 간결하다.
• 수학적인 문제를 표현하기 쉽다.
• 트리 구조나 그래프 탐색에 유리하다.

재귀의 단점

• 호출 스택 사용으로 메모리 소모가 크다.
• 성능이 반복문보다 떨어질 수 있다.
• 스택 오버플로우 발생 위험이 있다.

언제 재귀를 사용할까?

• 트리 구조 탐색 (DOM 트리, 파일 시스템)
• 분할 정복 알고리즘 (퀵 정렬, 병합 정렬)
• 백트래킹 문제

---

마무리

재귀는 처음에는 어려워 보이지만, 핵심 원리를 이해하면 매우 강력한 도구가 된다. 중요한 것은 다음 세 가지이다.

1. 종료 조건을 명확히 정의한다.
2. 다른 입력값으로 재귀 호출한다.
3. 문제를 작은 단위로 나누어 생각한다.

재귀를 완전히 이해하려면 시간이 걸릴 수 있다. 조급해하지 말고, 예제를 직접 작성하면서 차근차근 익숙해지면 된다.