Practice question · Multiple choice
Proving a recursive function correct and proving a statement by induction are the same argument. Which parts correspond?
Hints
- When proving
factorial(n)correct, what do you assume aboutfactorial(n-1)? - Ask what stops the descent in each case.
Show the answer
A. Base case to base case, inductive hypothesis to the recursive call
Why
You assume the recursive call is correct for the smaller input and prove the current case follows, which is the inductive step verbatim. Termination corresponds to reaching the base, which is why a missing base case gives infinite recursion and a missing base case gives a failed induction.
Practise Mathematical Induction
The app has 8 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.