CS 101 · MODULE 04

# Recursion: solving
problems by calling yourself.

In this module you'll learn why a function that calls itself is not a trick, but the most natural way to describe problems that contain smaller copies of themselves.

~ 45 min read prereq · functions, if/else lang · Python

OBJECTIVES

## By the end, you will be able to…

#### ① Explain recursion in one sentence.

"A function that solves a problem by calling itself on a smaller version of that problem."

#### ② Write a base case that always terminates.

Every recursive function must have an exit door, or it runs forever.

#### ③ Trace a call stack on paper.

Given `fact(4)`, draw the stack frames top-to-bottom.

#### ④ Convert a while-loop to a recursive equivalent.

And explain when one is clearer than the other.

CORE CONCEPT

## Two parts, always.

A recursive function has exactly two things inside it: a base case (when to stop) and a recursive case (how to shrink the problem before calling yourself).

Rule of thumb. If you can't name the base case out loud, don't write the recursion yet. Draw it on paper first.

#### Base case

The smallest possible input — one the function answers directly, without calling itself.

e.g. n == 0

#### Recursive case

Every other input — delegate to a smaller version of the same problem.

e.g. n × fact(n-1)

WORKED EXAMPLE

## Factorial, 7 lines.

    # fact(n) = n × (n-1) × … × 1,  and fact(0) = 1
    def fact(n):
        if n == 0:          # base case
            return 1
        return n * fact(n - 1)   # recursive case

    print(fact(4))   # → 24

Trace fact(4). 4 × fact(3) → 4 × (3 × fact(2)) → 4 × 3 × (2 × fact(1)) → 4 × 3 × 2 × 1 × fact(0) → 4 × 3 × 2 × 1 × 1 = 24.

EXERCISE 4.1

## Write sum_to(n).

Return `1 + 2 + … + n` using recursion — no loops allowed.

Your task

1. Write the base case. What does `sum_to(0)` return?
2. Write the recursive case in terms of `sum_to(n - 1)`.
3. Test it: `sum_to(5) == 15`, `sum_to(10) == 55`.
4. Bonus: what happens if you call `sum_to(-3)`? Fix it.

Stuck? Remember: a base case is the smallest input you already know the answer to.

CHECK YOUR UNDERSTANDING

## Which function will recurse forever?

A
def f(n): return 1 if n == 0 else n * f(n - 1)

Base case `n == 0`, shrinks toward it. Terminates.

B
def f(n): return n + f(n + 1)

✓ Correct. No base case, and `n` grows — infinite recursion.

C
def f(n): return n if n < 2 else f(n - 1) + f(n - 2)

Classic Fibonacci. Base case on `n < 2`. Terminates.

SUMMARY · MODULE 04

# You can now…

#### ✓ Define recursion

A function that calls itself on a smaller input.

#### ✓ Write a safe base case

Every recursion needs an exit door.

#### ✓ Trace a call stack

You can unwind `fact(4)` by hand.

#### ✓ Judge when to use it

Trees and self-similar problems → recursion. Flat iteration → loop.

Up next · Module 05. Divide & conquer: merge sort. We'll use everything you just learned — but on lists, not numbers.