Browser lab20 min+60 XP

Recursion

A function that calls itself. Mind-bending at first, then incredibly elegant.

0% done

Code runs right here in your browser. Nothing to install.

TASK 1

Learn it

Key idea

A recursive function calls itself on a smaller problem until it reaches the base case.

Key words
factorial(4)factorial(3)factorial(2)factorial(1)base case: 1factorial(4) = 4 * 6 = 24callscallscallsreturns 1returns 2returns 6
Calls go down to the base case, then the answers come back up.

A recursive function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs two parts: a base case that stops the recursion (the smallest problem, answered directly), and a recursive case that calls the function again with a smaller input.

Factorial is the classic example: 5! = 5 x 4 x 3 x 2 x 1. Notice that 5! = 5 x 4!. So factorial(n) returns n * factorial(n - 1), and the base case is factorial(1) = 1.

Without a base case the function calls itself forever until Python stops it with a RecursionError.

Real life linkFolders inside folders inside folders: a program that counts every file on a disk uses recursion to open each folder and then each folder inside that.
Example code
def countdown(n):
    if n == 0:
        print("Lift off!")
    else:
        print(n)
        countdown(n - 1)

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

countdown(3)
print(factorial(5))
TASK 2

Try it yourself

+10 XP

Write a recursive sum_to(n) that returns 1 + 2 + ... + n. The base case is sum_to(1) = 1. Print sum_to(10), which should be 55.

Create a free account to start this lab

Sign in to write, run and check your code here. Your progress, XP and code are saved to your account. No card needed.

TASK 3

Capture the flag

+10 XP

What is the name for the part of a recursive function that stops the recursion? (two words)

Create a free account to start this lab

Sign in to answer the flag question. Your progress, XP and code are saved to your account. No card needed.

HOMEWORK

Recursive toolkit

+20 XP

Write three recursive functions: power(base, exp) (base to the power exp, using power(b, 0) = 1), reverse(text) (the last character plus the reverse of the rest) and fib(n) (Fibonacci: fib(0) = 0, fib(1) = 1, each next one is the sum of the two before). Print power(2, 10), reverse("vault") and the first 10 Fibonacci numbers as a list.

Create a free account to start this lab

Sign in to do this homework and have it checked. Your progress, XP and code are saved to your account. No card needed.