Recursion vs iteration: when to use each, and what causes a stack overflow?

Two versions

def fact_rec(n):            # base case + recursive case
    return 1 if n <= 1 else n * fact_rec(n - 1)

def fact_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

What recursion does on the call stack. Each call pushes a stack frame holding its parameters, local variables and return address. fact_rec(5) builds the frames 5 → 4 → 3 → 2 → 1. Then they unwind, multiplying on the way back. The extra space is O(n).

If the recursion is too deep, or has no reachable base case, the stack runs out:

• C/C++: a crash (segmentation fault), with a typical default stack of a few MB.
• Java: StackOverflowError.
• Python: RecursionError. CPython's default limit is around 1000 frames, adjustable with sys.setrecursionlimit, which is risky.

Comparison

When recursion is the better choice: problems whose structure is recursive. Tree and graph traversal (DFS), divide and conquer (merge sort, quicksort, binary search), backtracking (permutations, N-Queens, sudoku) and parsing nested expressions. The iterative versions need an explicit stack and are harder to read.

Making recursion safe and fast

• Memoisation turns exponential recursion, such as naive Fibonacci with O(2ⁿ) calls, into O(n). That is the top-down form of dynamic programming.
• Tail recursion: when the recursive call is the very last action, some compilers reuse the frame (tail-call optimisation). Scheme guarantees it. C/C++ compilers often do it at higher optimisation levels. Java and CPython do not, so deep tail recursion still overflows there.
• Any recursion can be converted into iteration with an explicit stack data structure.