Practice question · Put in order
Order what happens when a recursive factorial computes 3 factorial.
- The call for 3 needs the value for 2
- The call for 1 needs the value for 0
- The base case gives the value for 0 as 1
- The results multiply back up to give 6
- The call for 2 needs the value for 1
Hints
- Recursion descends to the base case before anything is actually multiplied.
- Nothing can be returned until the base case is reached.
Show the answer
- The call for 3 needs the value for 2
- The call for 2 needs the value for 1
- The call for 1 needs the value for 0
- The base case gives the value for 0 as 1
- The results multiply back up to give 6
Why
The calls stack downward to the base case, which is the first value actually known, and only then does the multiplication unwind upward. Without the base case the descent never stops, the stack overflow.
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.
- 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…