TIL: 재귀 함수(Recursive Function)

재귀 함수(Recursive Function)

• 재귀 함수(Recursive Function)란 자기 자신을 호출하는 함수를 의미한다
• 즉, 함수 내부에서 자신을 다시 호출하는 방식으로 특정 문제를 해결하는 기법이다

---

재귀 함수의 기본 구조

• 재귀 함수는 보통 다음과 같은 구조를 가진다

func recursiveFunction() {
    // 종료 조건 (Base Case)
    if 조건 {
        return
    }

    // 자기 자신을 다시 호출 (Recursive Case)
    recursiveFunction()
}

---

재귀 함수의 핵심 요소

1. 기본 종료 조건(Base Case) ➡️ 재귀 호출이 무한히 반복되지 않도록 반드시 필요
2. 재귀 호출(Recursive Case) ➡️ 함수가 자기 자신을 다시 호출

---

재귀 함수의 동작 원리

• 재귀 함수는 호출될 때마다 스택(Stack) 메모리에 새로운 함수 인스턴스를 생성하여, 기본 종료 조건(Base Case)이 충족되면 함수가 차례로 종료된다

---

재귀 함수 예제

기본적인 재귀 함수

func countdown(_ n: Int) {
    if n <= 0 {  // 종료 조건
        print("끝!")
        return
    }
    
    print(n)
    countdown(n - 1)  // 재귀 호출
}

countdown(5)


// 출력 결과
5
4
3
2
1
끝!

동작 과정

1. countdown(5) 호출 ➡️ 5 출력 ➡️ countdown(4) 호출
2. countdown(4) 호출 ➡️ 4 출력 ➡️ countdown(3) 호출
3. countdown(3) 호출 ➡️ 3 출력 ➡️ countdown(2) 호출
4. countdown(2) 호출 ➡️ 2 출력 ➡️ countdown(1) 호출
5. countdown(1) 호출 ➡️ 1 출력 ➡️ countdown(0) 호출
6. countdown(0) 호출 ➡️ 종료 조건 충족 ➡️ 끝! 출력 후 함수 종료

• 재귀 함수는 마치 "함수 호출 스택"에 쌓였다가, 종료 조건을 만나면 하나씩 사라지는 방식으로 동작한다

---

재귀 함수의 활용 예제

1. 팩토리얼(Factorial) 계산

• 팩토리얼(n!)은 n * (n - 1) * (n - 2) * ... * 1을 의미한다.
  수식으로 나타내면 다음과 같다

n! = n * (n-1)!

• 즉, 팩토리얼은 자기 자신을 포함하는 정의이므로 재귀 함수로 쉽게 구현할 수 있다

func factorial(_ n: Int) -> Int {
    if n == 0 { // 종료 조건 (0! = 1)
        return 1
    }
    return n * factorial(n - 1) // 재귀 호출
}

print(factorial(5)) // 5! = 5 * 4 * 3 * 2 * 1 = 120


// 출력 결과
120

※ 팩토리얼 함수의 호출 과정

factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1  // 종료 조건

• 팩토리얼 함수는 재귀적으로 n - 1 을 계속 호출하며, n = 0 이 되면 종료된다

---

2. 피보나치 수열(Fibonacci Sequenc)

• 피보나치 수열은 다음과 같이 정의된다

F(n) = F(n-1) + F(n-2)
F(0) = 0, F(1) = 1

• 즉, 현재 항은 이전 두 항의 합으로 계산된다

func fibonacci(_ n: Int) -> Int {
    if n == 0 { return 0 } // 종료 조건
    if n == 1 { return 1 } // 종료 조건
    
    return fibonacci(n - 1) + fibonacci(n - 2) // 재귀 호출
}

print(fibonacci(5)) // 0, 1, 1, 2, 3, 5 → 결과: 5


// 출력 결과
5

※ 피보나치 함수의 호출 과정

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)
...

---

재귀 함수의 장 · 단점

재귀 함수의 장점

1. 코드가 간결하고 직관적 ➡️ 재귀적으로 정의된 문제를 그대로 코드로 표현 가능
2. 일부 알고리즘(DFS, 백트래킹 등)에서 매우 효과적
3. 반복문 없이도 반복적인 문제를 해결 가능

---

재귀 함수의 단점

1. 메모리 사용량 증가(스택 오버플로우 위험) ➡️ 함수 호출이 깊어질수록 스택 메모리를 많이 사용
2. 속도가 느릴 수 있음(특히 피보나치 같은 중복 호출이 많은 경우)
3. 반복문(Iterative) 방식이 더 효율적인 경우가 많음 ➡️ 예) for 또는 while 루프로 해결 가능하면 반복문이 더 좋음

---

재귀 함수를 최적화하는 방법

1. 꼬리 재귀(Tail Recursion)

• 재귀 함수의 호출이 끝난 후 추가 연산이 없는 형태
• Swift는 꼬리 재귀 최적화(Tail Call Optimization, TCO)를 자동 지원하지 않는다
• 하지만, 꼬리 재귀 방식으로 작성하면 명시적인 반복문으로 변환하기 쉽다
• 꼬리 재귀를 사용하면 불필요한 스택 사용을 줄일 수 있다

func factorialTail(_ n: Int, _ result: Int = 1) -> Int {
    if n == 0 { return result } // 종료 조건
    return factorialTail(n - 1, n * result) // 꼬리 재귀
}

print(factorialTail(5)) // 120

---

2. 메모이제이션(Memoization)

• 재귀 호출이 중복되는 경우, 결과를 저장해두고 재사용하는 방식
• 메모이제이션을 사용하면 중복 계산을 방지하여 성능이 향상된다
• 예) 피보나치 수열을 최적화 (동적 프로그래밍 방식)

var memo: [Int: Int] = [:]

func fibonacciMemo(_ n: Int) -> Int {
    if let value = memo[n] {
        return value
    }
    if n == 0 { return 0 }
    if n == 1 { return 1 }

    memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2)
    return memo[n]!
}

print(fibonacciMemo(50)) // 매우 빠르게 결과 도출