By the end of this lesson, cadets will be able to:
Complete before class. Recursion is new (CS110 did not cover it), so plan to read carefully.
| Source | Sections | Why |
|---|---|---|
| Supplementary notes (required) | Recursion I: First Exposure (all six sections) | Vocabulary and the call stack model. About 25 minutes. |
| King, C Programming: A Modern Approach | Section 9.6 (Recursive Functions), optional | Optional deeper dive with additional worked examples |
Note: Beej's Guide does not cover recursion as a topic. The supplementary notes are the assigned reading; they are short and focused.
n values per frame (Section 4)factorial(5) returns and write down what the call stack looks like at its deepest point. The trace widget in class will confirm or correct your prediction.Recursion is a way of solving a problem by breaking it into a smaller version of itself. The reference material below previews the concepts you saw in the supplementary notes; the in-class trace widget makes them visible in motion.
The Lesson 11 deck walks through the recursion concept, base case identification, the call stack model, factorial as the canonical example, and the two pitfalls. Roughly 30 to 40 minutes of lecture, then straight into the trace widget.
A recursive function is a function that calls itself. That single sentence is the whole concept, but it lands strangely the first time you read it. The question that immediately follows is, "if a function calls itself, when does it stop?" The answer to that question is what makes recursion work.
Each call works on a smaller version of the problem. Eventually one call hits the simplest possible version, returns an answer directly, and the chain of waiting calls unwinds with values flowing back. The supplementary notes show this with a simple countdown example before moving to factorial.
Every recursive function has exactly two pieces. Identifying them is the first thing you do when writing or reading recursive code.
| Piece | What it does |
|---|---|
| Base case | The smallest version of the problem. Returns directly. No further recursive calls. |
| Recursive case | Does a little work, then calls the function on a smaller input, then combines the result. |
Factorial is the textbook example because the math itself is already recursive: n! = n · (n-1)! and 0! = 1. The math tells you what the base case and the recursive case should be.
Every active function call has its own stack frame in memory: a little bundle holding that call's parameters, local variables, and a marker for where to return when the call finishes. The call stack is the collection of all currently-active frames, with the most recent call on top. A recursive call pushes a new frame; a return pops one.
During factorial(3), four frames are alive at once:
+----------------------------+ | factorial n=1 ret=? | <-- top (most recent) +----------------------------+ | factorial n=2 ret=? | +----------------------------+ | factorial n=3 ret=? | +----------------------------+ | main | <-- bottom +----------------------------+
Each frame has its own copy of n. There are three separate n values alive at the same time, and they do not interfere with each other. This is the fact the trace widget in Section 5 makes visceral.
Most broken recursion fails in one of two ways. Both involve the base case.
In Lesson 6 you learned about functional decomposition: breaking a problem into smaller, well-named functions. Recursion is decomposition in its purest form. Every recursive function says, "this problem decomposes into a smaller version of itself, plus a tiny bit of glue." The base case and the recursive case are the two pieces that decomposition produces.
When you write the L11 lab functions, name the pieces explicitly to yourself before you write any code: what is the base case? and what is the smaller problem? If you can answer both in plain English, the C code follows quickly.
Recursive code is short but conceptually dense. A two-line recursive function can hide a base-case bug that takes an hour to find. The DFCS C Programming Standard §2.4 (Inline Comments) applies directly: a comment above the base case stating what the base case is, and a comment above the recursive call stating what gets smaller, makes the intent visible to a reader and to your future self when the program crashes.
The standard reminds you not to comment every line and not to rephrase code in English — comments explain code in the context of the problem. For L11, that means a one-line comment per function naming the base case and the recursive case, not blow-by-blow narration. See the Resources section for the full standard.
Three things to do in class. Use the checklist to track your progress.
Five preloaded examples. Step through each one and watch the call stack grow and shrink. Mark all five complete to earn your code.
Enter your name. It will appear on the completion screen so you can include it in your screenshot for the Blackboard reflection.
Eight questions covering base case identification, return-value tracing, stack depth, broken recursion, and the questions to ask before writing recursion. Answer each one, click Submit, then click Next. Score of 70% or higher earns the passing code.
Enter your name. It will appear on the completion screen so you can include it in your screenshot for the Blackboard reflection quiz.