Practice question · Sort into groups
Each definition is evaluated at n = 5. Sort by whether the recursion terminates.
Groups: Terminates · Runs forever
- f(n) = f(n) + 1, with f(0) = 0
- f(n) = 2 * f(n - 1), with f(1) = 1
- f(n) = f(n - 1) + 1, with f(0) = 0
- f(n) = f(n - 2), with f(0) = 1 and f(1) = 1
- f(n) = f(n + 1) - 1, with f(0) = 0
Hints
- Every one of these HAS a base case, check whether the calls actually travel toward it.
- Follow the argument from 5 and see where it goes.
Show the answer
Terminates: f(n) = f(n - 1) + 1, with f(0) = 0, f(n) = f(n - 2), with f(0) = 1 and f(1) = 1, f(n) = 2 * f(n - 1), with f(1) = 1
Runs forever: f(n) = f(n) + 1, with f(0) = 0, f(n) = f(n + 1) - 1, with f(0) = 0
Why
d1, d3 and d5 shrink the argument and land on a base case (d3 goes 5, 3, 1). d2 never changes n and d4 increases it, so neither ever reaches 0 despite having a base case. Having a base case is not enough; the calls must reach it.
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…
- 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…