Python lesson 30

Recursion. A Function That Calls Itself

The strangest idea in this course, and one of the most useful.

Two Parts, Always

A recursive function calls itself on a smaller version of the problem. It needs a base case. The moment it stops. And a recursive case that gets closer to it. Without the base case it never ends, and Python gives up with a RecursionError.

def countdown(n):
if n == 0: # base case: STOP
print("Lift off!")
return
print(n)
countdown(n - 1) # smaller each time

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

countdown(3)

What Stops It?

def forever(n):
    print(n)
    forever(n - 1)

forever(3)

Build a Recursive Function

Factorial

5 factorial is 5 × 4 × 3 × 2 × 1. Run it and watch the layers unwind.

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

for n in range(1, 6):
    print(n, "factorial is", factorial(n))

Add Up a List

The sum of a list is the first item plus the sum of the rest. That sentence is the whole function.

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

print(total([1, 2, 3, 4, 5]))

Reverse a Word

Reversing a word is the last letter, plus the reverse of everything before it.

def backwards(word):
    if len(word) <= 1:
        return word
    return word[-1] + backwards(word[:-1])

print(backwards("python"))

What you can do on CodeIt

Run the example, change one part, and use the result to check your understanding before moving to the next lesson.