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))
🏋️ Extra Practice — Algorithm Reps
Recursion feels like magic until you have written ten of them — then it feels obvious. Here are your ten.
🚀
Task 5: Recursive Countdown
Easy
Write countdown(n) that prints n, then calls itself with n − 1, and prints Go! when n reaches 0. Call countdown(5). Every recursion needs that stopping point — the base case.
5
4
3
2
1
Go!
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(5)
🔋
Task 6: Power Without **
Medium
Write power(base, exp) recursively: anything to the power 0 is 1, otherwise it is base * power(base, exp - 1). Print power(2, 10) and power(5, 3).
1024
125
def power(base, exp):
if exp == 0:
return 1
return base * power(base, exp - 1)
print(power(2, 10))
print(power(5, 3))
🔢
Task 7: Count the Digits
Medium
Write count_digits(n) that returns how many digits a whole number has — without turning it into text. Base case: a number below 10 has 1 digit. Otherwise it is 1 + count_digits(n // 10). Print it for 7, 4720 and 1000000.
1
4
7
def count_digits(n):
if n < 10:
return 1
return 1 + count_digits(n // 10)
print(count_digits(7))
print(count_digits(4720))
print(count_digits(1000000))
🪞
Task 8: Recursive Palindrome
Tricky
Write is_palindrome(word) recursively: a word of 0 or 1 letters is a palindrome; otherwise the first and last letters must match and the middle must be a palindrome too. Print it for "racecar", "level" and "python".
True
True
False
def is_palindrome(word):
if len(word) <= 1:
return True
if word[0] != word[-1]:
return False
return is_palindrome(word[1:-1])
print(is_palindrome("racecar"))
print(is_palindrome("level"))
print(is_palindrome("python"))
📦
Task 9: Flatten a Nested List
Tricky
Lists can hide inside lists. Write flatten(items) that returns one flat list from [1, [2, [3, 4]], 5]. Hint: check each item with isinstance(item, list) and recurse when it is one.
[1, 2, 3, 4, 5]
def flatten(items):
result = []
for item in items:
if isinstance(item, list):
result += flatten(item)
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4]], 5]))
🗼
Task 10: Boss Level: Tower of Hanoi
Boss
The classic puzzle: move a stack of discs from peg A to peg C using peg B, never putting a bigger disc on a smaller one. Write hanoi(n, source, helper, target) that prints each move like Move disc 1 from A to C. Run it for 3 discs — exactly 7 moves.
Move disc 1 from A to C
Move disc 2 from A to B
Move disc 1 from C to B
Move disc 3 from A to C
Move disc 1 from B to A
Move disc 2 from B to C
Move disc 1 from A to C
def hanoi(n, source, helper, target):
if n == 0:
return
hanoi(n - 1, source, target, helper)
print(f"Move disc {n} from {source} to {target}")
hanoi(n - 1, helper, source, target)
hanoi(3, "A", "B", "C")