We say that a recursive program is guaranteed to be correct if (1) It is correct for the base case, and (2) The recursive case is correct assuming the recursive calls return correct answers. What is the reason for this guarantee of correctness?

A. Infinite recursion

B. Proof by contradiction

C. Mathematical induction

D. Asymptotic notation

Trace the following code. What is mystery(5)?

int mystery(int n): if n <= 2: return 3 return mystery(n-3) + 2*mystery(n-1) - mystery(n-2)

A.

11

B.

21

C.

28

D.

None of these

Which of the following is FALSE about recursion?

A.

All recursive programs can be converted into equivalent iterative programs.

B.

It is more convenient to trace a recursive program in a bottom-up manner, compared to top-down.

C.

The top-down tracing method is closer to the actual order of executation of a recursive program.

D.

Compared to iterative solutions with loops, recursive solutions typically use less memory.