재귀함수와 스택(Stack)

재귀함수 : 자기자신을 호출하는 함수

이때 stack 이라는 자료 구조를 사용하여 작동한다.

 

재귀함수는 for문 즉 반복문의 대체자이다. 

 

n 입력값을 3으로 가정하고 설명을 해보겠습니다. 

12 줄: 입력값 n 즉, 3 을 받음.

13 줄:  DFS(3): DFS함수를 호출하여  3을 넘김.

4 줄: 함수 DFS (3) if 문 실행

5 줄: 만약 x 가 0보다 크다면 실행. 0이거나 작으면 종료

6 줄: x 출력 -> 3이 출력됨.

7줄 ; DFS 함수 호출 [이 부분이 재귀함수이다. 왜냐하면 자기자신의 함수를 호출하기 떄문에 ]

DFS(3-1) 로 DFS(2)가 되며 함수 DFS를 호출함

 

다시 4번줄로 올라가서 def DFS(2): 가 되면서 

5번줄: if 2> 0 : 가 실행되고 참이므로 

6번줄: print(2) 로 인해서 2가 출력

7번줄: DFS(2-1) 이 됨.   DFS(1)로  자기 자신 함수인 DFS를 호출 [재귀함수]

 

이런 원리로 게속 반복되다가

 

n 이 0이 되면 종료됨. 

 

결과는 

---