Recursion in Python: A Beginner's Guide

Recursion is a famously tricky concept to grasp, but it's honestly quite simple, so don't let it intimidate you. A recursive function is just a function that calls itself.

All the content from our Boot.dev courses are available for free here on the blog. This one is the "Recursion" chapter of Learn Functional Programming in Python. If you want to try the far more immersive version of the course, do check it out!

What Is Recursion in Python?

If you thought loops were the only way to iterate over a list, you were wrong! Recursion is fundamental to functional programming because it's how we iterate over lists while avoiding stateful loops. Take a look at this function that sums the numbers in a list:

def sum_nums(nums: list[int]) -> int:
    if len(nums) == 0:
        return 0
    return nums[0] + sum_nums(nums[1:])

print(sum_nums([1, 2, 3, 4, 5]))
# 15

Don't break your brain on the example above! Let's break it down step by step.

How Does a Recursive Function Work?

Our goal is to sum all the numbers in a list, but we're not allowed to loop. So, we start by solving the smallest possible problem: summing the first number in the list with the rest of the list:

return nums[0] + sum_nums(nums[1:])

So, what actually happens when we call sum_nums(nums[1:])? Well, we're just calling sum_nums with a smaller list! In the first call, the nums input was [1, 2, 3, 4, 5], but in the next call it's just [2, 3, 4, 5]. We just keep calling sum_nums with smaller and smaller lists.

Here's another example, walking through a string one character at a time:

def print_chars(word: str, i: int) -> None:
    if i == len(word):
        return
    print(word[i])
    print_chars(word, i + 1)

print_chars("Hello", 0)
# H
# e
# l
# l
# o

What Is a Base Case in Recursion?

So what happens when we get to the "end"? sum_nums(nums[1:]) is called, but nums[1:] is an empty list because we ran out of numbers. We need to write a base case to stop the madness.

if len(nums) == 0:
    return 0

The "base case" of a recursive function is the part of the function that does not call itself.

How Do You Write a Recursive Factorial Function?

A classic example is the factorial. A factorial is the product of all positive integers less than or equal to a number. For example, 5! (read: "five factorial") is 5 * 4 * 3 * 2 * 1, which is 120.

The factorial of n is n times the factorial of n - 1, and the base case is that 0! is 1 (since 0! is an empty product).

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

print(factorial(5))
# 120

Why Use Recursion for Nested Lists?

Recursion really shines on nested data, like a list of lists, where you don't know how deep the nesting goes. Imagine each list represents a directory and each number represents a file size in bytes:

def sum_nested_list(items: list[int | list]) -> int:
    total = 0
    for item in items:
        if isinstance(item, list):
            total += sum_nested_list(item)
        else:
            total += item
    return total

print(sum_nested_list([5, [6, 7], [[8, 9], 10]]))
# 45

When item is an integer, we add it to the total. When it's a list, we recurse into it. The built-in isinstance function can tell you if an item is an integer or a list. You can use loops with recursion. While functional programming avoids loops, recursion is also used outside functional programming.

How Do You Use Recursion on a Dictionary?

Recursion is often used in "tree-like" structures because they can have unknown depth:

• Nested dictionaries
• File systems
• HTML documents
• JSON objects

Here we walk a file system represented as nested dictionaries, where a folder's value is another dictionary and a file's value is None:

def list_files(directory: dict, path: str) -> list[str]:
    file_paths = []
    for name, value in directory.items():
        new_path = path + "/" + name
        if value is None:
            file_paths.append(new_path)
        else:
            file_paths.extend(list_files(value, new_path))
    return file_paths

The base case looks a bit different from before, but it's just when a nested node's value is None because in that case, we don't have any more directories to explore.

When Should You Use Recursion Instead of a Loop?

Recursion is so dang useful with tree-like structures because we don't always know how deeply they're nested. Stop and think about how you would write nested loops to traverse a tree of arbitrary depth... it's not easy, is it?

for item in tree:
    for nested_item in item:
        for nested_nested_item in nested_item:
            for nested_nested_nested_item in nested_nested_item:
                # ... WHEN DOES IT END???

I most often use recursion on tree-like problems (file systems, nested dictionaries, etc.). If I'm just iterating over a one-dimensional list, then a loop (gasp...) is typically simpler, even if it's not as "pure" in the academic sense.

Remember: the rules of functional programming are just philosophies to help you write better code, but it's not always the right tool for the job. The same goes for any programming paradigm.

What Are the Dangers of Recursion in Python?

Recursion is great because it's simple and elegant (simple != easy). It's often the most straightforward way to solve a problem. But there are some dangers to be aware of:

1. Stack overflow: Each function call requires a bit of memory. So, if you recurse too deeply, you can run out of "stack" memory, which will crash your program. (This is what the famous website is named after.)
2. If you don't have a solid base case, you can end up in an infinite loop (which will likely lead to a stack overflow).
3. Especially in a language like Python, recursion is often slower than a for loop because each function call requires some memory. Tail call optimization can help with this, but Python doesn't support it.

If you're brand new to writing functions and loops, our Learn Python course covers the fundamentals before you dive deeper into functional patterns.