RUBY / CHAPTER 11
Recursive decomposition and termination
AdvancedTrace both calls and returns while proving progress.
By the end of this chapter
- Identify a base case
- Trace work before and after recursion
- Bound recursion depth deliberately
The idea
A recursive method delegates a smaller version of a problem to itself. A valid base case stops the chain, and every supported nonbase input must make progress toward that case. State the input domain explicitly; subtracting one approaches zero from positive integers but moves away from zero from negative integers. Validation and termination are related parts of the method’s contract.
Each invocation has its own local variables. Work before the recursive call happens while descending, and work afterward happens as calls return. A trace should therefore record both phases instead of treating recursion like a loop that only runs downward. Deep recursion consumes stack space, so an iterative algorithm may be more suitable for large inputs even when the recursive version is mathematically correct.
def sum_to(n)
raise ArgumentError if n < 0
return 0 if n == 0
n + sum_to(n-1)
end
puts sum_to(4)10
The chain reaches zero, then the waiting additions accumulate one, three, six, and ten.
Try it yourself
Trace a method that prints before and after its recursive call, then compare an iterative sum.
Use your own editor for this exercise. Runnable challenges on CodeQuest are available for JavaScript, Python, and SQL.
CHECK YOUR UNDERSTANDING