Coding Interview Prep · 강의

재귀와 재귀 트리 방법

재귀 호출을 트리로 추적하고, 마스터 정리를 적용하며, 병합 정렬·팩토리얼·피보나치 변형의 시간 복잡도를 도출합니다.

재귀와 재귀 트리 방법은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding 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로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“재귀와 재귀 트리 방법”에서 뭘 배우나요?

재귀 호출을 트리로 추적하고, 마스터 정리를 적용하며, 병합 정렬·팩토리얼·피보나치 변형의 시간 복잡도를 도출합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

“재귀와 재귀 트리 방법” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← Coding Interview Prep(으)로 돌아가기