[algorithm] 재귀 함수(Recursive Function) (Python)

재귀함수

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

def recursive_func():
    print('재귀 함수 호출')
    recursive_func()

recursive_func()

파이썬에서는 재귀를 호출하는 과정에서의 깊이 제한이 있기 때문에 별다른 설정을 하지 않고 함수를 재귀적으로 호출하게 되면 오류가 발생한다.

 

def recursive_func():
    if i == 100:
        return
    print(i, '번째 재귀함수에서', i+1, '번째 재귀함수 호출')
    recursive_function(i+1)
    print(i, '번째 재귀함수 종료')

recursive_func(1)

재귀 함수를 문제 풀이에서 사용할 때는 위처럼 재귀 함수의 종료 조건을 반드시 명시해야 한다.

 

재귀함수 구현 예제(팩토리얼)

n! = 1 x 2 x 3 x ... x (n-1) x n

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

# 재귀적으로 구현한 n!
def factorial_recursive(n):
    if n <= 1: # n이 1이하인 경우 1 반환 -> 0!과 1!의 값은 1
        return 1 
    # n! = n * (n-1)!
    return n * factorial_recursive(n-1)

print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))

# output
>>> 반복적으로 구현: 120
>>> 재귀적으로 구현: 120

 

재귀 함수 사용시 유의 사항

• 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있지만 오히려 다른사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용
• 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음
• 재귀 함수가 반복문보다 유리할 경우도 있고 불리한 경우도 있음
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임. 그래서 스택을 사용할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많음.