Fibonacci, strings and lists

In the Fibonacci sequence, each number is the sum of the two numbers before it: 1, 1, 2, 3, 5, 8, 13 and so on. The definition has two base cases, the first two numbers, and its recursive case calls the function twice:

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


print([fibonacci(n) for n in range(1, 11)])

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

You can check it one number at a time: fibonacci(3) is fibonacci(2) + fibonacci(1), which is 1 + 1 = 2. Then fibonacci(4) is fibonacci(3) + fibonacci(2), which is 2 + 1 = 3, and so on.

Two calls in every call add up fast, though. fibonacci(30) makes more than a million calls, because it works out the same smaller numbers again and again. A loop that remembers the two latest numbers is much faster. Recursion is often the clearest way to write something down, not always the fastest way to run it.

Smaller strings and lists

Recursion works whenever a problem has a smaller problem of the same kind inside it. A string without its first character is a shorter string, and a list without its first item is a shorter list. Slices give you those smaller pieces: text[1:] and numbers[1:]. The base case is often the empty string or the empty list.

The sum of a list is its first number plus the sum of the rest:

def list_sum(numbers):
    if len(numbers) == 0:
        return 0
    return numbers[0] + list_sum(numbers[1:])


print(list_sum([4, 8, 15, 16]))

43

A string reversed is the rest of it reversed, with the first character at the end:

def reverse(text):
    if text == "":
        return ""
    return reverse(text[1:]) + text[0]


print(reverse("stressed"))

desserts

A palindrome reads the same backwards, like "racecar". A string is a palindrome if its first and last characters are the same and the part between them, text[1:-1], is a palindrome too. A string of 0 or 1 characters is always one:

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


print(is_palindrome("racecar"))
print(is_palindrome("rocket"))

True
False

This one has two base cases: a short string gives True, and a mismatch gives False straight away, without looking at the rest.

When you write a recursive function, ask yourself two questions. What is the simplest case, and what's its answer? And how does the answer for a slightly smaller problem help with the whole one?