Recursion & Big-O — InteractLab

Module 1Every recursion needs two things

Base case

The stop sign. Without it, the function calls itself forever and Python crashes with RecursionError. Write this first.

Recursive case

The step that shrinks the problem — n - 1, a shorter string, a smaller list — so it always heads toward the base case.

# 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!

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

# factorial(4):
# 4 x factorial(3)
#     3 x factorial(2)
#         2 x factorial(1)
#             1 x factorial(0) <- base case -> 1
# <- 1x1=1 <- 2x1=2 <- 3x2=6 <- 4x6=24  OK

# 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:])

Module 2Watch the calls pile up and unwind

factorial(n) returns a number: n × (n−1) × … × 1.

Call stack

factorial(4)running

Execution log

call factorial(4)

Step 1 / 11Call factorial(4). It cannot finish until factorial(3) comes back, so it waits.

1 / 11

speed1×

Space play/pause · ←→ step · Home/End jump · R replay

Module 3The Fibonacci tree — the same work, over and over

15total calls

5fib(5)

≈ 322ⁿ growth

Wasted work: fib(3) ×2fib(2) ×3fib(1) ×5fib(0) ×3 — each of these is recomputed from scratch. Caching them (memoisation) turns this whole tree into a single straight line.

Module 4How fast does the work grow?

O(1)

O(log n)

3.0

O(n)

O(n²)

At n = 8, O(n²) already needs 64 steps while O(1) needs just 1. Now imagine n = 1,000,000.

Big-O	Name	Example	Verdict
`O(1)`	constant	`my_dict['key'] · lst[0]`	fastest
`O(log n)`	logarithmic	`binary search`	very fast
`O(n)`	linear	`one for loop`	acceptable
`O(n log n)`	linearithmic	`merge sort`	good for sorting
`O(n²)`	quadratic	`nested for loop`	slow — avoid

PracticeGuess the Big-O

def f1(items):
    return items[0]

def f2(items):
    for x in items:
        print(x)

def f3(items):
    for i in items:
        for j in items:
            ...

def f4(d, key):
    return d.get(key)

Module 5Six steps for any problem

Before writing a single character of code, make sure you fully understand what the problem wants. Write it in your own words.

# Problem: "find if a list has duplicate names"
# Input:  a list of strings → ['Adam','Sara','Adam']
# Output: True or False
# Rule:   True only if ANY name appears more than once

Worked example — brute force vs. optimised

# Step 3 - Brute Force O(n^2): 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^2) - 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 — nesting dolls and how fast code grows