What does "recursion" mean, with an example?

In programming, recursion is a technique where a function solves a problem by calling itself to solve smaller, more manageable versions of the same problem.

Think of it like a set of Russian nesting dolls. To get to the smallest doll in the center, you have to keep opening the current doll until you finally reach the one that cannot be opened anymore. That smallest, non-openable doll is the "base case"—the point where the process stops.

The Two Golden Rules of Recursion:

1. The Base Case: There must be a condition that stops the function from calling itself, otherwise it will run forever (causing a "stack overflow" error).
2. The Recursive Step: The function must call itself with a slightly smaller or simpler input, eventually moving toward the base case.

A Simple Example: Calculating a Factorial

A factorial (written as n!) is the product of all numbers from 1 to n.

• 5! = 5 * 4 * 3 * 2 * 1 = 120

Notice that 5! is actually 5 * 4!. And 4! is 4 * 3!, and so on. We can express this using recursion:

def factorial(n):
    # 1. Base Case: If n is 1, the answer is just 1. Stop here.
    if n == 1:
        return 1
    # 2. Recursive Step: Multiply n by the factorial of (n-1)
    else:
        return n * factorial(n - 1)

How the computer sees it:

If you call factorial(3):

1. Is 3 == 1? No. Return 3 * factorial(2).
2. Now the computer needs factorial(2). Is 2 == 1? No. Return 2 * factorial(1).
3. Now the computer needs factorial(1). Is 1 == 1? Yes! Return 1.
4. The chain reaction completes:
   • factorial(2) becomes 2 * 1 = 2
   • factorial(3) becomes 3 * 2 = 6
5. Final result: 6

Why use it?

It can make complex problems—like searching through folders on your computer, solving puzzles, or traversing data structures like trees—much cleaner and easier to write than using long, complicated loops. However, because each "call" takes up a bit of memory, it’s not always the most efficient choice for every task.