Recursion in Python

In the last lesson, we learned about the Scope of Variables. Now let’s see how a function can solve a problem by calling itself.

⚙️ Let’s Talk About a Function Calling Itself

We know how to write a function. We give it a name. We give it some code. And we call it when we need it.

But what if a function calls itself?

That sounds strange. Like a mirror facing another mirror. Infinite reflections. But in programming, it is actually a very powerful technique.

It is called recursion.

🧩 What Is Recursion in Python?

Recursion is when a function calls itself.

That is the whole idea. A function that solves a problem by calling itself on a smaller version of the same problem.

Think of it like Russian dolls. We open one doll. Inside is a smaller doll. We open that one. Inside is an even smaller doll. And so on. Until we reach the smallest doll that does not open.

Recursion is like that. We keep going smaller and smaller until we reach a point where we stop.

That stopping point is called the base case.

🧪 A Simple Recursion Example — Countdown

Let’s write a function that counts down from a number.

def countdown(n):
    if n == 0:
        print("Done!")
    else:
        print(n)
        countdown(n - 1)

Now call it:

countdown(5)

5
4
3
2
1
Done!

Let me explain what happened.

• countdown(5) prints 5, then calls countdown(4).
• countdown(4) prints 4, then calls countdown(3).
• countdown(3) prints 3, then calls countdown(2).
• countdown(2) prints 2, then calls countdown(1).
• countdown(1) prints 1, then calls countdown(0).
• countdown(0) sees that n is 0. So it prints “Done!” and stops. It does not call itself again.

That is recursion. The function keeps calling itself with a smaller number. Until it reaches the base case.

🏗️ The Two Parts of Recursion

Every recursive function has two parts.

Part 1: The base case

This is the condition where the function stops calling itself. Without it, the function would call itself forever. And our program would crash.

In the countdown example, the base case is if n == 0.

Part 2: The recursive case

This is where the function calls itself. But with a smaller or simpler input.

In the countdown example, the recursive case is countdown(n - 1).

Every recursive function needs both parts. Base case to stop. Recursive case to make progress.

⚠️ What Happens Without a Base Case in Python?

Let’s see what happens if we forget the base case.

def countdown(n):
    print(n)
    countdown(n - 1)

Now call countdown(5).

5
4
3
2
1
0
-1
-2
-3
...

It keeps going. Forever. Or at least until Python stops it.

Python has a limit on how deep recursion can go. It is usually 1000 levels. If we go beyond that, Python gives us an error.

RecursionError: maximum recursion depth exceeded

So let’s always have a base case. Always.

🧮 Another Recursion Example — Factorial

The factorial of a number is the product of all positive integers up to that number.

For example, factorial of 5 is 5 × 4 × 3 × 2 × 1 = 120.

Let’s write it with recursion.

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

Now call it:

print(factorial(5))

120

Let me trace through what happened.

• factorial(5) returns 5 * factorial(4).
• factorial(4) returns 4 * factorial(3).
• factorial(3) returns 3 * factorial(2).
• factorial(2) returns 2 * factorial(1).
• factorial(1) returns 1. Because that is the base case.

So the whole thing becomes:

5 * 4 * 3 * 2 * 1 = 120

That is recursion. Each call builds on the result of the smaller call.

🔍 Another Recursion Example — Fibonacci

The Fibonacci sequence is a series of numbers where each number is the sum of the two before it.

0, 1, 1, 2, 3, 5, 8, 13, 21, …

Let’s write it with recursion.

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Now call it:

print(fibonacci(7))

13

Because the 7th Fibonacci number is 13.

But let’s be careful. This recursive Fibonacci is very slow for large numbers. Because it recalculates the same values again and again. We will talk about that in a moment.

💡 When to Use Recursion in Python

Recursion is great when a problem can be broken into smaller versions of the same problem.

For example:

• Tree structures — going through a tree of folders or data
• Sorting algorithms — like quicksort and mergesort
• Mathematical sequences — factorial, Fibonacci, etc.
• Backtracking problems — like solving a maze or sudoku

But recursion is not always the best choice. Sometimes a loop is simpler and faster.

⚖️ Recursion vs Loops in Python

Anything we can do with recursion, we can also do with loops. And vice versa.

For example, the factorial can be written with a loop.

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

This is often faster than the recursive version. And it does not have the recursion depth limit.

So why use recursion? Because for some problems, recursion is more natural. It matches the way we think about the problem. Trees, for example, are naturally recursive.

Let’s use recursion when it makes the code clearer. Use loops when we need speed or want to avoid recursion limits.

🎯 The Problem with Recursive Fibonacci

Let’s look at the recursive Fibonacci again.

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

If we call fibonacci(40), it will take a long time. Why? Because it recalculates the same values many times.

For example, to calculate fibonacci(5), it calculates fibonacci(4) and fibonacci(3). To calculate fibonacci(4), it calculates fibonacci(3) and fibonacci(2). So fibonacci(3) is calculated twice. And this gets worse as n grows.

So recursive Fibonacci is not efficient. For real use, we would use a loop, or a technique called memoization.

📚 Recursion in Python: A Real-Life Example

Let’s write a function that finds the sum of all numbers in a nested list.

def sum_nested(data):
    total = 0
    for item in data:
        if isinstance(item, list):
            total += sum_nested(item)
        else:
            total += item
    return total

Now call it:

data = [1, 2, [3, 4], [5, [6, 7]]]
print(sum_nested(data))

28

Let me explain.

• The function loops through the list.
• If an item is a list, it calls itself on that list.
• If an item is a number, it adds it to the total.
• Finally, it returns the total.

That is a natural use of recursion. Because the data is nested. And the function handles any level of nesting.

🌍 Common Mistakes with Recursion in Python

❌ Mistake 1: Forgetting the Base Case

def countdown(n):
    print(n)
    countdown(n - 1)

This will run until Python stops it with a RecursionError.

So what do we do? We add a base case.

def countdown(n):
    if n == 0:
        print("Done!")
    else:
        print(n)
        countdown(n - 1)

🚫 Mistake 2: Not Making Progress

def bad(n):
    if n == 0:
        return
    else:
        bad(n)   # Same n, no progress

This will also run forever. Because n never changes. So the base case is never reached.

So what do we do? We make the input smaller.

bad(n - 1)

🛑 Mistake 3: Too Deep Recursion

def countdown(n):
    if n == 0:
        print("Done!")
    else:
        print(n)
        countdown(n - 1)

countdown(10000)

This will hit the recursion limit. Because Python only allows about 1000 levels deep.

So what do we do? We use a loop instead. Or increase the recursion limit (not recommended).

🐞 Mistake 4: Using Recursion When a Loop Is Simpler

def sum_list(numbers):
    if len(numbers) == 0:
        return 0
    else:
        return numbers[0] + sum_list(numbers[1:])

This works. But a simple loop is much better.

def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

Let’s use recursion when it makes sense. Not just because we can.

Next, we will learn about Python String Basics and start working with text in more detail.