Back

Question: 2019 Fall Midterm - 13

Author: Michiel Smid
Consider the following recursive algorithm $\Fib$, which takes as input an integer $n \geq 0$:

$\Fib(n):$
$\quad \mathbf{if}\ n = 0\ \mathrm{or}\ n = 1\ \mathbf{then}$
$\quad \quad f = n$
$\quad \mathbf{else}$
$\quad \quad f = \Fib(n - 1) + \Fib(n - 2)$
$\quad \mathbf{return}\ f$

When running $\Fib(12)$, how many calls are there to $\Fib(8)$?
(a)
6
(b)
7
(c)
4
(d)
5