Solution: 2018 Fall Midterm - 14

Consider the recursive algorithm $\Fart$, which takes as input an integer $n \geq 0$:

$\mathbf{Algorithm}\ \Fart(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ \text{eat one can of beans}$
$\mathbf{else}\ \mathbf{if}\ n\ \mathrm{is}\ \mathrm{even}$
$\elsesp \mathbf{then}\ \text{fart once};$
$\elsesp \thensp \Fart \left( n \middle/ 2 \right)$
$\elsesp \mathbf{else}\ \Fart(n + 1);$
$\elsesp \elsesp \text{fart once};$
$\elsesp \elsesp \Fart(n - 1)$
$\elsesp \mathbf{endif};$
$\mathbf{endif}$

If you run algorithm $\Fart(9)$, how many times do you fart?