Recursion is when a function calls itself to solve a smaller version of the same problem. Think of Russian nesting dolls 🪆 — each doll contains a smaller doll, until you reach the tiniest one that contains nothing.
Every recursive function needs two parts:
Base case — the simplest version, where it stops calling itself.
Recursive case — where it calls itself on a smaller problem.
No base case = disaster!
Without a base case, the function calls itself forever and Python crashes with a RecursionError. Always make the problem get smaller and have a clear stopping point.
🔢 Classic example: countdown
def countdown(n):
if n == 0: # base case
print("Liftoff!")
return
print(n)
countdown(n - 1) # recursive case (smaller!)
countdown(3)
# 3
# 2
# 1
# Liftoff!
✖️ Building a result: factorial
The factorial 5! = 5 × 4 × 3 × 2 × 1. Notice that 5! = 5 × 4! — a smaller copy of the same problem!
def factorial(n):
if n == 1: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5)) # 120
💡 How to trust recursion
Don't trace every call in your head! Just ask: "Is my base case correct?" and "Does each call get closer to it?" If yes, trust that the smaller call returns the right answer.
🌀 The call stack
Each recursive call waits for the one inside it to finish, stacking up like a pile of plates. When the base case returns, the stack "unwinds" back up:
Recursion = a function calling itself on a smaller problem.
Always need a base case (stop) and a recursive case (shrink).
Each call waits on the call stack until the base case returns.
Great for problems that contain smaller copies of themselves (trees, factorials, Fibonacci).
🎮 Time to Practice!
Find the base case, shrink the problem, and let recursion do the rest. 🪆
✖️
Task 1: Factorial
Easy
Finish factorial(n). Base case: n == 1 returns 1. Otherwise return n * factorial(n - 1). Print factorial(5) → 120.
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
print(factorial(5))
➕
Task 2: Recursive Sum
Medium
Add the numbers 1 to nwithout a loop. The trick: sum_to(n) = n + sum_to(n - 1), and sum_to(0) = 0. Print sum_to(5) → 15.
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
print(sum_to(5))
🔄
Task 3: Reverse a String
Tricky
Reverse text recursively! A reversed string is the last character + the reverse of the rest. Base case: an empty string returns itself. Print reverse("hello") → olleh. (Hint: s[0] is the first char, s[1:] is the rest.)
def reverse(s):
if s == "":
return ""
return reverse(s[1:]) + s[0]
print(reverse("hello"))
🐚
Task 4: Fibonacci
Challenge
Each Fibonacci number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8... Finish fib(n) where fib(n) = fib(n-1) + fib(n-2), with base cases fib(0)=0 and fib(1)=1. The loop prints the first 7 numbers.
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
for i in range(7):
print(fib(i))