재귀함수

재귀함수는 본인이 본인을 호출하는 함수이다.

재귀함수를 만들 때 반드시 존재해야 하는 조건이 2가지이다.

1. 반드시 끝나는 조건이 존재해야 한다는 것.

2. 계산 범위가 점점 줄어들어야 한다는 것.

가장 많이 예시로 드는 팩토리얼 코드를 보겠다.

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

print(factorial_recursive(3))

// 결과
// 3
// 2
// 1
// 6

 

기본적으로 재귀함수는 스택구조로 이루어져 있기 때문에 맨 마지막에 호출된 함수가 먼저 끝이난다는 점을 알고 있어야 한다.

천천히 로직대로 따라가보자.

n = 3 , result = 3 * factorial_recursive(2)(미완성)

n = 2, result = 2 * factorial_recursive(1)(미완성)

n = 1, result = 1 * factorial_recursive(0)(미완성)

 

factorial_recursive(1)은 n이 1일 때 1을 리턴하므로 다시 거슬러 올라간다.

 

n = 1, result = 1 * 1(완성) return 1

n = 2, result = 2 * factorial_recursive(1)(미완성)

n = 3 , result = 3 * factorial_recursive(2)(미완성)

 

 

n = 2, result = 2 * 1(완성) return 2

n = 3 , result = 3 * factorial_recursive(2)(미완성)

 

 

n = 3 , result = 3 * 2 (완성) return 6