Recursion – functions that call themselves

What you'll learn

Understand how a function can call itself
Tell the base case from the recursive step
Break problems down into smaller problems of the same kind

A function that calls itself

In the turtle lesson you already drew a tree that draws itself. The principle is called recursion: a function solves a problem by handing a smaller version of the same problem to itself.

def countdown(n):
    if n == 0:
        print("Lift-off! 🚀")
        return
    print(n)
    countdown(n - 1)


countdown(5)

The two ingredients

Every recursion needs exactly two things:

Base case – a case so simple that you know the answer straight away (above: n == 0).
Recursive step – the problem is made a bit smaller and passed on (above: countdown(n - 1)).

Without a base case, the function calls itself forever:

def endless(n):
    return endless(n + 1)


endless(1)

Python stops after about 1000 calls with a RecursionError – luckily!

Recursion with a result

def sum_up_to(n):
    if n == 1:
        return 1
    return n + sum_up_to(n - 1)


print(sum_up_to(4))   # 4 + 3 + 2 + 1

This is how Python thinks it through: sum_up_to(4) = 4 + sum_up_to(3) = 4 + 3 + sum_up_to(2) = 4 + 3 + 2 + sum_up_to(1) = 4 + 3 + 2 + 1 = 10. Watch it with ⏯ Steps!

What is it good for?

Recursion is ideal for things that are nested inside themselves: folders with subfolders, family trees, mazes, fractals – and many fast sorting methods.

folder = {"Photos": {"Holiday": {"beach.jpg": 0}, "dog.jpg": 0}, "note.txt": 0}


def count_files(content):
    count = 0
    for name, value in content.items():
        if isinstance(value, dict):
            count += count_files(value)   # subfolder: same question, smaller
        else:
            count += 1
    return count


print(count_files(folder), "files")

Quick check

What does this program print?

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


print(f(5))

Your task

Your turn

Write two functions recursively (without a loop – the function calls itself). factorial(n) calculates n! = n · (n−1) · … · 1, with factorial(0) == 1. digit_sum(n) adds up the digits of a number: digit_sum(472) == 13 (tip: n % 10 is the last digit, n // 10 the rest in front of it).

def factorial(n):
    pass


def digit_sum(n):
    pass


print(factorial(5))
print(digit_sum(472))

Something to think about
Base case: for n == 0 return 1. Otherwise: n * factorial(n - 1).
Which command helps?
Base case: a one-digit number is its own digit sum. Otherwise: last digit (n % 10) + digit_sum(n // 10).
The function must call itself inside its own body – and there shouldn't be a for or while loop.

Gap code – fill in the ___

                        def factorial(n):
    if ___:
        return ___
    return ___


def digit_sum(n):
    if ___:
        return ___
    return ___


print(factorial(5))
print(digit_sum(472))

Solve it without hints to earn a ⭐ on your progress page.

Show solution

Try it yourself first – mistakes teach you the most. Here is one possible solution:

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


def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)


print(factorial(5))
print(digit_sum(472))