[Python] 재귀 알고리즘

ungnam·2025년 2월 17일

재귀 알고리즘의 분석

def recur(n: int) -> int:
  if n > 0:
    recur(n - 1)
    print(n)
    recur(n - 2)

하향식(top-down)

가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 계단식으로 자세히 조사해 나가는 분석 방법

상향식(bottom-up)

아래쪽부터 쌓아 올리며 분석하는 방법

recur(1) -> 1
1. recur(0)을 실행한다.
2. 1을 출력한다.
3. recur(-1)을 실행한다.

recur(2) -> 1 2
1. recur(1)을 실행한다. -> 1
2. 2를 출력한다.
3. recur(0)을 실행한다.

recur(3) -> 1 2 3 1
1. recur(2)을 실행한다. -> 1 2
2. 3을 출력한다.
3. recur(1)을 실행한다. -> 1

recur(4) -> 1 2 3 1 4 1 2
1. recur(3)을 실행한다. -> 1 2 3 1
2. 4을 출력한다.
3. recur(2)을 실행한다. -> 1 2

재귀 알고리즘의 비재귀적 표현

꼬리 재귀 제거

위 코드의 recur(n - 2)의 의미는 결국

n의 값을 n - 2로 업데이트하고 함수의 시작 지점으로 돌아간다.

와 같다.
따라서 이를 아래 코드와 같이 구현할 수 있다.

def recur(n: int) -> int:
  while n > 0:
    recur(n - 1)
    print(n)
    n = n - 2

재귀 제거

하지만 recur(n - 1)의 경우, 예를 들어 n = 4일 때 recur(3)이 끝날 때까지 4를 기억하고 있어야 한다. 즉, 한 번 호출된 값이 바로 사라지면 안 되기 때문에 단순히 제거할 수 없다.

이 문제는 스택을 사용하면 쉽게 해결할 수 있다. 스택을 이용하면, 먼저 호출된 값(4)을 저장해 두고, 이후 recur(3), recur(2) 등이 끝난 후 다시 꺼내어 처리할 수 있다.

from collections import deque

def recur(n: int) -> int:
  s = deque([], n)

  while True:
    if n > 0:
      s.append(n)
      n = n - 1
      continue
    if len(s):
      n = s.pop()
      print(n)
      n = n - 2
      continue
    break

✅ 1️⃣ if n > 0: 부분 분석
🔹 n이 양수일 때(n > 0), 재귀처럼 스택에 n을 저장하고 n = n - 1로 감소시킵니다.
🔹 이는 recur(n-1)을 수행하는 것과 동일한 동작이다.

`n` 값	동작	스택(`s`) 상태
`4`	`4`을 스택에 push	`[4]`
`3`	`3`을 스택에 push	`[4, 3]`
`2`	`2`을 스택에 push	`[4, 3, 2]`
`1`	`1`을 스택에 push	`[4, 3, 2, 1]`
`0`	`if len(s):`로 이동	`[4, 3, 2, 1]`

📌 결과적으로 s = [4, 3, 2, 1]이 쌓임
➡ 마치 재귀 호출(recur(n-1))이 계속된 것과 같은 상태

✅ 2️⃣ if len(s): 부분 분석
🔹 n == 0이 되면, if len(s):가 실행되면서 스택에서 pop 수행
🔹 n = s.pop()으로 가장 나중에 push된 n 값을 다시 가져옴
🔹 print(n)을 실행하여 현재 n 값을 출력
🔹 n = n - 2를 수행하여 n을 두 단계 감소시킨 후 다시 반복

`n` 값 (pop)	스택(`s`) 상태	출력 (`print(n)`)	`n = n - 2`
`1`	`[4, 3, 2]`	`1` 출력	`n = -1`
`2`	`[4, 3]`	`2` 출력	`n = 0`
`3`	`[4]`	`3` 출력	`n = 1`
`1`	(pop 실행)	`1` 출력	`n = -1`
`4`	`[]` (마지막 pop)	`4` 출력	`n = 2`