Recursion vs Iteration — Recursion Crashed JSON Parser

import sys
import time
from functools import lru_cache

# --- Naive recursion: O(2^n) time, O(n) space ---
# DO NOT use this in production for n > 35
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 ---
# This is what production code should use
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 ---
# Useful when you need recursive structure for clarity
# and can afford the O(n) cache memory
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# Timing comparison — run on your machine to feel the difference
def time_it(fn, n, label):
    start = time.perf_counter()
    result = fn(n)
    elapsed = time.perf_counter() - start
    print(f"{label:30s} fib({n}) = {result:>20} in {elapsed*1000:.3f}ms")

time_it(fib_iterative, 50, "Iterative")
time_it(fib_memo, 50,      "Memoized recursive")
# fib_recursive(50) would take several minutes — do not run it

# Python's recursion limit — check yours
print(f"\nRecursion limit: {sys.getrecursionlimit()} frames")

# fib_memo(990) works; fib_memo(1001) raises RecursionError
# because the memoized version still recurses to compute uncached values
try:
    fib_memo(995)
    print("fib_memo(995): OK")
except RecursionError:
    print("fib_memo(995): RecursionError — cache not warm")

# Iterative has no such limit
print(f"fib_iterative(10000): {fib_iterative(10000)} (truncated)"[:60] + '...')

from collections import deque

# --- Recursive DFS ---
# Clean, readable, mirrors the algorithm definition
# Dangerous on graphs with unknown depth or high node count
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()  # IMPORTANT: never use mutable default arg
    visited.add(node)
    print(node, end=' ')
    for neighbour in graph.get(node, []):
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited)
    return visited

# --- Iterative DFS ---
# Same traversal order, no stack overflow risk
# Uses heap memory (Python list) instead of the C call stack
def dfs_iterative(graph, start):
    visited = set()
    stack   = [start]  # explicit stack — append is push, pop is pop

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

# For contrast: BFS uses a deque instead of a list
def bfs_iterative(graph, start):
    visited = set([start])
    queue   = deque([start])  # FIFO — popleft instead of pop

    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbour in graph.get(node, []):
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return visited

# Test graph — directed, acyclic
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print('Recursive DFS: ', end=''); dfs_recursive(graph, 'A'); print()
print('Iterative DFS: ', end=''); dfs_iterative(graph, 'A'); print()
print('Iterative BFS: ', end=''); bfs_iterative(graph, 'A'); print()

# Demonstrate the depth advantage
# Simulate a chain graph 5000 nodes long — recursive would crash
chain = {i: [i + 1] for i in range(5000)}
chain[5000] = []
visited = dfs_iterative(chain, 0)
print(f"\nIterative DFS visited {len(visited)} nodes in 5000-node chain without stack overflow")

import sys

# --- Tail-recursive factorial ---
# The recursive call is the LAST operation — nothing pending after it
# accumulator carries the result forward so no computation needed after return
def factorial_tail(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)  # tail position — accumulator updated

# --- Non-tail-recursive factorial ---
# Multiplication happens AFTER the recursive call returns
# The stack frame must be retained to perform n * (result of recursive call)
def factorial_non_tail(n):
    if n <= 1:
        return 1
    return n * factorial_non_tail(n - 1)  # NOT tail position — n must be remembered

# --- Iterative factorial — what you should actually write ---
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Demonstrate that Python treats both recursive versions identically
# Both will fail at the same recursion depth
for fn_name, fn in [("tail", factorial_tail), ("non_tail", factorial_non_tail)]:
    sys.setrecursionlimit(200)  # low limit to make failure obvious
    try:
        result = fn(150)
        print(f"factorial_{fn_name}(150) = {str(result)[:20]}...")
    except RecursionError:
        print(f"factorial_{fn_name}(150) -> RecursionError at depth 150")

# Iterative has no such limit
sys.setrecursionlimit(1000)  # restore
print(f"factorial_iterative(150) = {str(factorial_iterative(150))[:20]}...")
print(f"factorial_iterative(10000): computed successfully, len={len(str(factorial_iterative(10000)))} digits")

# Show the tail-recursive -> iterative mechanical conversion
# Replace: return factorial_tail(n-1, n*acc) with loop variable reassignment
def factorial_tail_to_iterative(n):
    accumulator = 1
    while n > 1:          # was: if n <= 1: return accumulator
        accumulator = n * accumulator  # was: argument to recursive call
        n = n - 1         # was: first argument to recursive call
    return accumulator

print(f"\nTail-to-iterative conversion: factorial(20) = {factorial_tail_to_iterative(20)}")

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional

@dataclass
class TreeNode:
    val: int
    left:  Optional['TreeNode'] = None
    right: Optional['TreeNode'] = None

# --- Recursive inorder: left -> root -> right ---
# 3 lines, directly mirrors the definition
# Depth = tree height — O(log n) for balanced, O(n) for degenerate
def inorder_recursive(node: Optional[TreeNode]) -> list[int]:
    if node is None:
        return []
    return inorder_recursive(node.left) + [node.val] + inorder_recursive(node.right)

# --- Iterative inorder: same result, harder to read ---
# Required when tree height is unbounded or user-controlled
def inorder_iterative(root: Optional[TreeNode]) -> list[int]:
    result, stack, current = [], [], root
    while current or stack:
        # Go as far left as possible
        while current:
            stack.append(current)
            current = current.left
        # Process the leftmost unprocessed node
        current = stack.pop()
        result.append(current.val)
        # Move to right subtree
        current = current.right
    return result

# --- Recursive merge sort: clean divide-and-conquer ---
def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    mid   = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left: list[int], right: list[int]) -> list[int]:
    result = []
    i = j  = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

# Build a balanced BST for testing
#         4
#        / \
#       2   6
#      / \ / \
#     1  3 5  7
root = TreeNode(4,
    TreeNode(2, TreeNode(1), TreeNode(3)),
    TreeNode(6, TreeNode(5), TreeNode(7))
)

recursive_result = inorder_recursive(root)
iterative_result = inorder_iterative(root)
print(f"Recursive inorder: {recursive_result}")
print(f"Iterative inorder: {iterative_result}")
print(f"Results match: {recursive_result == iterative_result}")

# Merge sort demo
unsorted = [38, 27, 43, 3, 9, 82, 10]
print(f"\nMerge sort: {unsorted} -> {merge_sort(unsorted)}")

# Depth analysis: balanced tree with 1M nodes
import math
nodes = 1_000_000
balanced_depth = math.ceil(math.log2(nodes + 1))
print(f"\nBalanced tree with {nodes:,} nodes: max depth = {balanced_depth}")
print(f"Python's recursion limit: 1000 frames")
print(f"Safe for recursion? {'Yes' if balanced_depth < 900 else 'No'}")

// io.thecodeforge — dsa tutorial

public class StackBlowOut {
    // Recursive: crashes at around depth 17,000
    private static void recursiveCount(int depth) {
        if (depth == 0) return;
        recursiveCount(depth - 1);
    }
    
    // Iterative: never crashes, uses constant stack
    private static void iterativeCount(int limit) {
        int runner = 0;
        while (runner < limit) {
            // process...
            runner++;
        }
    }
    
    public static void main(String[] args) {
        try {
            recursiveCount(200000);
        } catch (StackOverflowError e) {
            System.out.println("Recursion died at 200k depth");
        }
        
        iterativeCount(200000);
        System.out.println("Iteration survived 200k iterations");
    }
}