Practice question · Put in order
The lesson's factorial function is called as factorial(3). Order the events by when they happen in time.
- factorial(3) starts and calls factorial(2)
- factorial(1) starts and calls factorial(0)
- factorial(0) returns 1 without recursing
- The waiting calls finish in turn, giving 1, then 2, then 6
- factorial(2) starts and calls factorial(1)
Hints
- Each call is suspended at the moment it makes its own call, and cannot finish before that call does.
- The first call to be made is the last one to finish.
Show the answer
- factorial(3) starts and calls factorial(2)
- factorial(2) starts and calls factorial(1)
- factorial(1) starts and calls factorial(0)
- factorial(0) returns 1 without recursing
- The waiting calls finish in turn, giving 1, then 2, then 6
Why
Calls stack up on the way down and unwind on the way back, so factorial(3) is the first to start and the last to finish. This is exactly why deep recursion costs memory: every suspended call keeps its frame on the call stack until the one below it returns.
Practise Recursion and Iterative Alternatives
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Recursion and Iterative Alternatives
- Every recursive function can be rewritten as a loop, and every loop can be rewritten recursively. Why does…
- A recursive function that would need a million frames crashes in Python and runs fine in a language with…
- Select every statement the lesson supports about choosing recursion over iteration.
- A recursive function that has a base case cannot recurse forever.