재귀 함수

재귀 함수(Recursive funtion)은 자기 자신을 다시 호출하는 함수를 의미한다. 재귀 함수를 사용할 때는 종료 조건을 꼭 명시해야 한다. 그렇지 않으면 재귀의 깊이를 초과했다는 RecursionError가 발생한다.

 

 

종료 조건을 명시하는 예시는 다음과 같다. 자신을 호출하기 전에 종료 조건을 명시해야한다.

def recursive_function(i):
    # 10번째 출력했을 때 종료되도록 종료 조건 명시
    if i == 5:
        return
    print(f"{i}번째 재귀 함수에서 {i + 1}번째 재귀 함수 호출")
    recursive_function(i + 1)
    ########################################
    print(f"{i}번째 재귀 함수 종료")

recursive_function(1)

1번째 재귀 함수에서 2번째 재귀 함수 호출
2번째 재귀 함수에서 3번째 재귀 함수 호출
3번째 재귀 함수에서 4번째 재귀 함수 호출
4번째 재귀 함수에서 5번째 재귀 함수 호출
4번째 재귀 함수 종료
3번째 재귀 함수 종료
2번째 재귀 함수 종료
1번째 재귀 함수 종료

 

출력 결과를 보면 알 수 있는 것이 재귀 함수의 수행은 스택 자료구조를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료된다.

 

 

재귀 함수는 수학의 점화식과 비슷하다. 예를 들어 팩토리얼의 점화식은 다음과 같다.

 

1. 정수 n이 0 또는 1일 때: $f(n) = 1$
2. 정수 n이 1 보다 클 때: $f(n) = n \times f(n-1)$

 

이를 코드로 표현하면 다음과 같다.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)