Recursion, and the stack underneath it

A recursive function calls itself on a smaller version of the same problem. It needs exactly two things, and leaving out either is the whole of what goes wrong.

def factorial(n):
    if n <= 1:          # base case: where it stops
        return 1
    return n * factorial(n - 1)   # moves TOWARD the base case

A base case, or it never stops. Progress toward it, or it never arrives.

What is really happening

Each call gets its own stack frame, holding its parameters and where to return to. factorial(4):

factorial(4)  waiting on factorial(3)
  factorial(3)  waiting on factorial(2)
    factorial(2)  waiting on factorial(1)
      factorial(1)  returns 1
    returns 2 × 1 = 2
  returns 3 × 2 = 6
returns 4 × 6 = 24

Four frames alive at once. That is why deep recursion crashes: the stack is finite, typically about a megabyte, and Python stops you at roughly 1,000 frames on purpose.

The trap that makes it exponential

def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

This is correct and unusable. fib(50) makes about twenty billion calls, because fib(30) is recomputed millions of times.

def fib(n, memo={}):
    if n <= 1: return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Remembering answers makes it O(n). This is memoisation, and it is the doorway to dynamic programming.

When recursion is the right tool

When the problem is genuinely built from smaller copies of itself: trees, directories, divide and conquer. factorial is a bad example precisely because a loop is clearer.