Solution: 2017 Fall Final - 10

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

$\mathbf{Algorithm}\ \IFeelLikeSinging(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ \mathrm{sing}\ {\it O\ Canada}$
$\mathbf{else}\ \mathbf{if}\ n\ \text{is odd}$
$\elsesp \mathbf{then}\ \IFeelLikeSinging(n + 1)$
$\elsesp \mathbf{else}\ \IFeelLikeSinging(\frac{n}{2});$
$\elsesp \elsesp \IFeelLikeSinging(\frac{n}{2} - 1)$
$\elsesp \mathbf{endif};$
$\mathbf{endif}$

If you run algorithm $\IFeelLikeSinging(9)$, how many times do you sing O Canada?