Recursion & Big-O

the core idea

🪆 Recursion = a function that calls itself

Every recursive function has exactly two parts. Both are required. If either is missing, the function breaks.

✅ Base Case

The stopping condition. When the problem is tiny enough to answer directly. Write this first, always. Without it → crash.

🔁 Recursive Case

The function calls itself with a smaller problem. Each call must bring the problem closer to the base case.

countdown — the simplest possible recursion

# Step 1: write the BASE CASE first def countdown(n): if n <= 0: # ← BASE CASE: stop here print('Done!') return print(n) # do something at this level countdown(n - 1) # ← RECURSIVE CASE: smaller!

factorial — recursion with a return value

def factorial(n): if n == 0: # BASE CASE: 0! = 1 return 1 return n * factorial(n - 1) # RECURSIVE CASE # factorial(4): # 4 × factorial(3) # 3 × factorial(2) # 2 × factorial(1) # 1 × factorial(0) ← base case → 1 # ← 1×1=1 ← 2×1=2 ← 3×2=6 ← 4×6=24 ✓

recursion on strings and lists — same pattern

# Reverse a string recursively def reverse(text): if text == '': # BASE CASE: empty string return '' return reverse(text[1:]) + text[0] # Sum a list recursively def list_sum(nums): if nums == []: # BASE CASE: empty list return 0 return nums[0] + list_sum(nums[1:])

Pattern: base case = empty input. Recursive case = operate on first, recurse on rest.

choose a function and input

function

n =

📦 call stack (newest on top)

📋 execution log

Press Next Step → to start the trace.

step 0 / 0

memory legend

blue frame = being called right now green frame = base case reached purple frame = returning a value grey = waiting for answer from below

fibonacci call tree — visualise the repeated work

Each node is one function call. Nodes with the same colour are computing the same value — wasted work. This is why naive Fibonacci is slow.

fib(n) — choose n

fib(5)

why this matters — big-o of fibonacci

factorial(n) → O(n)

One call per level. n calls total. Linear — manageable.

fib(n) naive → O(2ⁿ)

Two calls per level. Calls double each level. fib(40) = over a million calls!

drag to change n — watch the bars grow

n = 5

O(1) — constant

O(log n) — logarithmic

O(n) — linear

O(n²) — quadratic

complexity reference table

notation	name	example code	speed
O(1)	constant	my_dict['key'] · lst[0]	fastest
O(log n)	logarithmic	binary search (Week 13)	very fast
O(n)	linear	one for loop	acceptable
O(n log n)	linearithmic	merge sort (Week 12)	good for sorting
O(n²)	quadratic	nested for loop	slow — avoid

interactive: annotate this code

Click each function to reveal its Big-O and why.

use these 6 steps on every problem — even easy ones

Click a step to expand its example. The worked problem: "Find if a list has any duplicate names."

full worked example — brute force vs optimised

# Step 3 — Brute Force O(n²): two nested loops def has_duplicate_slow(names): for i in range(len(names)): for j in range(i + 1, len(names)): if names[i] == names[j]: return True return False # Big-O: O(n²) — loop inside a loop # Step 4 — Optimised O(n): use a dict as memory def has_duplicate_fast(names): seen = {} for name in names: # one loop = O(n) if name in seen: # dict lookup = O(1) return True seen[name] = True return False # Big-O: O(n) — one loop, O(1) lookup inside

recursion + big-o together

Counting recursive calls = Big-O

factorial(n) calls itself n times → O(n).
fib(n) calls itself twice per level → O(2ⁿ). Draw the call tree in Panel 3 to see it.

Brute force first, then optimise

Naive recursion is often the "brute force" in Step 3. Step 4 asks: can I cache the results? (That is memoization — coming later in the course.)