220831_TIL_재귀함수와 스택

재귀함수와 스택에 관해 도식화한 자료를 통한 이해

Code

def DFS(x):									
	if x>0:								
		DFS(x-1)							
		print(x, end=' ')							


n = int(input())									
DFS(n)

# 입력 : 3
# 출력 : 1 2 3

아래 그림은 위의 코드 좌측에 각 라인의 순서를 숫자로 붙인 것이다.

하단의 메모리 관련 그림에서 Line에 관해서 확인 시 참고할 것

※ n = 3부터 시작이기 때문에 DFS(3) → DFS(2) → DFS(1) 의 순서로 진행되지만, 출력은 1 → 2 → 3 의 순서로 되는 이유에 대해 잘 이해할 것!!

편의상 DFS를 줄여서 D라고 사용.

• 아래 그림과 같이, DFS(3) 실행 시, D(3) → D(2) → D(1) → D(0)의 순서로 함수가 호출되면서 각각의 스택프레임에 관련 정보가 저장되며, 호출 순서대로 메모리 공간에 저장됨.
  • 스택프레임 관련 참고 사이트
    - https://welcome-young.tistory.com/61
    - https://dojang.io/mod/page/view.php?id=2341
    
    
• D(0) 호출 시, 함수 본문의 if x>0의 조건을 만족시키지 않으므로 그대로 함수가 종료되고, 메모리 할당이 삭제됨.
  • 스택프레임 내에 저장해두었던 복귀주소로 돌아가게 됨.

• 메모리 할당 해제 시, 마지막에 저장되었던 스택프레임부터 확인하여 복귀주소로 돌아가게 되며 작업을 종료 후 해당 스텍프레임은 메모리 공간에서 제거됨.

  • 아래 그림에서 보면, 복귀 주소는 함수식의 3번째 줄에 해당됨.
  • 그 주소가 가리키는 D(0)으로 돌아오게 됨.
  • D(0)에 대한 스택프레임은 삭제되며 함수식의 4번째 줄에 있는 print(1)을 실행하여 1이 먼저 출력됨.
    

• 그 다음 저장되어 있던 스택프레임을 확인하여 위의 과정을 계속하여 반복하여 2가 출력되고 3이 출력되는 것임.
  
  

• 최종적으로 마지막 스택프레임까지 모두 메모리에서 제거된 후 실행이 종료됨.
  
  

※ 참고!

• 만약 아래와 같이, 함수 본문에서 print문이 재귀 호출 구문의 위에 위치하는 경우에는 첫 번째 숫자부터 1 → 2 → 3의 순서로 출력됨.

Code

def DFS(x):									
	if x>0:							
		print(x, end=' ')								
		DFS(x-1)							


n = int(input())									
DFS(n)

# 입력 : 3
# 출력 : 3 2 1