การแลกเปลี่ยนระหว่างแบบเรียกซ้ำกับแบบวนซ้ำ

ความเป็นคู่กันของการเรียกซ้ำและการวนซ้ำ

factorial: แบบเรียกซ้ำเทียบกับแบบวนซ้ำ

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}')

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทบทวนบทเรียน