Back

Question: 2013 Fall Midterm - 12

Author: Pat Morin
Consider the recursive algorithm $\Fib$, which takes as input an integer $n \geq 0$:

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

When running $ FIB(5) $, how many calls are there to $ FIB(2) $?
(a)
$3$
(b)
$1$
(c)
$2$
(d)
$4$