오류가 발생하는 이유는 재귀 함수가 계속해서 자기 자신을 호출하기 때문입니다. 계속 호출하면 스택 프레임이 계속 생성되고 결국 스택 오버플로(stack overflow)가 발생합니다. 이러한 사태를 막으려면 ‘탈출 조건’이 필요합니다. 탈출 조건이란 함수 호출을 멈추는 조건이라고 생각하면 됩니다. 팩토리얼에서 탈출 조건은 n이 0 혹은 1일 때 값이 1이라는 것입니다. 이제 탈출 조건을 함수 정의에 추가하겠습니다.

코드 13-2 data_structure_2/ds_1/factorial.py ②

def factorial(n):
    # 탈출 조건
    if n <= 1:                 #1
        return 1

    return factorial(n-1) * n  #2

탈출 조건이 추가되었습니다. n이 1 이하면 1을 반환하고 더 이상 자기 자신을 호출하지 않고 빠져나갑니다(#1).

n이 3일 때 재귀 함수의 작동 방식을 스택 프레임을 쌓아가며 살펴보겠습니다. 그림 13-1은 factorial(3)을 호출했을 때 생성되는 스택 프레임입니다.

그림 13-1 재귀 함수 스택 프레임 ①

n이 3이므로 #1은 건너뛰고 #2에서 factorial(2)를 호출합니다. 다음 그림을 볼까요?