3. Algorithms and Problem Solving

Recursion — Quiz

Test your understanding of recursion with 5 practice questions.

Practice Questions

Question 1

What is the output of the following recursive function when called with input 4? $$\text{func}(n) = \begin{cases} 2 & \text{if } n=0 \\ 3 + \text{func}(n-1) & \text{if } n>0 \end{cases}$$

Question 2

Which of the following recursive functions correctly computes the product of all elements in an array $A$ of length $n$?

Question 3

Consider the following recursive function for computing the greatest common divisor (GCD) of two numbers $a$ and $b$: $$\text{gcd}(a, b) = \begin{cases} a & \text{if } b=0 \\ \text{gcd}(b, a \mod b) & \text{if } b>0 \end{cases}$$. What is the value of $\text{gcd}(48, 18)$?

Question 4

Which of the following best describes the time complexity of a recursive function that computes the $n$th Fibonacci number using the naive recursive approach (without memoization)?

Question 5

Consider the following recursive function: $$\text{sumEven}(n) = \begin{cases} 0 & \text{if } n=0 \\ n + \text{sumEven}(n-2) & \text{if } n>0 \end{cases}$$. What is the value of $\text{sumEven}(6)$?