Practice question · Multiple choice
A recursive function calls itself, which sounds like it should never finish. Why does a correct recursion terminate, and what happens when the base case is missing?
Hints
- For factorial(n) calling factorial(n−1), what happens to the argument at each step?
- Ask what stops the descent.
Show the answer
A. Because each call takes a strictly smaller input toward a base case.
Why
Two conditions must hold: the argument strictly decreases toward the base, and the base handles the smallest input without recursing. Remove it and the descent runs past zero, adding frames until the stack is exhausted. The parallel with induction is exact, base case, inductive hypothesis, and proving a recursion correct is an induction proof.
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
- 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…
- Complete the condition for a recursion to terminate.
- A recursive Fibonacci function is elegant and unusably slow; the loop version is ugly and instant. Where does…