1. 정의
재귀함수란 자기 자신을 다시 호출하는 함수이다. 재귀함수를 통해 큰 문제를 작은 문제로 나누어 해결할 수 있다. 이전 두 수의 합이 다음 수가 되는 피보나치 수열(Fibonacci Sequence)도 재귀함수로 구현할 수 있다. 하지만 재귀함수를 제대로 구현하기 위해서는 몇가지 알아야할 사항들이 존재한다.
def fibonacci(n):
if n <= 0:
return 1
return fibonacci(n-1) + fibonacci(n-2)2. 스택프레임과 메모리 문제
함수가 호출되면 메모리에는 스택 프레임이란 공간이 생긴다. 스택 프래임에는 함수 실행에 필요한 지역 변수들이 할당된다.두 수를 더하는 간단한 함수를 통해 스택 프레임에 대해서 알아보자.
def add(a, b):
c = a + b
return c
a = 10
b = 10
c = add(a, b)a와 b를 파라미터로 전달하고 add 함수를 호출하면 스택 프레임이라는 내부 공간이 생성된다. 해당 공간 속에 함수 내부에 있는 파라미터 a, b와 결과값인 지역 변수 c가 저장된다.
하지만 스택 프레임에 존재하는 a, b, c는 전역 변수인 a, b, c와는 서로 다른 변수이다. 함수 내에 존재하는 지역 변수들은 함수가 종료된 뒤에 스택 프레임이 사라지면서 같이 사라지게 된다.
하지만 재귀함수는 자기 자신을 계속해서 호출하기 때문에 메모리 속에 스택 프레임이 계속해서 쌓이게 된다. 따라서 재귀함수가 적절한 시기에 끝나지 않는다면 계속해서 생성되는 스택 프레임으로 인해 오류가 발생한다. 이때 발생하는 오류가 그 유명한 Stack Overflow 오류이다.
3. base case
재귀함수로 인해 발생할 수 있는 Stack Overflow 오류를 방지하기 위해서는 함수를 종료시켜줄 수 있는 조건이 필요하다. 이러한 조건을 base case라고 칭한다. 재귀함수의 파라미터가 base case에서 설정해놓은 조건과 일치하게 되면 재귀가 끝나며 함수가 종료된다.
피보나치 수열 함수의 예시에서 n의 값이 점차 줄다가 0에 도달하게 되면 base case를 만족시키며 재귀가 중단된다.
def fibonacci(n):
#base case
if n <= 0:
return 1
return fibonacci(n-1) + fibonacci(n-2)4. 결론
따라서 재귀 함수를 설계할 때는 다음 두 가지를 고려해야한다.
- 언제 어떤 파라미터를 전달하여 호출할 것인지
- 재귀 호출을 멈추는 조건인 base case
재귀 함수를 설계할 때는 함수의 파라미터가 언젠가는 반드시 base case를 만족하게끔 설계해야 오류를 발생시키지 않는다.
