Algorithms traced line by line until they click.

A recursive function calls itself on a smaller version of the same problem, until it hits a base case that stops the recursion.

function factorial(n):
    if n == 0: return 1        # base case
    return n * factorial(n-1)  # recursive case

Tracing factorial(4)

• factorial(4) = 4 × factorial(3)
• factorial(3) = 3 × factorial(2)
• factorial(2) = 2 × factorial(1)
• factorial(1) = 1 × factorial(0)
• factorial(0) = 1 ← base case hit, now it unwinds: 1×1×2×3×4 = 24

The two things every recursive function needs: a base case that stops it, and a recursive case that makes real progress toward that base case.