Recursion

Problem

How many arrangements are there?

There are 5 books on the shelf. In how many ways can you arrange them? For the first spot there are 5 choices, for the second 4, then 3, 2 and 1: 5 · 4 · 3 · 2 · 1 = 120. This is a factorial, written 5!.

You can already do it with a loop:

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


print(factorial_loop(5))

Output

120

Look at it this way too: 5! = 5 · 4!. And 4! = 4 · 3!. The task is solved through the same task, only smaller. Can the function say exactly that?

The idea

A function that calls itself

It can. A function that calls itself is called recursive, and the approach is recursion.

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


print(factorial(5))

Output

120

Two things make it work:

• A base case. A case that is solved directly, without a new call. Here: 1! = 1.
• A smaller task. Each call calls itself with a number closer to the base case: n - 1.

See it

The pile of calls

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


print(factorial(3))  # 6

Step by step, in words

1. The program calls factorial(3).
2. New memory for factorial with n = 3.
3. 3 is not 1, so the function calls factorial(2) and waits for the answer.
4. The same again: factorial(2) calls factorial(1). Each call has its own n.
5. n is 1: this is the base case. It returns 1 without calling again.
6. The answer comes back down: 2 * 1 = 2.
7. And again: 3 * 2 = 6.
8. factorial(3) returns 6 and the program prints it.

Each call gets its own memory with its own n. They pile up one on top of the other and wait. This pile is called the call stack. When the base case returns 1, the answers go back down one by one and the pile comes apart.

Try it

Down and back up

What will the program print?

def steps(n):
    if n == 0:
        return
    print(f"down {n}")
    steps(n - 1)
    print(f"up {n}")


steps(2)

Answer

down 2
down 1
up 2
up 1

down 2
up 2
down 1
up 1

down 2
down 1
up 1
up 2

Check

Try it

Find the bug

sum_to(4) should return 1 + 2 + 3 + 4 = 10. Instead, the program stops with RecursionError: maximum recursion depth exceeded. Which line is the bug on?

Pick the line with the bug.

1def sum_to(n):2 if n == 1:3 return 14 return n + sum_to(n)

Check

The idea

Recursion or a loop?

You can write the factorial with a loop or with recursion. Here the loop is the better choice: it does not pile up memory for each call. And Python puts a limit on the stack: at around 1,000 nested calls it stops the program with a RecursionError. Even factorial(1100) does not get through, while the loop works it out too.

Recursion is natural where a thing contains smaller things of the same kind: a folder with folders inside, a category with subcategories, a branch with branches. You will come across tasks like these later in the course. There a loop gets clumsy, while the recursive function stays short.

More precisely, if you are curious

• The factorial is often written with the base case 0! = 1 (if n == 0:). Then it works for 0 too.

• Integers in Python have no limit: however big the result is, that is how many digits it has. 30! comes out exactly:

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


print(factorial(30))

Output

265252859812191058636308480000000

• You can raise the stack limit with sys.setrecursionlimit(), but that is rarely a good idea: for deep calculations, write a loop.

Try it

Put the lines in order

The function has to work out a power: power(2, 10) is 1024. Put its lines in order.

1. def power(base, exp):↑↓
2. return 1↑↓
3. return base * power(base, exp - 1)↑↓
4. if exp == 0:↑↓

Check

Exercise

Recursive tasks

1. Factorial two ways. Write factorial_loop(n) with a for loop and factorial(n) with recursion. Read a number and print the result from both functions.

Input

5

Output

The factorial of 5 is 120
The factorial of 5 is 120

2. Sum of digits. sum_digits(n): the last digit (n % 10) plus the sum of the digits of the rest (n // 10). The base case is a single-digit number.

3. Fibonacci. Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8… fib(n) returns the nth number. Try it with 10, and then with 35. Why is it so slow? Hint: how many times is each number worked out?

4. Palindrome. is_palindrome(s): the first and last letters are the same, and the middle is a palindrome. The base case is a word with 0 or 1 letters.

Calls

sum_digits(2024)
fib(10)
is_palindrome("level")
is_palindrome("ABCDE")

Output

8
55
True
False

Test

Check yourself

1. What is recursion?

Two functions with the same nameA loop inside a functionA function that calls itself

2. Why does a recursive function need a base case?

So it stops calling itselfSo it can return a resultSo it runs faster

3. factorial(3) calls factorial(2), and that calls factorial(1). How many variables n are in memory just before factorial(1) returns?

ThreeOneNone

4. What happens if the base case is never reached?

The function returns 0The program runs forever, with no errorThe stack overflows and the program stops with a RecursionError

Check

Start the lesson over