Recursion in Python: A Clear, Simple Explanation

What is Recursion?

A recursive function is a function that calls itself. Recursion solves problems by breaking them into smaller versions of the same problem.

The classic analogy: looking up a word in a dictionary. If the definition contains another word you don't know, you look that up too — recursion.

The Two Parts of Every Recursion

1. Base case — when to stop (simplest answer)
2. Recursive case — break problem into smaller version

Without a base case, recursion runs forever and crashes.

Classic Example: Factorial

n! = n × (n-1) × (n-2) × ... × 1

def factorial(n):
    if n == 0:                # BASE CASE
        return 1
    return n * factorial(n - 1)  # RECURSIVE CASE

print(factorial(5))   # 120

How It Executes

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * (1 * factorial(0)))))
= 5 * (4 * (3 * (2 * (1 * 1))))
= 120

Example: Sum of a List

def sum_list(lst):
    if len(lst) == 0:           # BASE
        return 0
    return lst[0] + sum_list(lst[1:])  # RECURSIVE

print(sum_list([1, 2, 3, 4]))   # 10

Example: Countdown

def countdown(n):
    if n == 0:                  # BASE
        print("Blast off!")
        return
    print(n)
    countdown(n - 1)            # RECURSIVE

countdown(3)
# 3
# 2
# 1
# Blast off!

Example: Fibonacci

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))   # 55

Recursion vs Iteration

Almost every recursive solution can be written with a loop. When to use each:

• Recursion: problems naturally split into smaller versions (tree structures, divide-and-conquer)
• Iteration: sequential processing, when you'd otherwise create too many function calls

Common Pitfalls

1. Missing Base Case

def bad(n):
    return n + bad(n - 1)   # never stops!
# RecursionError: maximum recursion depth exceeded

2. Infinite Recursion

def bad(n):
    if n == 0: return 0
    return bad(n)           # doesn't get smaller!

3. Unnecessary Work

Naive Fibonacci recomputes the same values millions of times. For HKDSE, use iteration or memoisation.

HKDSE Context

Recursion appears in ~30% of HKDSE Paper 1B papers, usually as a simple factorial or sum. Know the pattern, even if you prefer iteration for your own code.