Chapter 22 Key Takeaways: Recursion

  1. Recursion solves problems by self-reference. A recursive function calls itself with simpler arguments until it reaches a base case it can solve directly.

  2. Every recursive function needs a base case and a recursive case. The base case stops the recursion. The recursive case makes progress toward the base case. Missing either one causes infinite recursion and a stack overflow.

  3. Recursion has two phases: winding and unwinding. During winding, calls are pushed onto the stack. During unwinding, results propagate back. Where you place work relative to the recursive call determines whether it executes during winding or unwinding.

  4. Elegant recursion is not always efficient recursion. Naive recursive Fibonacci is a beautiful translation of the mathematical definition but has exponential O(2ⁿ) time complexity due to redundant recomputation. Efficiency often requires memoization, dynamic programming, or conversion to iteration.

  5. Recursion shines on recursive data structures. Linked lists and trees have recursive definitions — a list is a node plus a list, a tree is a node plus subtrees. Recursive algorithms on these structures mirror their definitions exactly.

  6. The call stack is finite. Each recursive call consumes stack space. Very deep recursion (tens of thousands of calls) can overflow the stack. Know your depth limits and choose iteration for potentially deep recursion on linear structures.

  7. Recursion vs. iteration is a design choice. Use recursion when the problem has self-similar structure and bounded depth (trees, divide-and-conquer). Use iteration when recursion is linear, very deep, or involves redundant computation.

  8. Tail recursion carries computation forward. In tail recursion, the recursive call is the last operation, and all computation is encoded in accumulator parameters. Some compilers can optimize tail recursion into a loop.

  9. Mutual recursion uses forward declarations. When function A calls B and B calls A, Pascal's forward keyword declares A's signature before B's body, breaking the circular dependency.

  10. The threshold concept: recursion reflects problem structure. Do not ask "can I use recursion?" Ask "does this problem contain smaller copies of itself?" If the problem is recursive, the code should be recursive. If it is not, use a loop.