재귀 함수

DFS와 BFS를 구현하려면 재귀 함수도 이해해야 한다.

 

-재귀 함수의 종료 조건

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

 

컴퓨터 내부에서 재귀 함수의 수행은 스택을 사용한다. 함수를 계속 호출했을 때 마지막에 호풀한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 연속해서 호풀되는 함수는 메인 메모리의 스택에 적재된다. 그래서 재귀 함수는 스택과 같다는 말이 틀린 말이 아니다.

 

# 반복적으로 구현한 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을 반환
        return 1
    # n! = n * (n - 1)!를 그대로 코드로 작성하기
    return n * factorial_recursive(n - 1)

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

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

1. n이 0 혹은 1일 때, factorial(n) = 1

2. n이 1보다 클 때, factorial(n) = n * factorial(n-1)

 

여기서 종료 조건 n이 0 혹은 1일 때 이다.