Recursion

Recursion is a function solving a problem by calling itself on a smaller version of the same problem, until it reaches a case simple enough to answer directly.

factorial(5)

Calls

    Call stack

    empty

    factorial(5) = 5 × factorial(4) … until factorial(1), which is simply 1.

    Step 1 / 12
    Stack depth
    0
    factorial(n):
      if n == 1: return 1
      return n × factorial(n − 1)
    factorial(n), n =

    What's happening?

    1. Every call that is not the base case waits for a smaller call — and each waiting call is a frame on the call stack.
    2. The base case answers without calling anything, and that is what stops the recursion.
    3. Then the frames come off the stack newest first, each finishing its own work with the answer from below.

    Complexity

    Time
    O(n) calls for factorial(n)
    Space
    O(n) stack frames

    Where you'll meet it

    Tree and graph traversal, file-system walks, parsers, divide-and-conquer algorithms like merge sort, and backtracking.

    Common mistake

    A missing or unreachable base case: the stack keeps growing until the program crashes with a stack overflow.

    FAQ

    What is a base case?

    The input small enough to answer directly, without another call. Every recursion needs one.

    Why does deep recursion cause a stack overflow?

    Each waiting call keeps a frame on the call stack; too many frames exhaust the memory set aside for it.

    Is recursion slower than a loop?

    Often slightly, because of the extra frames — but for trees and graphs it is usually far clearer.