Practice question · Fill in the blanks
Complete the condition for a recursion to terminate.
A recursive function fails to terminate when its calls ______.
Word bank: reach the base case too quickly · do not make the problem strictly smaller · return a value each time · use a loop instead of recursion
Hints
- A base case is necessary but not sufficient.
- A call on the SAME size of problem makes no progress at all.
Show the answer
A recursive function fails to terminate when its calls do not make the problem strictly smaller.
Why
Progress is the second requirement: each call must shrink the problem so the base case is eventually reached. A definition like f(n) = f(n) + 1 has a base case that is simply never reached.
Practise Recursion
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Recursion
- A recursive function calls itself, which sounds like it should never finish. Why does a correct recursion…
- Each definition is evaluated at n = 5. Sort by whether the recursion terminates.
- Order what happens when a recursive factorial computes 3 factorial.
- The factorial is defined by fact(n) = n * fact(n-1) with fact(0) = 1. Compute fact(5).
- Computing fact(4) recursively, how many calls to fact are made in total, counting the original call and the…
- A recursive Fibonacci function is elegant and unusably slow; the loop version is ugly and instant. Where does…