A recursive solution delegates work to smaller instances of the same problem. Understanding it requires two views: how calls are created, and how their results return to complete the waiting work.
Reading route¶
Recursive calls and termination: identify the base case, progress and returned results.
The call stack: follow separate frames and distinguish live depth from total calls.
Divide, conquer and combine: connect splitting to a complete worked sorting example.
Recursion trees and costs: explain balanced and unbalanced shapes, levels, time and space.
Implementation choices: compare index-based merging with front removal and account for slicing.
The figures show the calls, state and intermediate results used by the code. Read each diagram with the surrounding trace, rather than treating the tree as a picture of simultaneous execution.
Before you start¶
Review objects and references and algorithm analysis. Basic function calls, loops and list indexing are assumed. No notebook is required.
After reading, you should be able to trace calls and returns, justify termination for valid inputs, distinguish recursion from divide-and-conquer, and explain why recursion depth alone does not determine time complexity.
One route from contracts to costs¶
Specify valid inputs, returned results, side effects and exceptions first. Identify a reachable base case and a decreasing measure that keeps child calls in the valid domain. Follow the suspended work and returned results, justify the local combine step, then count total local work and maximum live storage separately.
Read each call diagram in execution order, then trace the returned values. The cost summary distinguishes sort frames, total sort calls, merging, copied references and returned output. Python’s finite recursion capacity remains a practical limit, not a proof that a valid mathematical recursion fails to terminate.
For a particular term, use the concept index. The Sorting topic compares merge sort with other strategies; here merge sort supplies a concrete example of recursive decomposition.
Code listings offer Python, JavaScript and Julia tabs where a runnable example is present. Python remains the explanation and trace language; see the language guide for native conventions and runnable topic downloads.