Recursion basics¶

~20 min · prerequisite: Scope: where names live

What you will be able to do¶

Explain what recursion means, and write a function that calls itself.
Write a base case that stops the calls, and a recursive case that makes the problem smaller.
Recognize the RecursionError message and find the missing base case that caused it.

The idea¶

Recursion is when a function calls itself. It sounds strange at first, but it is useful when a problem can be split into a smaller copy of the same problem. For example, the number of items in a list is one more than the number of items in the list without its first element.

A recursive function does not need a loop, because the repeated work happens through the calls. Every recursive function needs two parts. The base case is a situation that is answered directly, without another call. Check for it first in the function. The recursive case is the part that calls the function again on a smaller input. Each call must move closer to the base case. If it never does, the calls never end. Problems like nested lists follow the same pattern, because each level looks like the whole.

Think of a set of nesting dolls. You open one and find a smaller doll inside. You keep opening until you reach the smallest doll, which does not open at all. The smallest doll is the base case.

Each call gets its own local variables, so the call factorial(4) and the call it makes, factorial(3), do not overwrite each other's n.

Python limits how deep the calls can go. The default limit is 1000 nested calls. If a function goes deeper than that, Python stops it and raises a RecursionError.

Recursion is not a faster way to do work. A loop is usually clearer for a plain count. Use recursion when splitting the problem into smaller parts makes the code shorter.

Worked example¶

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


print(factorial(5))

Expected output:

Line by line, this is what Python does:

if n <= 1: checks the base case. When n is 1 or less, the function returns 1 without calling itself.
return n * factorial(n - 1) is the recursive case. It asks for the factorial of one less, and multiplies the answer by n.
factorial(5) needs 5 * factorial(4). That call needs 4 * factorial(3), which needs 3 * factorial(2), which needs 2 * factorial(1).
factorial(1) hits the base case and returns 1.
The waiting calls now finish in reverse order: 2 * 1 is 2, then 3 * 2 is 6, then 4 * 6 is 24, then 5 * 24 is 120.
print shows 120.

Try it¶

The first block checks the base and recursive cases of factorial. The second block adds up a list by taking off its first item each time. The third block splits a number into its last digit and the rest.

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


assert factorial(0) == 1
assert factorial(1) == 1
assert factorial(5) == 120
assert factorial(6) == 720

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


assert total([]) == 0
assert total([4, 5, 6]) == 15

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


assert digit_sum(7) == 7
assert digit_sum(2024) == 8

Common mistakes¶

Leaving out the base case. The following function calls itself forever:
```
def forever(n):
    return forever(n - 1)


forever(3)
```
Python stops the calls and reports:
```
RecursionError: maximum recursion depth exceeded
```
Add an if that returns a value when the input is small enough.

Returning nothing from the base case. The following base case prints a message but does not return a value:

def bad_factorial(n):
    if n <= 1:
        print("base case")
    else:
        return n * bad_factorial(n - 1)


bad_factorial(2)

Python reports:

TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'

The base case returned None. Return 1 there instead.

Expecting very deep recursion to work. The following call needs five thousand nested calls:

def count_down(n):
    if n == 0:
        return 0
    return 1 + count_down(n - 1)


count_down(5000)

Python reports:

RecursionError: maximum recursion depth exceeded

Use a loop for long counts, or keep the input small.

Forgetting to return the recursive result. The following function computes the answer and then throws it away:
```
def add_up(n):
    if n == 0:
        return 0
    add_up(n - 1) + n


assert add_up(3) == 6
```
Python reports:
```
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'
```
The call add_up(1) gives None, because its recursive line has no return. Write return add_up(n - 1) + n.

Practice¶

Define countdown_list(n) that returns a list from n down to 1, such as [3, 2, 1]. Assert that countdown_list(3) equals [3, 2, 1].
Define count_items(items) that returns the number of items in a list, without calling len. Assert that count_items(["a", "b", "c"]) equals 3, and that count_items([]) equals 0.
Define reverse_text(text) that returns the text reversed. Assert that reverse_text("abc") equals "cba", and that reverse_text("") equals "".
Define fibonacci(n) where fibonacci(0) is 0, fibonacci(1) is 1, and each later value is the sum of the two before it. Assert that fibonacci(6) equals 8 and that fibonacci(10) equals 55.
Stretch: define is_palindrome(text) that returns True when the text reads the same forwards and backwards. Use recursion on text[1:-1]. Assert that is_palindrome("level") is True, that is_palindrome("python") is False, and that is_palindrome("") is True.

Solution

```python def countdown_list(n): if n == 0: return [] return [n] + countdown_list(n - 1)

assert countdown_list(3) == [3, 2, 1] ```

```python def count_items(items): if not items: return 0 return 1 + count_items(items[1:])

assert count_items(["a", "b", "c"]) == 3 assert count_items([]) == 0 ```

```python def reverse_text(text): if text == "": return "" return reverse_text(text[1:]) + text[0]

assert reverse_text("abc") == "cba" assert reverse_text("") == "" ```

```python def fibonacci(n): if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2)

assert fibonacci(6) == 8 assert fibonacci(10) == 55 ```

```python def is_palindrome(text): if len(text) <= 1: return True if text[0] != text[-1]: return False return is_palindrome(text[1:-1])

assert is_palindrome("level") is True assert is_palindrome("python") is False assert is_palindrome("") is True ```

Recap¶

A recursive function calls itself on a smaller input, and must have a base case that returns without calling again.
Each call has its own local variables, and results return in reverse order.
Calls that go too deep raise RecursionError, which often means a missing base case.