Thinking Recursively

Solve a problem by trusting a smaller copy of it. Base cases, the call stack, and how to design recursive solutions without getting lost. The leap of faith Designing recursion is easier than tracing it. Ask three questions: What is the smallest input? Answer it directly.How can I make the input smaller? (n − 1, the rest of the list, half the array.)If a friend solved the smaller problem, how…