Recursion in Python: Functions That Call Themselves

The big idea

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. It sounds strange at first — how can something be defined in terms of itself? — but it mirrors how we think about many real tasks.

Picture a stack of boxes. To find a key hidden somewhere in the pile, you open the top box. If the key is there, great. If not, you face a smaller pile and repeat the exact same process. That repeated, shrinking process is recursion.

This lesson assumes you already understand functions that return values. If "return" is fuzzy, review that first, because recursion depends on it completely.

The two ingredients

Every correct recursive function has exactly two parts:

1. Base case — the simplest situation you can answer immediately, with no further calls. It stops the recursion.
2. Recursive case — where the function calls itself on a smaller input, getting closer to the base case each time.

Miss the base case and the function calls itself forever, producing a RecursionError.

A gentle first example: countdown

def countdown(n):
    if n == 0:               # base case
        print("Blast off!")
    else:                    # recursive case
        print(n)
        countdown(n - 1)     # call self on a smaller number

countdown(3)

Output:

3
2
1
Blast off!

Line by line:

• if n == 0: is the base case. When n reaches 0, we print "Blast off!" and do not call again. The chain stops.
• Otherwise we print n, then call countdown(n - 1). Each call uses a number one smaller, so we march toward 0.

Trace it: countdown(3) prints 3 then calls countdown(2), which prints 2 then calls countdown(1), which prints 1 then calls countdown(0), which hits the base case.

Worked example: factorial

The factorial of a number n (written n!) is n × (n-1) × (n-2) × ... × 1. For example 4! = 4 × 3 × 2 × 1 = 24. Mathematicians define it recursively:

• 0! = 1 (base case)
• n! = n × (n-1)! (recursive case)

That definition translates straight into code:

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

print(factorial(4))   # 24

Let's trace factorial(4) carefully. Each call waits for the one below it to return:

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 returns directly

Now the answers travel back up:

factorial(1) = 1 * 1   = 1
factorial(2) = 2 * 1   = 2
factorial(3) = 3 * 2   = 6
factorial(4) = 4 * 6   = 24

This "go down to the base case, then come back up" pattern is the heart of recursion. The list of paused calls waiting to finish is called the call stack.

Recursion vs loops

The same factorial can be written with a loop:

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

print(factorial_loop(4))   # 24

Both are correct. So when do you reach for recursion?

• Use a loop for straightforward repetition like counting or summing a list — it is usually simpler and uses less memory.
• Use recursion when the problem naturally splits into smaller copies of itself: navigating nested folders, walking a family tree, or processing nested lists. You will meet these structures in Python nested lists and dictionaries.

A practical recursive example: summing a nested list

def deep_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):    # a smaller list inside
            total += deep_sum(item)   # recurse into it
        else:
            total += item
    return total

print(deep_sum([1, [2, 3], [4, [5, 6]]]))   # 21

Here the base case is hidden: when a list contains no more lists, the for loop finishes and we return the total without recursing further. Each nested list triggers a deeper call. A plain loop cannot easily handle unknown levels of nesting, which is exactly where recursion shines.

Common mistakes

• No base case, or a base case the recursion never reaches. Always ask: "Does my input definitely get smaller and hit the stopping point?"
• Forgetting to return the recursive call. n * factorial(n - 1) must be returned; otherwise the function gives back None.
• Going too deep. Python limits recursion to roughly 1000 calls. Very deep problems may need a loop instead.

Try it yourself

1. Write a recursive sum_to(n) that adds 1 + 2 + ... + n. Base case: sum_to(0) returns 0.
2. Write a recursive power(base, exp) that computes base ** exp using base * power(base, exp - 1), with base case power(base, 0) = 1.
3. Write a recursive function that counts how many times a letter appears in a string by checking the first character, then recursing on the rest.

When you finish, strengthen the looping alternative with Python for loops so you can choose the right tool for each job.