Himanshu SharmaSoftware engineer
Let’s talk

Python Tutorial · Lesson 40 of 70

Python recursion: functions that call themselves

Learn how a Python function can call itself, why every recursive function needs a base case, and how recursion depth and loops compare, with real output.

13 minFunctionsUpdated 14 November 2026

Awaiting technical review. This lesson is readable but not yet listed in search engines.

By the end of this lessonWrite a simple recursive function with a base case and a recursive step, and explain what happens when the base case is missing.

After this lesson you can read and write a function that solves a problem by calling itself, and you can recognise the two parts that keep such a function safe.

The idea

Recursion sounds mysterious, but the idea is simple. To solve a big problem, solve a slightly smaller version of the same problem and combine the answer. A function that does this calls itself.

Think of counting the people in a queue. You cannot see the whole line, so you ask the person ahead of you "how many are in front of you?", add one, and answer the person behind. The person at the very front knows without asking: nobody is ahead. That person is the stopping point.

Two required parts

Every working recursive function has:

  1. A base case: an input so small that the answer is known directly. No further call is made.
  2. A recursive case: the function calls itself with a smaller input, getting closer to the base case.

Here is a countdown with both parts:

python
def countdown(n):
    if n == 0:
        print("liftoff")
        return
    print(n)
    countdown(n - 1)

countdown(3)
result
3
2
1
liftoff

When n is 0 the base case prints and returns. Otherwise the function prints and calls itself with n - 1. Each call is closer to zero.

A function that returns a value

The classic example is the factorial. factorial(4) means 4 * 3 * 2 * 1. Notice that factorial(4) is 4 * factorial(3).

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

print(factorial(0))
print(factorial(4))
print(factorial(10))
result
1
24
3628800

Trace factorial(3) by hand. It waits for factorial(2), which waits for factorial(1), which waits for factorial(0). That one returns 1. Then the waiting calls finish in reverse order: 1 * 1, then 2 * 1, then 3 * 2. This waiting list of unfinished calls is called the call stack.

You can see the order by printing on the way in and out:

python
def trace(n):
    print("enter", n)
    if n > 0:
        trace(n - 1)
    print("leave", n)

trace(2)
result
enter 2
enter 1
enter 0
leave 0
leave 1
leave 2

Another example: adding a list

You can sum a list recursively by taking the first item and adding the sum of the rest:

python
def total(numbers):
    if not numbers:
        return 0
    return numbers[0] + total(numbers[1:])

print(total([5, 10, 15]))
result
30

The base case is the empty list, whose total is 0. This is for learning. In real code you would write sum(numbers), which is simpler and faster.

Where recursion shines: nested data

Loops are better for flat data. Recursion pays off when a structure contains smaller copies of itself, such as a menu with sub-menus.

python
menu = {
    "name": "Food",
    "children": [
        {"name": "Drinks", "children": [
            {"name": "Tea", "children": []},
            {"name": "Juice", "children": []},
        ]},
        {"name": "Snacks", "children": []},
    ],
}

def show(node, depth=0):
    print("  " * depth + node["name"])
    for child in node["children"]:
        show(child, depth + 1)

show(menu)
result
Food
  Drinks
    Tea
    Juice
  Snacks

No loop could be written without knowing in advance how deep the nesting goes. The recursive version does not care. Each node, however deep, is handled by the same code.

Forgetting the base case

If the recursion never reaches a base case, the calls pile up. Python protects you by stopping after a limit, which by default is about a thousand calls.

python
def forever(n):
    return forever(n + 1)

forever(0)
result
RecursionError: maximum recursion depth exceeded

This limit is why recursion is a poor choice for walking a list of a million items. A loop has no such limit.

python
import sys
print(sys.getrecursionlimit())
result
1000

Recursion versus loops

The factorial can also be written with a loop:

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

print(factorial_loop(10))
result
3628800

Both give the same answer. For simple counting, prefer the loop. For trees, nested folders and similar shapes, prefer recursion.

Counting the steps

It helps to measure how deep a recursion goes. The next function counts how many digits a whole number has by cutting off the last digit each time:

python
def count_digits(n):
    if n < 10:
        return 1
    return 1 + count_digits(n // 10)

print(count_digits(7))
print(count_digits(48213))
result
1
5

The base case is a single digit. Each recursive call works with a number that is ten times smaller, so it must eventually reach the base case. Whenever you write a recursive function, ask yourself two questions: "what is the smallest input, and what do I return for it?" and "how does every other input get smaller?" If you can answer both, the function will work.

Common mistakes

  • No base case. The most common mistake, ending in a RecursionError.
  • A recursive step that does not get smaller. Calling countdown(n) instead of countdown(n - 1) never ends.
  • Forgetting to return the recursive result. Writing factorial(n - 1) without return gives None.
  • Using recursion for long flat data. A loop is simpler and has no depth limit.
  • Skipping the hand trace. If a recursive function confuses you, write out the first three calls on paper.

Exercise

Write a recursive function power(base, exponent) that returns base raised to a non-negative whole exponent, without using **. The base case is exponent 0, which gives 1. Test it with power(2, 5).

Show one possible answer
python
def power(base, exponent):
    if exponent == 0:
        return 1
    return base * power(base, exponent - 1)

print(power(2, 5))
print(power(5, 0))
result
32
1

Key points

  • A recursive function calls itself on a smaller version of the problem.
  • Every recursive function needs a base case that stops the calls, and a recursive case that moves toward it.
  • Without a base case Python stops the program with a RecursionError once the call stack gets too deep.
  • Anything done with recursion can be done with a loop. Choose recursion when the data is naturally nested, such as folders inside folders.
  • Python allows about a thousand nested calls by default, so recursion is not a good fit for very long sequences.

Check yourself

1. What is the base case of a recursive function?
2. What happens if a recursive function never reaches its base case?
3. What does factorial(4) equal, where factorial(n) is n * factorial(n - 1) and factorial(0) is 1?
4. Which data is a natural fit for recursion?