[자료구조] 재귀 함수( Recursive Function)

Recursive Fuction (재귀 함수)

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다.

- 예제 : 재귀 함수

def recursive_fuction():
    print("재귀 함수를 호출합니다.")
    recursive_fuction()

recursive_fuction()

위 함수를 실행하면 '재귀 함수를 호출합니다.'라는 문자열이 무한히 출력된다. 여기서 정의한 recursive_function()이 자기 자신을 계속해서 추가로 불러오기 때문이다. 물론 어느 정도 출력하다가 다음과 같은 오류 메시지를 출력하고 멈출 것이다.

RecursionError: maximum recursion depth exceed while pickling an object

이 오류 메시지는 재귀(Recursion)의 최대 깊이를 초과했다는 내용이다. 보통 파이썬 인터프리터는 호출 횟수 제한이 있는데 이 한계를 벗어났기 때문이다. 따라서 무한대로 재귀 호출을 진행할 수는 없다.

- 재귀 함수의 종료 조건

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야한다.

자칫 종료 조건을 명시하지 않으면 함수가 무한 호출이 될 수 있다.

- 예제 : 재귀 함수 종료

def recursive_function(i):
    #100번째 출력했을 때 종료되도록 종료 조건 명시
    if i == 100:
        return
     print(i,'번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다.')
     recursive_function(i + 1)
     print(i,'번째 재귀 함수를 종료합니다.')

recursive_fuction(1)

재귀 함수의 수행은 스택 자료구조를 이용 한다.

함수를 계속 호출했을 때, 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.

따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. (ex : DFS)

- Factorial

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n + 1):
        result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_recursion(n):
    if n <= 1: # n이 1이하인 경우 1을 반환
        return 1
    # n! = n * (n - 1)!을 그대로 코드로 작성하기
    return n * factorial_recursion(n - 1)

# 각각의 방식으로 구현한 n! 출력 (n = 5)
print('반복적으로 구현: ', factorial_iterative(5))
print('재귀적으로 구현: ', factorial_recursion(5))

- 결과값

반복적으로 구현 : 120
재귀적으로 구현 : 120

실행 결과는 동일하다. 그러면 반복 함수 대신 재귀함수를 사용했을 때 장점은 무엇일까?

=> 두 코드를 비교하였을 때, 재귀 함수의 코드가 더 간결 한 것을 알 수 있다.

이렇게 간결해진 이유는 재귀 함수가 수학의 점화식(재귀식)을 그대로 소스 코드로 옮겼기 때문이다.