Recursion on Linked Structures
When the data structure recurses, the traversal usually should too
In a nutshell
A linked list has the recursive shape “a head node plus a smaller linked list.” A recursive traversal mirrors that shape: base case when head is NULL, recursive case when you process head->value and recurse on head->next. The resulting code is often shorter than the iterative version and makes the invariants obvious. The cost is stack frames: recursing on a list of a million nodes can overflow the stack, so iterative traversal is still the default for large inputs.
Why it matters
Trees are linked structures where each node points to multiple children. Traversing a tree iteratively means maintaining your own stack; recursively it falls out of the recursive structure. Before you get to trees in week 9, practice the pattern on linked lists where it is simple.
Key takeaways
- Base case first. For linked-list recursion, the base case is almost always
if (head == NULL) return ...;. - Recursive case processes head, recurses on tail.
process(head->value); recurse(head->next);. - Tail recursion. If the recursive call is the last thing the function does, some compilers optimize it to iteration. C compilers are inconsistent about this; do not rely on it.
- Recursion uses stack space proportional to list depth. A million-node list can blow the stack.
- Every linked-list algorithm (length, find, reverse, copy, free) has a clean recursive form. Writing each one both ways is the exercise.
Lessons in this topic
(Lesson pages for week 8 are being authored.)
Practice and deep dives
Practice this topic: browse the practice gallery.
What comes next
Trees (preview) — each node points to two children instead of one. The recursion pattern you just practiced generalizes: process the node, recurse left, recurse right.