Recursion
Loading
Loading
Recursion
The two halves of every recursive function, and why trusting the recursion is the skill.
By the end of this chapter
def total(nums, index=0): if index == len(nums): # base case: returns without recursing return 0 # recursive case: strictly smaller problem, plus the combining step return nums[index] + total(nums, index + 1)Concept
Do not trace the call stack. Assume total(nums, index + 1) correctly returns the sum of the rest, then ask only whether adding nums[index] to it gives the right answer. If the base case is right and the combining step is right, the whole thing is right by induction.
Each pending call holds a frame: parameters, locals, and where to return to. A recursion n levels deep therefore uses O(n) memory even if it allocates nothing.
If the recursion tree contains the same arguments many times, the work is exponential for no reason. Storing each answer the first time it is computed collapses it.
routes(5) computed naivelyroutes(5)calls routes(4) and routes(3)routes(4)calls routes(3) and routes(2)routes(3)computed twice alreadyroutes(2)and this one three timesroutes(2) is recomputed 3 timesQuick quiz
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: take the quiz above, and try 1 practice problem.