Why use recursion instead of a normal loop?

Any recursive problem can be solved with a loop (iteration), but recursion is often used when it makes the code much cleaner and easier to read. It is especially useful for problems involving complex data structures like trees or graphs.

Does recursion use more memory than a loop?

Yes, generally. Because each recursive call adds a new layer to the call stack, recursion uses more memory to keep track of all the paused functions, whereas a simple loop just updates a few variables.

What is infinite recursion?

Infinite recursion happens when a recursive function never reaches its base case. It keeps calling itself over and over until the program crashes from a stack overflow.

What is recursion, with a simple example?

Recursion happens when a computer function calls itself. Instead of writing a loop to repeat an action, a recursive function solves a problem by breaking it down into a smaller version of the same problem, asking itself to solve that smaller piece.

Think of it as looking up a word in a dictionary, only to find another word in the definition you do not know. You look up the new word, and if that definition also has an unknown word, you look that one up too. You keep doing this until you finally read a definition where you understand every word. Then, you can work your way back up to understand the very first word you looked up.

The Anatomy of a Recursive Function

Every valid recursive function must have two main parts: the base case and the recursive step. The recursive step is where the function actually calls itself with a slightly smaller or simpler input. This is what drives the process forward.

The base case is the stopping condition. It is a simple version of the problem that can be answered immediately without needing another function call. Without a base case, your function would keep calling itself forever.

Why Recursion Works

Recursion works because the computer uses a structure called the 'call stack' to keep track of all the active function calls. Each time the function calls itself, the computer pauses the current function and adds the new one to the top of the stack.

Once the base case is reached, that function finishes and returns its answer. The computer then goes back to the previous function, uses that answer, and finishes it. This process ripples all the way back down the stack until the very first function call gets the final answer.

Where Students Slip Up

The most common mistake when writing a recursive function is forgetting the base case, or writing a base case that the recursive step never actually reaches.

When this happens, the function calls itself endlessly. The call stack fills up with paused functions until the computer runs out of memory allocated for this task. This triggers an error you might have heard of: a 'stack overflow'.

Worked through

Write a recursive function to find the factorial of a number $n$ , written as $n!$ . The factorial of an integer is the product of that number and all positive integers below it (e.g., $4! = 4 imes 3 imes 2 imes 1$ ).

Let us define our function $factorial(n)$ .

First, we need our base case. The simplest factorial is $1! = 1$ (or $0! = 1$ ). So, if $n = 1$ , we simply return $1$ .

Next, we need our recursive step. Notice that $4!$ is the same as $4 imes 3!$ . In general, $n! = n imes (n-1)!$ . So, our function will return $n imes factorial(n - 1)$ .

If we call $factorial(3)$ :

$n=3$ , which is not 1. We return $3 imes factorial(2)$ .
For $factorial(2)$ , $n=2$ , not 1. We return $2 imes factorial(1)$ .
For $factorial(1)$ , $n=1$ . This is our base case! We return $1$ .
The previous step resolves: $2 imes 1 = 2$ .
The first step resolves: $3 imes 2 = 6$ .

The final answer is $6$ .

Questions students ask

Ask about this topic

Explain at

Where this comes from: Introduction to Algorithms, Third Edition (Cormen, Leiserson, Rivest, Stein) · Khan Academy: Computer Science - Recursion · OpenStax: Introduction to Python Programming