Stage 1 · Code
Programming Foundations
Recursion
Recursive thinking, base cases, call stack, and tail recursion.
Recursive Thinking
Recursion solves problems by breaking them into smaller instances of the same problem. Every recursive function needs: (1) a base case that stops recursion, (2) a recursive case that makes progress toward the base case.
Base Cases
Without a base case, recursion becomes infinite (stack overflow). Always identify the simplest input(s) that can be solved directly.
- Empty/zero case: Empty list, n=0, empty tree.
- Single element case: Length 1, leaf node.
- Boundary conditions: Start/end of array, root of tree.
Call Stack Visualization
Each recursive call adds a frame to the call stack. For factorial(4):
Tail Recursion
A tail call is when the recursive call is the last operation. Go doesn't guarantee tail call optimization, but writing tail-recursive functions is good practice for languages that do optimize.
Recursion vs Iteration
| Aspect | Recursion | Iteration |
|---|---|---|
| Readability | Often cleaner for tree/graph problems | Better for simple loops |
| Memory | O(depth) call stack | O(1) typically |
| Stack overflow risk | Yes for deep recursion | No |
| Go optimization | No TCO guaranteed | Preferred for deep loops |
Go's default stack is small (~1KB initial, grows as needed). Deep recursion (10k+ calls) can cause stack overflow. For deep algorithms (DFS on deep trees), prefer explicit stack with slice or increase stack with runtime.SetMaxStack().
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.