Lesson 11/25 · 🌀 Recursion
🌀 RecursionLesson 11/25
Phase 3 · Recursion20 min

Recursion Fundamentals

Functions that call themselves, and why that's not as scary as it sounds

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive solution has two parts:
1. Base case, the simplest version that doesn't recurse (stops infinite loops)2. Recursive case, breaks the problem into a smaller version of itself
Classic recursion: factorialpython
def factorial(n):
    # Base case: 0! = 1
    if n == 0:
        return 1
    # Recursive case: n! = n × (n-1)!
    return n * factorial(n - 1)

# factorial(4) = 4 × factorial(3)
#              = 4 × 3 × factorial(2)
#              = 4 × 3 × 2 × factorial(1)
#              = 4 × 3 × 2 × 1 × factorial(0)
#              = 4 × 3 × 2 × 1 × 1
#              = 24

print(factorial(4))  # → 24
🔍Code TracerStep 1 / 5
trace.py
1def fib(n):
2 if n <= 1: return n←
3 return fib(n-1) + fib(n-2)
4
5result = fib(4)
Variables
nint
4
Step 1 / 5
🤔Quick Check

What happens if you forget the base case in a recursive function?

Practice Exercises

0/1 solved
Exercise 1 of 1medium
⏱ 00:00

Power Function

Implement x raised to the power n using recursion. Use fast exponentiation (halve the problem each time).
Expected output: 8
solution.py
1 / 1
Solve all 1 exercise to unlock completion
PreviousNext