What Is Recursion? Explained Simply with Examples

Quick Answer

Recursion is when a function solves a problem by calling itself on a smaller piece of that same problem. Every recursive function needs a base case that stops the calls and a recursive case that moves toward it. Python tracks each call on the call stack, so once the base case is reached, the results unwind back up. It shines for naturally nested problems, but too many calls can cause a stack overflow.

What Is Recursion?

What is recursion? It is a way of solving a problem where a function calls itself. Instead of writing a loop, you describe the answer in terms of a smaller version of the same problem, and let the function repeat until the problem becomes trivially small.

Here is the everyday version. Imagine you are standing in a long queue and want to know your position, but you can only ask the person in front of you. You ask, "What number are you?" That person does not know either, so they ask the person in front of them, and so on. Eventually the question reaches the person at the very front, who says "I am number 1." Now the answer flows back: the next person adds 1 and says "2," the next says "3," and it travels all the way back to you.

That is recursion. Each person does one small step (add 1) and passes the hard part to the person ahead. The person at the front is special because they can answer without asking anyone. In code, that special stopping point is called the base case, and it is what keeps recursion from running forever.

The Two Parts: Base Case and Recursive Case

Every correct recursive function has exactly two kinds of logic. Get these two right and the rest follows.

• Base case — the simplest input, where you already know the answer and do not call the function again. This is your stop sign.
• Recursive case — every other input, where the function calls itself on a smaller input and builds the answer from that result.

The golden rule: the recursive case must always move toward the base case. If it does not shrink the problem each time, the calls never stop, and Python eventually crashes. Think of it like walking down a staircase. The base case is the ground floor. Every step must go down, never sideways, or you will never arrive.

Before you write any recursion, ask yourself two questions: "What is the smallest input I can answer instantly?" and "How do I make the input smaller on each call?" If you can answer both, you can write the function.

Example 1: Factorial in Python

Factorial is the classic first example. The factorial of a number n (written n!) is every whole number from n down to 1 multiplied together. So 5! = 5 × 4 × 3 × 2 × 1 = 120.

Notice the pattern: 5! is just 5 × 4!, and 4! is 4 × 3!, and so on. Each factorial is defined in terms of a smaller factorial. That is a perfect fit for recursion. The base case is 0! = 1 (by definition).

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

print(factorial(5))   # 120

Read it out loud: "If n is 0, the answer is 1. Otherwise, the answer is n times the factorial of n - 1." The input gets smaller on every call (n - 1), so it always marches toward the base case of 0. That is why it stops instead of looping forever.

Example 2: Sum of a List

Recursion is not only for numbers. Here is how to add up all the numbers in a list. The idea: the sum of a list is the first item plus the sum of everything that is left.

def sum_list(numbers):
    if not numbers:            # base case: empty list
        return 0
    return numbers[0] + sum_list(numbers[1:])   # recursive case

print(sum_list([2, 4, 6, 8]))   # 20

The base case is the empty list, whose sum is 0. In the recursive case, numbers[0] is the first element and numbers[1:] is a slice with everything except the first element, so the list shrinks by one item on each call. Eventually it becomes empty, the base case fires, and the additions unwind: 2 + (4 + (6 + (8 + 0))), which is 20.

See the shared shape? Both examples do one small piece of work, then hand a smaller version of the problem to another call. That shape is the heart of every recursive solution.

How the Call Stack Works

To understand why recursion returns the right answer, you need to know about the call stack. Every time a function is called, Python sets aside a small block of memory (a "stack frame") to remember where it was and what its variables are. When the function returns, that block is thrown away and Python continues where it left off.

With recursion, these blocks pile up. Let us trace factorial(3). The calls stack up on the way down:

factorial(3)  ->  3 * factorial(2)   (waiting)
factorial(2)  ->  2 * factorial(1)   (waiting)
factorial(1)  ->  1 * factorial(0)   (waiting)
factorial(0)  ->  returns 1          (base case!)

Each call is paused, waiting for the one below it to finish. When the base case returns 1, the answers unwind back up the stack:

factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6

A stack is "last in, first out": the most recent call finishes first, just like plates you stack and then remove from the top. This down-then-up motion is the mental model to keep. If you can picture the calls stacking and unwinding, recursion stops feeling like magic.

Recursion vs Iteration: When Each Wins

Anything you can do with recursion, you can also do with a loop (iteration), and vice versa. Factorial with a loop is perfectly fine and actually a bit faster:

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result = result * i
    return result

So when should you reach for recursion? Use it when the problem itself is nested or branching, because then the recursive code reads almost like the definition of the problem.

Rule of thumb: if a loop is obvious and the data is deep or huge, use a loop. If the problem is naturally made of smaller copies of itself, recursion will usually be shorter and clearer.

The Risk: Stack Overflow

Recursion has one big trap. Every pending call takes up a stack frame, and that memory is limited. If the calls go too deep, or the base case is never reached, Python stops you with a RecursionError. In many other languages the same problem is called a stack overflow (yes, that is where the website got its name).

Python sets a safety limit on how deep the stack can get, often around 1000 calls:

import sys
print(sys.getrecursionlimit())   # e.g. 1000

def countdown(n):
    print(n)
    countdown(n - 1)   # oops, no base case!

countdown(5)   # runs past 0 forever, then RecursionError

This function forgets to stop. It happily counts 5, 4, 3, 2, 1, 0, -1, -2 and keeps going until the stack limit is hit and Python raises RecursionError: maximum recursion depth exceeded. Two habits prevent almost every case:

• Always write the base case first, before the recursive call, so you never forget it.
• Make sure the input actually shrinks toward the base case on every call.

If a problem genuinely needs tens of thousands of levels of depth, that is a signal to switch to a loop instead. Do not just raise the recursion limit and hope.

Recommendation: How to Get Comfortable

Recursion clicks with practice, not with staring. Here is a practical order to learn it:

1. Re-type the factorial and sum-of-a-list examples above and run them yourself. Change the inputs and predict the output before you press run.
2. Add a print at the top of the function showing the current argument. Watching the values on the way down and the returns on the way up makes the call stack real.
3. Try small exercises: reverse a string, count down from n, or find the nth Fibonacci number. Each one is just a base case plus a smaller call.
4. Only then move to nested data, like adding up numbers inside lists of lists, where recursion truly beats loops.

My recommendation for beginners: learn recursion, but reach for a loop by default. Use recursion when it makes the code clearly match the problem, such as trees and nested structures. When you do use it, write the base case first, every single time.

Want a structured, free path with hands-on exercises? Work through our Python course, which builds up functions, the call stack, and recursion step by step so these ideas become second nature.

Frequently Asked Questions