[알고리즘] 재귀함수 작동 과정

date

Oct 9, 2023

slug

ag-2

author

status

Public

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

핵심은 ‘기본 케이스’와 ‘재귀 케이스’이다.

: 더이상 자신을 호출하지 않고 결과를 반환하는 조건.

: 문제의 크기나 복잡성을 줄여서 같은 문제를 다시 푸는 부분. 자기 자신을 다시 호출 한다.


def factorial(n):
    if n == 0:  # base case
        return 1
    else:       # recursive case
        return n * factorial(n-1)

factorial(3)의 실행 과정은 아래와 같습니다:

Then, each call resolves: ◦ factorial(1) returns 1 * factorial(0) = 1 ◦ factorial(2) returns 2 * factorial(1) = 2 ◦ Finally, factorial(3) returns 3 * factorial(2) = 6

⇒ 스택 구조와 비슷하게 동작한다.