Week 14 — Lecture Outline · Recursion (Intro)

Course: Introduction to Computer Science — CS1 / Programming Fundamentals in Python (CSCI 1101) · Silver Oak University (fictional sample) · Prof. Okafor
Objective covered: Objective 8 — Use recursion (base case & recursive case, the call stack) and relate it to iteration.
SLOs touched: A (write & run a recursive function) · B (trace the call stack; find & fix a defect)
Meeting pattern: 2 studio sessions × 75 min = 150 min.

Every output below was produced by actually running the code in Python — not hand-traced. Run them live; visualize the call stack in Python Tutor.

---

Week at a Glance

Big question	"What happens when a function calls itself — and how does it ever stop?"
By end of week, students can…	(1) explain the base case and the recursive case; (2) write a simple recursive function (factorial, countdown, sum); (3) trace the call stack as calls pile up and unwind; (4) explain recursion vs. iteration and what a missing base case causes (RecursionError).
Key vocabulary	recursion, recursive function, base case, recursive case, call stack, frame, return value, infinite recursion, RecursionError, iteration
Materials	slides (Deck 14), readings, the online editor + Python Tutor (essential this week), one approved chatbot
Timing note	8 segments, ~150 min. Students run every example and step through the call stack in Python Tutor.

---

Segment 1 — Hook & the Promise (8 min)

Hook. Hold up two mirrors facing each other — a tunnel of reflections, each a smaller copy of the same thing. "That's recursion: something defined in terms of a smaller version of itself. Today a function will call itself — and the trick is making sure it ever stops."

Promise: "By Friday you'll write a function that calls itself, trace the stack of calls as it piles up and unwinds, and know the one line that keeps it from running forever."

Memory hook: "Every recursion needs a base case to stop and a recursive case to shrink."

---

Segment 2 — Base Case + Recursive Case (the code-along) (24 min)

Plain language. A recursive function solves a problem by calling itself on a smaller version, until it reaches a base case simple enough to answer directly.

Code-along — factorial (5! = 5×4×3×2×1):

def factorial(n):
    if n == 0:          # base case: stop here
        return 1
    return n * factorial(n - 1)   # recursive case: shrink toward 0

print(factorial(5))     # run-verified -> 120
print(factorial(0))     # run-verified -> 1   (base case)

"Two parts, always: the base case (n == 0 → return 1) stops the recursion; the recursive case (n * factorial(n-1)) shrinks n toward the base case. Without the base case it never stops."

Land the idea: every recursive call must make the problem smaller and move toward the base case. factorial(5) calls factorial(4) calls factorial(3) … factorial(0), which stops.

---

Segment 3 — The Call Stack (the worked trace in Python Tutor) (24 min)

Plain language. Each call waits for the call it made to finish — they stack up like dishes, then unwind from the top.

Code-along — countdown (paste into Python Tutor and step through):

def countdown(n):
    if n == 0:
        print("Go!")
        return
    print(n)
    countdown(n - 1)

countdown(3)            # run-verified -> 3, 2, 1, Go!  (four lines)

"Watch the call stack in Python Tutor: countdown(3) prints 3 and calls countdown(2) (now two frames), which prints 2 and calls countdown(1), which prints 1 and calls countdown(0), which hits the base case, prints Go!, and returns — then each frame unwinds back up the stack."

A returning example — sum 1..n:

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(5))        # run-verified -> 15   (5+4+3+2+1)

"This one returns values that add up as the stack unwinds: sum_to(0) returns 0, then 1+0, then 2+1, … up to 15."

---

Segment 4 — Spot & Fix the Bug: the Missing Base Case (18 min) · Session 1 closes

The buggy program — recursion with no base case:

def bad(n):
    return n + bad(n - 1)   # no base case — never stops!

print(bad(5))

Run it. Python protects itself and stops with (run-verified): RecursionError: maximum recursion depth exceeded.
"The function kept calling itself — bad(5), bad(4), bad(3), … past 0 into negatives — and never hit a stopping point. The call stack grew until Python cut it off. The fix is always the same: add a base case that returns without recursing."

def good(n):
    if n <= 0:          # base case
        return 0
    return n + good(n - 1)
print(good(5))          # run-verified -> 15

Land the idea: infinite recursion is the recursion version of an infinite loop. The base case is your "stop" — never write a recursive function without one.

---

Segment 5 — Recursion vs. Iteration (20 min) · Session 2 opens

Plain language. Anything you can do with recursion you can usually do with a loop (iteration), and vice versa. Same factorial, two ways:

# Recursive
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# Iterative
def factorial_iter(n):
    result = 1
    for i in range(1, n + 1):
        result = result * i
    return result

print(factorial(5))       # run-verified -> 120
print(factorial_iter(5))  # run-verified -> 120

"Same answer. Recursion is often clearer when a problem is naturally self-similar (file folders inside folders, a family tree). Iteration (a loop) avoids the call-stack overhead and can't hit RecursionError. Pick whichever makes the code clearer."

---

Segment 6 — When Recursion Shines (16 min)

Plain language — recursion fits self-similar problems. Examples to name (not implement in depth): exploring folders inside folders; walking a family/organization tree; the divide-and-conquer idea behind binary search (Week 13) — "search the left half" is itself a smaller search.

Misconception + cure:
- ❌ "Recursion is just a fancy loop with no rules."
✅ Cure: it has strict rules — a base case and a smaller recursive call every time. Break either and you get wrong answers or a RecursionError.
- ❌ "Recursion is always better / always worse than a loop."
✅ Cure: neither — choose the one that makes the problem clearest.

---

Segment 7 — Misconceptions Round-Up + Interaction (20 min)

• ❌ "A recursive function doesn't need a base case if the input is small." ✅ It always needs one — otherwise RecursionError.
• ❌ "The recursive call can use the same n." ✅ It must move toward the base case (e.g., n - 1), or it never stops.
• ❌ "countdown(3) prints Go! first." ✅ It prints 3, 2, 1, Go! — the base case is reached last.
• ❌ "Recursion and iteration give different answers." ✅ Same answer (factorial 120 both ways) — different style.

Interaction — trace-then-run: put a small recursive function on a slide; have the room predict the printed output and the order, then run it and step through the stack in Python Tutor.

---

Segment 8 — Technology Workflow + AI-Critique, Callback & Hand-off (18 min) · Session 2 closes

Technology workflow: (1) write the base case first, then the recursive case that shrinks toward it; (2) run it on a small input; (3) paste it into Python Tutor and step through to watch the call stack grow and unwind; (4) if you get RecursionError, your base case is missing or unreachable.

AI-critique moment:

Ask a chatbot: "Write a recursive function for factorial and tell me what factorial(5) returns and how many times the function is called." Then run it and step through Python Tutor: chatbots sometimes omit or misplace the base case (causing infinite recursion), miscount the calls, or get the unwinding order wrong. The tool drafts; you run it and judge.

Callback + tease:
- Callback: "A function that calls itself — with a base case to stop and a smaller call each time — and a call stack you can watch."
- Tease next week: "We've used functions and data. Next week we bundle data and the functions that work on it together into objects — our first look at object-oriented programming, with classes and __init__."

Hand-off: Lecture Tutorial 14; Quiz 14; Discussion 14 ("Explain Recursion to a Friend"); Assignment 14 ("Call Yourself"); Coding Lab 14 — "Watch the Stack."

---

Instructor FAQ — Common Stumbles

Student says / does	Quick cure
Writes a recursive function with no base case.	Add a base case that returns without recursing, or you get RecursionError.
Recursive call doesn't shrink (f(n) calls f(n)).	The argument must move toward the base case (e.g., n - 1).
Expects countdown(3) to print Go! first.	Base case is reached last — output is 3, 2, 1, Go!.
Confused by the unwinding of sum_to.	Step through Python Tutor — values add up as frames return.
Thinks recursion is always better than a loop.	Choose whichever is clearer; iteration avoids stack overhead.

---

Scope flag

This outline keeps recursion at the intro level: a single self-call with a clear base case (factorial, countdown, sum). Multiple/mutual recursion, recursion on trees and graphs, memoization, and tail-call details are CS2. The call stack is shown via Python Tutor, not implemented. RecursionError is referenced factually; the instructor and institution remain fictional. Every output shown was produced by running the code.