[김태원 알고리즘] 재귀함수와 스택🌟

재귀함수란 자기가 자기 자신을 반복하여 호출하는 함수이다.
이러한 특성을 이용해 “반복문”의 효과를 낼 수 있다.
(알고리즘 문제 풀이에서 재귀함수는 반복문의 대체제로 볼 수 있다!)

아래 두 예제 비교해보자

예제 1

def DFS(x):
    if x > 0:
        print(x, end = ' ') # ✅ 3 2 1 출력
        DFS(x-1)

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

예제 2

def DFS(x):
    if x > 0:
        DFS(x-1)
        print(x, end = ' ') # ✅ 1 2 3 출력

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

출력문의 위치에 따라 결과가 달라진다.
예제1에서는 재귀 호출 이전에 출력문을 위치시킴으로써 3 2 1을 출력했다.
하지만 예제2에서는 재귀 호출 이후에 출력문을 위치시킴으로써 1 2 3을 출력했다.

예제2처럼 재귀 호출 이후에 출력문을 작성하면 왜 거꾸로 출력되는 것일까?
그 이유는 재귀함수가 🌟’스택’ 자료구조를 활용하기 때문이다!

🌟🌟 알아두기!

• 함수가 종료되어야지만 스택에서 소멸되는 것이다.
  • 함수가 종료되기 전에는 스택에 남아있는 것이다!
  • 함수가 종료되면 stack frame이 소멸되는 것이고, 소멸”될” stack frame에 적힌 복귀주소로 이동하여 그 이후부터 실행한다.
• 항상 스택의 top은 실행되고 있는 함수(stack frame)를 가리킨다고 생각하자.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기