Recursion vs Iteration

import sys
import time

# Naive recursion — O(2^n) time, catastrophic
def fib_recursive(n):
    if n <= 1: return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

# Iterative — O(n) time, O(1) space
def fib_iterative(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Memoized recursion — O(n) time, O(n) space
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n - 1) + fib_memo(n - 2)

print(fib_iterative(50))   # 12586269025 — instant
print(fib_memo(50))        # 12586269025 — instant
# fib_recursive(50) would take minutes

# Python's recursion limit
print(sys.getrecursionlimit())  # 1000
# sys.setrecursionlimit(10000)  # raise if needed

# Recursive DFS — clean but limited by call stack depth
def dfs_recursive(graph, node, visited=None):
    if visited is None: visited = set()
    visited.add(node)
    print(node, end=' ')
    for neighbour in graph.get(node, []):
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited)

# Iterative DFS — same result, no stack overflow risk
def dfs_iterative(graph, start):
    visited = set()
    stack   = [start]  # explicit stack replaces call stack

    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        print(node, end=' ')
        # Push neighbours in reverse to match recursive order
        for neighbour in reversed(graph.get(node, [])):
            if neighbour not in visited:
                stack.append(neighbour)

graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []}
print('Recursive:', end=' '); dfs_recursive(graph, 'A'); print()
print('Iterative:', end=' '); dfs_iterative(graph, 'A'); print()