재귀와 재귀 트리 방법
재귀 호출을 트리로 추적하고, 마스터 정리를 적용하며, 병합 정렬·팩토리얼·피보나치 변형의 시간 복잡도를 도출합니다.
재귀와 재귀 트리 방법은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
재귀와 호출 스택
함수가 자기 자신을 호출하면 호출할 때마다 스택 프레임이 추가되고, 기본 조건에 도달할 때까지 쌓인 다음 역순으로 해제됩니다. 이 과정을 머릿속으로 그려 보는 것이 재귀 분석의 첫 단계입니다.
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive call
# Call chain: factorial(4)
# 4 * factorial(3)
# 3 * factorial(2)
# 2 * factorial(1)
# 1 * factorial(0) -> 1
# Unwinds: 1, 2, 6, 24
print(factorial(5)) # 120피보나치 재귀 트리
재귀 트리는 각 호출을 하위 호출로 확장해 보여 줍니다. 단순한 피보나치는 매번 두 갈래로 나뉘므로 약 2^n개의 노드가 있는 트리가 만들어집니다. 따라서 O(2^n)입니다. 코드를 확인해 보세요.
call_count = [0]
def fib_naive(n):
call_count[0] += 1
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
for n in [5, 10, 15, 20]:
call_count[0] = 0
result = fib_naive(n)
print(f'fib({n})={result}, calls={call_count[0]}')
# Calls roughly double each time n increases by 1반복되는 하위 문제 식별
이 트리에서는 fib(3) 같은 동일한 호출이 여러 가지에서 반복됩니다. 이러한 겹치는 하위 문제는 메모이제이션을 적용해야 한다는 신호이며, 메모이제이션을 사용하면 O(2^n)을 O(n)으로 줄일 수 있습니다.
# Memoised: each unique sub-problem computed once
def fib_memo(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
call_count2 = [0]
def fib_counted(n, memo={}):
call_count2[0] += 1
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_counted(n-1, memo) + fib_counted(n-2, memo)
return memo[n]
fib_counted(20)
print(f'calls with memo: {call_count2[0]}') # only 21병합 정렬 재귀 트리
병합 정렬의 트리는 log n개의 레벨로 이루어지고, 각 레벨에서는 전체적으로 O(n)의 작업을 수행합니다. 모든 요소를 한 번씩 다루기 때문입니다. 두 값을 곱하면 O(n log n)이 됩니다. 코드를 확인해 보세요.
# Merge sort: at each level, n total elements are merged
# Level 0: 1 merge of n elements -> n work
# Level 1: 2 merges of n/2 each -> n work
# Level 2: 4 merges of n/4 each -> n work
# ...log(n) levels...
# Total: n * log(n)
# Verify with operation counter:
def merge_sort_counted(arr):
ops = [0]
def _sort(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r = _sort(a[:m]), _sort(a[m:])
result, i, j = [], 0, 0
while i < len(l) and j < len(r):
ops[0] += 1
if l[i] <= r[j]: result.append(l[i]); i+=1
else: result.append(r[j]); j+=1
return result + l[i:] + r[j:]
return _sort(arr), ops[0]
_, c = merge_sort_counted(list(range(64, 0, -1)))
print(f'Merge ops: {c}') # ~384 ~ 64*log2(64)=384마스터 정리
마스터 정리는 T(n) = a*T(n/b) + O(n^d)를 세 가지 경우로 풉니다. 병합 정렬(a=2, b=2, d=1)에 적용하면 O(n log n)이 나옵니다. 시험을 위해 세 가지 경우를 외워 두세요.
# Merge sort: T(n) = 2*T(n/2) + O(n)
# a=2, b=2, d=1, log_b(a)=log2(2)=1=d => O(n log n)
# Binary search: T(n) = 1*T(n/2) + O(1)
# a=1, b=2, d=0, log2(1)=0=d => O(log n)
# Strassen matrix mult: T(n) = 7*T(n/2) + O(n^2)
# a=7, b=2, d=2, log2(7)~2.81 > 2 => O(n^log2(7)) ~ O(n^2.81)
import math
print('log2(7) =', math.log2(7)) # 2.807...재귀 트리 그리기: 단계별로 보기
재귀 트리를 그리는 방법은 다음과 같습니다. 맨 위에 T(n)을 놓고, 각 호출을 확장한 다음, 각 레벨의 작업량을 더하고, 마지막으로 레벨 수를 곱합니다. 자동으로 할 수 있을 때까지 연습하세요.
# Factorial: T(n) = T(n-1) + O(1)
# Tree is a chain: n levels, O(1) each -> O(n)
# Fibonacci: T(n) = T(n-1) + T(n-2) + O(1)
# Binary tree of depth n, ~2^n nodes -> O(2^n)
# Merge sort: T(n) = 2*T(n/2) + O(n)
# Log levels, n work each -> O(n log n)
def count_recursive_calls(n, results=[]):
if n <= 1:
results.append(n)
return n
return count_recursive_calls(n-1, results) + count_recursive_calls(n-2, results)
results = []
count_recursive_calls(8, results)
print(f'fib(8) leaf calls: {len(results)}')지수 시간 재귀: 부분집합
모든 subsets를 생성하는 데는 O(2^n)이 걸립니다. 부분집합이 정확히 2^n개이므로 이보다 더 줄일 수 없습니다. 각 요소를 포함하거나 제외하면서 선택의 이진 트리를 만듭니다. 코드를 확인해 보세요.
def subsets(nums):
result = []
def backtrack(start, current):
result.append(list(current)) # O(n) copy
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
nums = [1, 2, 3]
ss = subsets(nums)
print(len(ss)) # 8 = 2^3
print(ss)꼬리 재귀와 최적화
꼬리 재귀란 재귀 호출이 마지막 단계인 경우를 말합니다. 일부 언어는 이때 프레임을 재사용하지만, 파이썬은 그렇지 않습니다. 따라서 깊은 재귀는 여전히 오버플로를 일으킵니다. 대신 반복문을 사용하세요.
# Tail-recursive factorial (accumulator pattern)
def fact_tail(n, acc=1):
if n == 0:
return acc
return fact_tail(n - 1, n * acc) # tail call
# Python does NOT TCO, so this overflows for large n
# Instead, convert to iterative:
def fact_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(fact_tail(10)) # 3628800
print(fact_iter(10)) # 3628800재귀의 공간 복잡도
재귀 호출마다 프레임을 유지하므로 재귀의 공간 비용은 깊이에 비례합니다. 선형 재귀는 O(n)이고, 균형 잡힌 트리 DFS는 O(log n)입니다. 너무 깊이 들어가면 RecursionError가 발생합니다.
import sys
print(sys.getrecursionlimit()) # default 1000
# Increase limit for deep problems
sys.setrecursionlimit(10000)
# Track max depth manually
def max_depth_tracker(n, depth=0, max_seen=[0]):
max_seen[0] = max(max_seen[0], depth)
if n <= 0:
return
max_depth_tracker(n - 1, depth + 1, max_seen)
return max_seen[0]
print(max_depth_tracker(50)) # 50 => O(n) stack frames퀵 정렬 재귀 트리
퀵 정렬은 피벗을 잘 선택하면 O(n log n)이지만, 정렬된 입력에서 피벗을 잘못 선택하면 O(n^2)으로 악화됩니다. 그래서 피벗을 무작위로 선택하는 것이 중요합니다. 코드를 확인해 보세요.
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # randomised -> O(n log n) expected
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
print(quick_sort([3, 6, 8, 10, 1, 2, 1])) # sorted거듭제곱 함수: log n 재귀
단순한 x^n 계산은 O(n)번 곱셈이 필요하지만, 제곱을 사용하면 각 단계에서 작업량이 절반으로 줄어듭니다. 즉 x^n = (x^(n/2))^2입니다. 따라서 깔끔한 O(log n)이 됩니다. 절반으로 줄이는 방식이 실제로 어떻게 작동하는지 보여 줍니다. 코드를 확인해 보세요.
def fast_pow(x, n):
if n == 0: return 1
if n < 0: return 1 / fast_pow(x, -n)
if n % 2 == 0:
half = fast_pow(x, n // 2)
return half * half # O(log n) calls
return x * fast_pow(x, n - 1)
print(fast_pow(2, 10)) # 1024
print(fast_pow(3, 5)) # 243
# Only log2(10)=3-4 recursive calls for n=10빠른 확인
빠르게 확인해 보겠습니다. 재귀 트리 방법으로 무엇을 배웠는지 보여 주세요. 한 문제이니 천천히 풀어 보세요. 🌳
학습 내용 복습
복습해 보겠습니다. 재귀 트리는 전체 작업량을 드러내고, 마스터 정리는 분할 정복 점화식을 풀며, 재귀에는 깊이에 비례하는 O(depth) 스택 공간이 필요합니다.
자주 묻는 질문
“재귀와 재귀 트리 방법” 강의는 무료인가요?
네 — “재귀와 재귀 트리 방법” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“재귀와 재귀 트리 방법”에서 뭘 배우나요?
재귀 호출을 트리로 추적하고, 마스터 정리를 적용하며, 병합 정렬·팩토리얼·피보나치 변형의 시간 복잡도를 도출합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“재귀와 재귀 트리 방법” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- Big-O 표기법 기초
- 반복문과 중첩 반복문 분석
- 재귀와 재귀 트리 방법
- 공간 복잡도와 트레이드오프