Recursion vs Iteration: Linked List Speed & Stack Limit

#recursion #iteration #linkedlist #codinginterview

Why This Matters in Real Interviews

Linked list problems show up in every FAANG interview rotation, and here's the awkward truth: most candidates default to recursion because it looks elegant. Then they hit a 10,000-node list and stack overflow. I've seen this happen during mock interviews more times than I can count.

The choice between recursion and iteration isn't just about style — it's about understanding the machine-level trade-offs between call stack depth and explicit loop control. Let's walk through what actually happens when you run both approaches on the same problem, with real memory profiles and timing data.

The Problem: Reversing a Singly Linked List

This is the canonical case where both approaches feel natural. Given a list 1 -> 2 -> 3 -> 4 -> None, return 4 -> 3 -> 2 -> 1 -> None.

Here's the recursive solution most people write first:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_recursive(head):
    # Base case: empty list or single node
    if not head or not head.next:
        return head

    # Recursive case: reverse the rest, then fix pointers
    new_head = reverse_recursive(head.next)
    head.next.next = head  # Make next node point back
    head.next = None       # Break forward link
    return new_head