Recursion Fundamentals (Calls and the Call Stack)

Recursion solves a problem by reducing it to smaller instances of itself until a base case stops the chain—each call gets its own stack frame with locals.

Why this shows up in the real world

Filesystem walks, AST traversals, and functional decomposition mirror recursion naturally.

Core idea (explained for students)

Ensure each recursive step moves toward base (smaller n, shorter list, tighter bounds). Tail recursion is not optimized in Python—use loops or explicit stacks for deep linear recursions.

Try this in Python

def fact(n: int) -> int:
    return 1 if n <= 1 else n * fact(n - 1)


print(fact(5))

Common mistakes

• Missing base case → maximum recursion depth exceeded.
• Accidentally quadratic work when each level scans whole array.

Key takeaways

• Convert linear-depth recursion >1000 to iterative or sys.setrecursionlimit only as hack.
• Write recurrence relation T(n)=... on paper.