By the end of this lesson, cadets will be able to:
The reading for this lesson is the instructor-written supplementary notes. There is no Beej chapter assigned; the notes are the source.
Recursion on a linked list is mostly transcription: the structure is recursive, so the function is too. The reference material below previews the concepts; the in-class trace widget shows them in motion, and the lab is where you write them.
The Lesson 32 deck walks through the recursive structure of a list, the deferred operation each frame holds, the before-versus-after-the-call distinction, recursive freeing and the order trap, and the bridge to trees. Roughly 30 to 40 minutes of lecture, then into the trace widget and the lab.
Lesson 32 slide deck (PDF) — opens in a new tab
A linked list is either empty (a NULL pointer) or one node followed by another linked list, the part next points at. That second half is itself a list, so the structure is defined in terms of a smaller version of itself. The base case is the empty list; the thing that shrinks is the list, because each call passes node->next; and it terminates because a finite list ends at NULL.
When a function reaches return 1 + list_length(node->next); it cannot finish until the recursive call returns, so it suspends and the 1 + it still owes is saved in its stack frame. Go several nodes deep and several frames stack up, each holding its own deferred operation, waiting. The answer is assembled on the way back up as the calls return, not on the way down. The trace widget draws this directly, showing each suspended frame holding 1 + ? and then resolving it.
For length and sum you would normally use a loop, and Lesson 33 takes up that tradeoff. The place recursion clearly wins on a singly linked list is any operation that must run from the tail back toward the head, because the list has no backward pointer. Putting the work after the recursive call gives you tail-first order for free: the deepest frame acts first. That is the shape of reverse printing and of the collect_reverse function in the lab.
Recursive freeing also acts after the call: free the rest of the list first, then this node's word string, then the node itself. The order is not optional. Freeing the node first and then reaching for node->next reads memory you just returned, which is a use after free. Each node owns two heap allocations, the node and its word, and both must be freed.
This lesson revisits two standing rules rather than introducing a new section. Section 8.5 (always free dynamically allocated memory) returns with a twist: when a struct member is itself a heap pointer, freeing the struct means freeing that member first, so free_list must free each node's word before the node. Section 2.4 (inline comments) earns its keep in recursive code: a one-line comment naming the base case and what shrinks makes a recursive function far easier for the next reader. See the standard in the course Resources for the full text.
Two things to do in class. Use the checklist to track your progress.
Five functions: list_length, list_sum, find, print_reverse, and free_list. Step through each one and watch two things: the call stack growing on the left with each frame holding its deferred work, and the heap below with the node the active frame points at lit up. Answer the prediction at the end of each trace to mark it complete.
Enter your name. It will appear on the completion screen so you can include it in your screenshot for the Blackboard reflection quiz.
Step through five recursive functions over a linked list of structs. The call stack grows on the left; each suspended frame shows the deferred work it is holding (for example 1 + ?). The heap is below, and the node the active frame points at lights up. At the end of each trace, answer one prediction to mark it complete.
node_t nodesnode_t struct: its num and word fields sit in the DATA cell, and next holds the address of the following node (or NULL). The lit node is the one the active frame points at.print_reverse and free_list, watch how the work happens after the recursive call, on the way back up the stack. Miss a prediction twice and the hint button pulses. Stuck on the concept? Schedule EI.
valgrind --leak-check=full on your demo before you submit; the autograder will.