Recursion
A function that calls itself. Mind-bending at first, then incredibly elegant.
Code runs right here in your browser. Nothing to install.
Learn it
A recursive function calls itself on a smaller problem until it reaches the base case.
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.
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))
Try it yourself
+10 XPWrite 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.
Capture the flag
+10 XPWhat 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.
Recursive toolkit
+20 XPWrite 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.