[코딩테스트] 재귀함수

재귀 함수란?

 

: 재귀 함수는 자기 자신을 호출하여 원래 문제에 속한 더 작은 하위 문제를 해결하는 함수이다.

이를 통해 문제를 반복적으로 분해하다가, 더 이상 분해할 수 없는 기본 조건(base condition)에 도달하면 함수 호출을 종료한다. 

재귀 함수의 장점과 단점은 무엇인가?

 

 장점

• 코드가 반복적인 구조를 가진 문제(예: 특정 패턴의 탐색)를 간결하게 작성할 수 있습니다.
• 문제를 작게 나누어 해결하는 경우 구현이 상대적으로 단순해집니다.

단점

• 잘못된 구현이나 불필요한 깊이의 호출이 발생하면 성능이 저하될 수 있습니다.
• 깊은 재귀 호출로 인해 프로그램이 강제 종료될 가능성도 있습니다.

---

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

재귀 함수는 깊이(호출의 반복 횟수)가 깊어질수록 성능에 악영향을 줄 수 있다.

이때, 재귀 깊이를 줄이기 위한 몇 가지 방법을 사용할 수 있다.

메모제이션(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]

반복문으로 변환
재귀로 풀 수 있는 문제는 대부분 반복문을 통해 해결할 수도 있다.

반복문으로 변환할 경우, 재귀 함수 호출로 인한 추가적인 메모리 사용을 방지할 수 있다.

 

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

최적화된 종료 조건 설정
재귀 호출의 종료 조건을 잘 설정하면 불필요한 깊은 호출을 방지할 수 있다.

특히, 매번 상태를 변경하거나 갱신하여 기본 조건에 빨리 도달하도록 설계해야 한다.

---

재귀 함수를 구현하는 절차

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

기본 조건은 재귀 호출이 끝나야 할 시점을 정의하는 것이다.

만약 기본 조건이 없다면, 함수가 계속해서 자기 자신을 호출하여 무한 루프에 빠지게 되고, 결국 스택 오버플로우 오류를 발생시킨다.

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

2. 더 작은 문제로 분할:

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

또한 각 재귀 호출에서 문제의 크기를 줄여야 한다는 것이다. 만약 문제의 크기가 줄어들지 않으면, 기본 조건에 도달할 수 없게 되어 함수가 계속해서 호출되는 문제가 발생한다.

3. 재귀 호출:

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

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

---

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

1. 기본 조건을 확실하게 설정해야 한다.
2. 재귀 깊이 고려해야 한다. 

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

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

import sys

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

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

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

 

 

 

출처: "코딩 테스트 합격자 되기-박경록"