재귀함수와 스택 작동 원리

재귀 함수는 3중, 4중 for문 써야할 때 쓰면 좋다.

 

def DFS(x):
    if x > 0:
        DFS(x-1)
        print(x)

if __name__=="__main__":
    n = int(input())
    DFS(n)

3을 입력하면 출력은 1, 2, 3 순으로 출력된다. 

왜그럴까?

 

왜냐하면 재귀함수는 스택으로 작동하기 때문이다.

 

DFS(3) 을 하면

1. 매개변수 x = 3
2. 지역변수
3. 복귀주소 

이 세개가 스택에 쌓인다.

 

□                                     □

□ x=0, DFS(1) 복귀주소    □

□ x=1, DFS(2) 복귀주소    □

□ x=2, DFS(3) 복귀주소   □

□ x=3, 지역변수,복귀주소 □

□□□□□□□□□□□□□

 

하나의 묶음을 스택 프레임이라고도 한다.

스택 프레임을 하나씩 처리하고 복귀하면서 끝이 나게 된다.

 

그렇기 때문에 1, 2, 3 으로 출력이 된다.