P-5.2 Recursion, and Trusting It

Work through these

• A base case and a step that makes the problem smaller

  Those two pieces are the entire recipe, and a missing or unreachable base case is what produces infinite recursion. Write the base case first every time.

  Algorithms · Reference

• Assume the smaller call is already correct, and write only one step

  Trusting the recursive call rather than tracing it is the mental move that makes this workable. Tracing three levels down to convince yourself is how people conclude recursion is hard.

• Recursion on trees, where the structure is already recursive

  A tree is a node with subtrees, so a function that handles a node and calls itself on the children is a direct restatement of the definition. Nothing shorter exists.

• Each call costs a frame, and the stack has a limit

  Depth costs memory, so recursion proportional to input size will overflow on large inputs. This connects directly to the call stack from the data structures module.

• When a loop is the better answer, and what tail recursion means

  Simple linear recursion is often clearer as a loop and always cheaper. Some languages convert a call in the final position into a loop for you, and knowing whether yours does is worth checking.