Practice question · Numerical answer
Computing fact(4) recursively, how many calls to fact are made in total, counting the original call and the base-case call?
Hints
- List the arguments of every call that occurs.
- The chain runs 4, 3, 2, 1, 0.
Show the answer
5
Why
The calls are fact(4), fact(3), fact(2), fact(1), fact(0), five in all. Each is a pending frame on the call stack, which is why a recursion that never reaches its base case exhausts memory rather than merely looping.
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).
- 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…