Solution: 2019 Fall Final - 10

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

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

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