Recursion in Python

In the last lesson you learned Scope of Variables. That was about where a name lives and who can see it. Now we look at a different idea. A function that calls itself. It sounds strange at first, right? But once it clicks, some problems become really clean to solve. This is called recursion. That is what this lesson is about.

🤔 Why Recursion?

Some problems are made of smaller copies of themselves. Think about a folder on your computer. A folder holds files. But it can also hold more folders. And those folders hold more folders. To go through everything inside, you do the same job again and again on a smaller box each time.

You could try to write that with loops. But it gets messy fast. Here is the pain. The problem keeps shrinking into the same shape. A normal loop does not naturally follow that shape. Recursion solves it in one line of thinking. You say “to solve the big thing, solve a slightly smaller thing the same way, and stop when it gets tiny.”

🧩 What Recursion Actually Is

Recursion is when a function calls itself to solve a smaller piece of the same problem.

Here is a real-world way to picture it. Imagine Alex is standing in a long line and wants to know what position they are in. Alex cannot see the front. So Alex taps the person ahead and asks, “what is your position?” That person asks the person ahead of them. And so on down the line. The very first person knows their answer is 1. Then the answer travels back down the line. Each person adds one. That is recursion. Everyone does the same small job. And there is one person at the front who already knows the answer without asking.

Every recursive function needs two parts.

• A base case. This is the simple situation where the function knows the answer right away and stops. The first person in the line is the base case.
• A recursive case. This is where the function calls itself on a smaller version of the problem. Each call moves one step closer to the base case.

📉 A Gentle Example: Countdown

Let’s start with something easy to picture. We want a function that counts down from a number to zero and prints each number. Here it is.

def countdown(n):
    if n == 0:          # base case: stop here
        print("Done!")
        return
    print(n)            # do a little work
    countdown(n - 1)    # recursive case: smaller problem

countdown(3)

Running that prints this.

3
2
1
Done!

Now let’s walk through it slowly. This is where recursion makes sense.

• We call countdown(3). Is n zero? No. So it prints 3, then calls countdown(2).
• Inside countdown(2), is n zero? No. It prints 2, then calls countdown(1).
• Inside countdown(1), is n zero? No. It prints 1, then calls countdown(0).
• Inside countdown(0), is n zero? Yes! This is the base case. It prints Done! and returns.

See how each call works on a smaller number than the one before? That shrinking is what carries us to the base case. Without it, the countdown would never end.

🔢 A Real Example: Factorial

Now a classic one. The factorial of a number means you multiply it by every whole number below it, down to 1. So the factorial of 4 is 4 × 3 × 2 × 1, which is 24. People write it as 4!.

Here is the recursive idea in plain words. The factorial of 4 is just 4 times the factorial of 3. And the factorial of 3 is 3 times the factorial of 2. It keeps shrinking. The factorial of 1 is simply 1. That is where we stop. So that becomes our base case.

This is the same thing in code.

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

print(factorial(4))

That prints the answer.

24

The line-by-line story is the fun part. Watch how the calls stack up and then fold back.

• factorial(4) cannot finish yet. It needs factorial(3) first. So it waits.
• factorial(3) needs factorial(2). It waits too.
• factorial(2) needs factorial(1). It also waits.
• factorial(1) hits the base case and returns 1 right away. No more waiting.

Now the answers travel back up. factorial(2) was waiting for that 1, so it returns 2 × 1, which is 2. Then factorial(3) returns 3 × 2, which is 6. Finally factorial(4) returns 4 × 6, which is 24. Each call was paused, holding its own value of n, waiting for the smaller call to come back.

This stack of paused calls has a name. Python keeps track of them on the call stack. Every time a function calls itself, a new entry goes on top. When a call returns, its entry comes off. The base case is what lets the stack start emptying.

⚠️ Common Mistakes

The biggest danger with recursion is forgetting to stop. If there is no base case, or the calls never reach it, the function calls itself forever. Python does not let that run truly forever. It stops you with a RecursionError.

Here is the broken version. Notice it never checks for a base case.

# ❌ Avoid: no base case, so it never stops
def countdown(n):
    print(n)
    countdown(n - 1)   # always calls again, even past zero

countdown(3)

That prints 3, 2, 1, 0, and then keeps going into negative numbers until Python gives up.

3
2
1
0
-1
-2
...
RecursionError: maximum recursion depth exceeded

The fix is always the same. Add a base case. Then make sure each call moves toward it.

# ✅ Good: base case stops the recursion
def countdown(n):
    if n < 0:          # base case
        return
    print(n)
    countdown(n - 1)

countdown(3)

A few more slips to watch for.

• Calling yourself with the same value, like factorial(n) instead of factorial(n - 1). The problem never shrinks, so the base case never arrives.
• Putting the base case check after the recursive call. Then the function dives down before it ever gets a chance to stop.
• Forgetting to return the recursive call’s result. If you call factorial(n - 1) but do not return or use it, the answer gets thrown away.

✅ Best Practices

• Write the base case first, before anything else. It is the part that keeps you safe, so put it at the top of the function.
• Make sure every recursive call uses a smaller input than the one it got. If you cannot point to what is shrinking, the recursion is probably wrong.
• Keep the recursive case simple. One clear step toward the base case is easier to trust than a tangle of conditions.
• Reach for recursion when the problem is naturally nested. Folders inside folders, or a tree of comments where each reply can have its own replies. For plain counting or running through a list, a normal loop is usually shorter and easier to read.

🧩 What You’ve Learned

• ✅ Recursion is a function that calls itself to solve a smaller piece of the same problem.
• ✅ Every recursive function needs a base case that stops it and a recursive case that moves toward that base case.
• ✅ You traced a countdown and a factorial step by step, watching the calls stack up and then fold back with answers.
• ✅ Forgetting the base case (or not shrinking the input) causes infinite recursion and a RecursionError.
• ✅ Recursion fits naturally nested problems, but a plain loop is often simpler and safer.

🚀 What’s Next?

You have functions that can call themselves now. That is a big step. Next we move from numbers and logic into working with text. It is one of the things you will use most in real programs.

String Basics