재귀함수

재귀함수

• 재귀함수란, 자기 자신을 다시 호출하는 함수이다.

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

recursive_function()

"재귀함수를 호출합니다" 라는 문자열을 무한히 출력하는 듯 싶다가, 최대 재귀 깊이 초과 메시지가 출력되며 에러가 발생한다. 함수는 호출될 때마다 스택 프레임에 쌓이게 되는데,재귀의 경우 계속 호출만 되고 반환이 되지 않아 스택이 계속 쌓이게 된다. 당연히 컴퓨터메모리는 한정된 메모리를 가지고 있으므로 이 스택이 계속 쌓이면 메모리에 이상이 발생할 수 있으므로 그 전에 중단시켜버리는 것이다.
재귀함수는 DFS를 실질적으로 구현하고자 할 때 자주 사용되는 방법중 하나이므로, 꼭 이해하고 있어야 한다.

• 의도적으로, 무한루프를 생각하여 재귀함수를 이용하지 않는다면, 반드시 재귀함수의 종료조건을 명시해야 한다.
• 아래는 종료조건을 포함한 재귀함수의 예제이다.

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

이처럼 재귀함수는 스택에 데이터를 넣었다가 꺼내는 동작을 수행한다.

팩토리얼 구현 예제

수학적으로 0!과 1! 의 값은 1이다.

반복문을 사용하여 구현한 n!

def factorial_iterative(n):
    result = 1
    for i in range(n,0,-1):
        result = result*i
    return result

재귀적으로 구현한 n!

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

재귀함수 사용시 유의사항

• 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음
• 컴퓨터가 함수를 연속적으로 호출하면, 컴퓨터 메모리 내부의 스택 프레임에 쌓임
• 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 많음

대표적으로, DFS를 간결하고 짧은 코드로 작성하기 위해 단순히 재귀함수를 이용하여 재귀함수를 구현하기도 함