[코딩테스트 합격자 되기 + ] 재귀

재귀

0. 기본 개념

Python 개발자로서 면접 준비를 할 때, 재귀 함수에 대한 질문을 자주 받게 됩니다. 주로 다음과 같은 질문들이 있을 수 있습니다:

1. 재귀 함수란 무엇인가?
   • 재귀 함수는 자기 자신을 호출하여 원래 문제의 더 작은 하위 문제를 해결하는 함수입니다. 이를 통해 문제를 반복적으로 분해하다가, 더 이상 분해할 수 없는 기본 조건(base condition)에 도달하면 함수 호출을 종료합니다.
2. 재귀 함수의 장점과 단점은 무엇인가?
   • 장점:
     • 코드가 반복적인 구조를 가진 문제(예: 특정 패턴의 탐색)를 간결하게 작성할 수 있습니다.
     • 문제를 작게 나누어 해결하는 경우 구현이 상대적으로 단순해집니다.
   • 단점:
     • 잘못된 구현이나 불필요한 깊이의 호출이 발생하면 성능이 저하될 수 있습니다.
     • 깊은 재귀 호출로 인해 프로그램이 강제 종료될 가능성도 있습니다.

---

1. 재귀 함수에서 재귀 깊이를 줄이기 위한 방법

재귀 함수는 깊이(호출의 반복 횟수)가 깊어질수록 성능에 악영향을 줄 수 있습니다. 이때, 재귀 깊이를 줄이기 위한 몇 가지 방법을 사용할 수 있습니다:

1. Memoization:
   • 이전에 계산한 값을 저장해 두었다가 재사용하는 기법입니다. 이를 통해 동일한 계산을 여러 번 반복하지 않게 되어 재귀 호출 횟수를 줄일 수 있습니다.

     memo = {}
     def fibonacci(n):
       if n in memo:
           return memo[n]
       if n <= 1:
           return n
       memo[n] = fibonacci(n-1) + fibonacci(n-2)
       return memo[n]

2. 반복문으로 변환:
   • 재귀로 풀 수 있는 문제는 대부분 반복문을 통해 해결할 수도 있습니다. 반복문으로 변환할 경우, 재귀 함수 호출로 인한 추가적인 메모리 사용을 방지할 수 있습니다.

     def fibonacci_iterative(n):
       a, b = 0, 1
       for _ in range(n):
           a, b = b, a + b
       return a

3. 최적화된 종료 조건 설정:
   • 재귀 호출의 종료 조건을 잘 설정하면 불필요한 깊은 호출을 방지할 수 있습니다. 특히, 매번 상태를 변경하거나 갱신하여 기본 조건에 빨리 도달하도록 설계해야 합니다.

---

2. 재귀 함수를 구현하는 절차

재귀 함수를 구현할 때는 세 가지 중요한 단계를 따르는 것이 좋습니다. 각 단계는 함수가 적절하게 작동하고, 재귀 호출을 효율적으로 사용할 수 있도록 도와줍니다. 이 절차는 모든 재귀 함수의 기본적인 구조를 형성하며, 복잡한 문제를 간결하게 해결하는 방법론을 제시합니다.

1. 기본 조건 설정 (Base Condition):

재귀 함수의 첫 번째 단계는 기본 조건을 설정하는 것입니다. 기본 조건은 재귀 호출이 끝나야 할 시점을 정의합니다. 기본 조건이 없으면 함수가 계속해서 자기 자신을 호출하여 무한 루프에 빠지게 되고, 결국 스택 오버플로우 오류를 발생시킵니다.

기본 조건은 문제의 가장 작은 단위를 처리하는 코드로 작성해야 하며, 일반적으로 재귀 호출의 종료를 의미합니다.

2. 더 작은 문제로 분할:

재귀의 핵심은 문제를 작은 문제로 나누는 것입니다. 원래 문제를 더 작은 하위 문제로 분할함으로써, 최종적으로 기본 조건에 도달할 수 있습니다. 하위 문제는 원래 문제와 동일한 성질을 가져야 하며, 이는 재귀 호출이 문제를 반복적으로 해결할 수 있는 이유입니다.

문제를 하위 문제로 분할할 때 중요한 점은, 각 재귀 호출에서 문제의 크기를 줄여야 한다는 것입니다. 만약 문제의 크기가 줄어들지 않으면, 기본 조건에 도달할 수 없게 되어 함수가 계속해서 호출되는 문제가 발생합니다.

3. 재귀 호출:

마지막 단계는 재귀적으로 자기 자신을 호출하는 것입니다. 이때, 더 작은 문제를 해결하기 위해 동일한 함수를 호출하게 됩니다. 재귀 호출은 기본 조건에 도달할 때까지 계속되며, 기본 조건에 도달하면 결과가 반환되기 시작합니다.

이 과정에서 주의할 점은, 함수가 재귀 호출을 할 때마다 상태(예: 변수 값)가 변화해야 한다는 것입니다. 그렇지 않으면 문제의 크기가 줄어들지 않아 무한 루프에 빠질 수 있습니다.

파이썬 예시

다음은 팩토리얼을 계산하는 재귀 함수의 예시입니다:

def factorial(n):
    # 1. 기본 조건 설정: n이 0이거나 1일 때는 더 이상 재귀 호출을 하지 않고 결과를 반환
    if n == 0 or n == 1:
        return 1
    # 2. 더 작은 문제로 분할: n을 n-1로 줄여서 문제를 해결
    else:
        return n * factorial(n - 1)

# 예시 실행
print(factorial(5))  # 출력: 120

예시 설명:

1. 기본 조건: n == 0 또는 n == 1일 때, 함수는 더 이상 자기 자신을 호출하지 않고 1을 반환합니다.
2. 더 작은 문제로 분할: 각 함수 호출에서 n의 값을 1씩 줄여서 더 작은 문제로 만들고, 결국 n == 0이나 n == 1에 도달하게 됩니다.
3. 재귀 호출: factorial(n - 1)을 호출하여 자기 자신을 계속 호출합니다.

이 과정을 통해 factorial(5)는 다음과 같은 방식으로 계산됩니다:

factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1  (기본 조건)

최종적으로 5 * 4 * 3 * 2 * 1 = 120이 계산됩니다.

두 번째 예시: 피보나치 수열

다음은 피보나치 수열을 계산하는 재귀 함수의 예시입니다:

def fibonacci(n):
    # 1. 기본 조건 설정: n이 0이거나 1일 때는 그 값을 반환
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # 2. 더 작은 문제로 분할: n을 n-1과 n-2로 줄여서 문제를 해결
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 예시 실행
print(fibonacci(6))  # 출력: 8

예시 설명:

1. 기본 조건: n == 0일 때는 0을 반환하고, n == 1일 때는 1을 반환합니다.
2. 더 작은 문제로 분할: n의 값을 두 개로 나눠서 각각 fibonacci(n - 1)과 fibonacci(n - 2)을 호출하여 더 작은 문제로 만듭니다.
3. 재귀 호출: 두 개의 재귀 호출을 통해 피보나치 수열을 계산하며, 기본 조건에 도달할 때까지 계속됩니다.

이 과정을 통해 fibonacci(6)는 다음과 같은 방식으로 계산됩니다:

fibonacci(6) = fibonacci(5) + fibonacci(4)
fibonacci(5) = fibonacci(4) + fibonacci(3)
...
fibonacci(1) = 1  (기본 조건)
fibonacci(0) = 0  (기본 조건)

최종적으로 8이 계산됩니다.

---

3. 재귀 함수 구현 시 주의해야 할 점

재귀 함수를 구현할 때는 몇 가지 주의해야 할 중요한 사항들이 있습니다. 이러한 요소들은 성능 문제나 예상치 못한 오류를 방지하는 데 중요한 역할을 합니다. 아래에 그 주의사항들을 자세히 설명하겠습니다.

1. 기본 조건을 확실하게 설정:

재귀 함수에서 기본 조건(Base Condition)이란, 재귀 호출을 멈추는 지점을 정의하는 코드입니다. 만약 이 기본 조건이 제대로 설정되지 않으면, 함수는 무한히 자기 자신을 호출하게 되어 무한 루프에 빠집니다. 결국 프로그램이 스택 오버플로우(Stack Overflow) 에러로 인해 비정상적으로 종료될 수 있습니다.

기본 조건이 명확하지 않으면, 시스템 자원을 모두 소모하게 되어 프로그램이 비효율적으로 작동할 수 있으므로 이를 확실히 설정하는 것이 중요합니다.

2. 재귀 깊이 고려:

재귀 호출은 호출할 때마다 메모리의 스택 공간을 사용합니다. 따라서 재귀 호출이 너무 깊어지면 메모리가 부족해질 수 있습니다. 특히, Python에서는 재귀 깊이가 기본적으로 제한되어 있어, 그 한도를 넘어서면 RecursionError가 발생합니다.

따라서 재귀 깊이를 고려하여 설계해야 하며, 가능한 경우 반복문을 통해 문제를 해결하는 방법도 고려해야 합니다. 혹은 sys.setrecursionlimit() 함수를 사용해 최대 재귀 깊이를 조정할 수 있습니다.

import sys

# 재귀 깊이 제한을 늘리기
sys.setrecursionlimit(2000)

그러나 이 방법은 메모리 사용량을 늘리기 때문에 신중히 사용해야 합니다.

3. 반복적 재계산 방지:

많은 재귀 함수에서 동일한 하위 문제를 여러 번 계산하는 경우가 발생할 수 있습니다. 이로 인해 중복 계산이 일어나고 성능이 크게 저하될 수 있습니다. 이를 방지하기 위해 메모이제이션(Memoization)을 사용하여 이미 계산된 값을 저장하고 재사용하는 방법을 고려해야 합니다.

다음은 메모이제이션을 사용하는 피보나치 수열 계산 예시입니다.

# 메모이제이션을 위한 딕셔너리
memo = {}

def fibonacci(n):
    # 1. 기본 조건
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # 2. 이미 계산된 값이면 그 값을 반환
    if n in memo:
        return memo[n]
    # 3. 계산된 값을 메모이제이션 딕셔너리에 저장
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return memo[n]

# 예시 실행
print(fibonacci(10))  # 출력: 55

예시 설명:

1. 기본 조건: n == 0일 때 0을 반환하고, n == 1일 때 1을 반환하여 재귀 호출을 멈춥니다.
2. 메모이제이션: 이미 계산된 값이 있으면 메모에서 가져오고, 그렇지 않으면 계산 후 메모에 저장합니다.
3. 재귀 호출: 피보나치 수열의 정의에 따라 fibonacci(n-1)과 fibonacci(n-2)를 호출합니다.

이렇게 메모이제이션을 사용하면 중복 계산을 방지할 수 있어 성능이 크게 향상됩니다.