Recursion finally clicked when I stopped tracing every call
For weeks I tried to trace recursion by following every single call down and back up. It works for tiny inputs and melts your brain for anything real.
What finally worked was the "trust" approach:
1. Handle the base case: what's the smallest input, and what's the answer?
2. Assume the recursive call already works on the smaller problem.
3. Ask only: given that answer, how do I build the answer for my current input?
Example: counting nodes in a tree. Base case: an empty tree has 0 nodes. Trust that count(left) and count(right) are correct. Then my answer is count(left) + count(right) + 1. Done, no tracing needed.
Tracing is still great for debugging, but writing recursion with trust is so much faster.
Comments
This is how I explain it to people I tutor now. Base case, trust, combine.
Trusting the recursive call is the whole secret. Wish someone had told me sooner.