재귀와 반복의 트레이드오프

재귀와 반복의 이중성

팩토리얼: 재귀형과 반복형 비교

def factorial_rec(n):
    if n == 0:
        return 1
    return n * factorial_rec(n - 1)   # O(n) stack

def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i                    # O(1) stack
    return result

print(factorial_rec(10))   # 3628800
print(factorial_iter(10))  # 3628800

# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0)  # True (Python handles big ints)

피보나치: 지수 시간과 선형 시간

import time

def fib_rec(n):
    if n <= 1: return n
    return fib_rec(n-1) + fib_rec(n-2)   # O(2^n)

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a                              # O(n) time, O(1) space

# Timing comparison for n=35
start = time.time()
fib_rec(35)
print(f'Recursive n=35: {time.time()-start:.3f}s')

start = time.time()
fib_iter(35)
print(f'Iterative n=35: {time.time()-start:.6f}s')

print(fib_iter(100))  # handles large n

트리 순회: 재귀 방식과 반복 방식

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val   = val; self.left = left; self.right = right

def preorder_rec(root, result=None):
    if result is None: result = []
    if root:
        result.append(root.val)
        preorder_rec(root.left, result)
        preorder_rec(root.right, result)
    return result

def preorder_iter(root):
    if not root: return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right: stack.append(node.right)
        if node.left:  stack.append(node.left)
    return result

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_rec(root))   # [1, 2, 4, 5, 3]
print(preorder_iter(root))  # [1, 2, 4, 5, 3]

병합 정렬: 재귀 방식과 반복 방식(상향식)

def merge_sort_iterative(arr):
    n = len(arr)
    size = 1
    while size < n:
        for start in range(0, n, 2 * size):
            mid   = min(start + size, n)
            end   = min(start + 2 * size, n)
            left  = arr[start:mid]
            right = arr[mid:end]
            # Merge
            i = j = 0
            for k in range(start, end):
                if i < len(left) and (j >= len(right) or left[i] <= right[j]):
                    arr[k] = left[i]; i += 1
                else:
                    arr[k] = right[j]; j += 1
        size *= 2
    return arr

print(merge_sort_iterative([5, 2, 4, 6, 1, 3]))  # [1,2,3,4,5,6]

재귀 방식이 확실히 더 나은 경우

# Recursion is clearest for JSON-like nested structures
def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))  # recurse on sub-list
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4], 5], 6]))  # [1, 2, 3, 4, 5, 6]
print(flatten([]))                        # []
print(flatten([[1, [2]], [3, [4, [5]]]])) # [1, 2, 3, 4, 5]

반복 방식이 확실히 더 나은 경우

# Iterative is clearest for sequential array processing
def running_max(nums):
    result = []
    curr_max = float('-inf')
    for n in nums:
        curr_max = max(curr_max, n)
        result.append(curr_max)
    return result

print(running_max([3, 1, 4, 1, 5, 9, 2, 6]))  # [3,3,4,4,5,9,9,9]

# No natural recursion here — iteration is the only sensible choice

DFS 재귀를 반복 방식으로 변환하기

# Post-order iterative using two stacks
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val=val; self.left=left; self.right=right

def postorder_iter(root):
    if not root: return []
    s1, s2 = [root], []
    while s1:
        node = s1.pop()
        s2.append(node.val)
        if node.left:  s1.append(node.left)
        if node.right: s1.append(node.right)
    return s2[::-1]  # reverse gives post-order

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(postorder_iter(root))  # [4, 5, 2, 3, 1]

재귀의 성능 오버헤드

import time

def rec_sum(n):
    if n == 0: return 0
    return n + rec_sum(n - 1)

def iter_sum(n):
    total = 0
    for i in range(n + 1):
        total += i
    return total

import sys; sys.setrecursionlimit(10000)

n = 5000
start = time.time()
for _ in range(100): rec_sum(n)
print(f'Recursive sum({n}) x100: {(time.time()-start)*1000:.2f}ms')

start = time.time()
for _ in range(100): iter_sum(n)
print(f'Iterative sum({n}) x100: {(time.time()-start)*1000:.2f}ms')

면접에서 선택하기

요약: 상충 관계 표

rows = [
    ('Factorial',   'O(n) / O(1)', 'O(n) / O(1)', 'Same time; iter wins on space'),
    ('Fibonacci',   'O(2^n) / O(n)', 'O(n) / O(1)', 'Iter massively wins'),
    ('Binary search','O(log n) / O(log n)', 'O(log n) / O(1)', 'Iter wins on space'),
    ('Tree DFS',    'O(n) / O(h)',  'O(n) / O(h)', 'Equal; rec cleaner'),
    ('Merge sort',  'O(n log n) / O(log n)', 'O(n log n) / O(1)', 'BU-iter wins on stack'),
]
for name, rec, it, note in rows:
    print(f'{name:<15} rec={rec:<22} iter={it:<22} {note}')

간단 확인

수업 복습