\section*{5. For ALL APPLICANTS.}
Let $f ( n )$ be a function defined, for any integer $n \geqslant 0$, as follows:

$$f ( n ) = \left\{ \begin{array} { c c } 
1 & \text { if } n = 0 \\
( f ( n / 2 ) ) ^ { 2 } & \text { if } n > 0 \text { and } n \text { is even } \\
2 f ( n - 1 ) & \text { if } n > 0 \text { and } n \text { is odd }
\end{array} \right.$$

(i) What is the value of $f ( 5 )$ ?

The recursion depth of $f ( n )$ is defined to be the number of other integers $m$ such that the value of $f ( m )$ is calculated whilst computing the value of $f ( n )$. For example, the recursion depth of $f ( 4 )$ is 3 , because the values of $f ( 2 ) , f ( 1 )$, and $f ( 0 )$ need to be calculated on the way to computing the value of $f ( 4 )$.\\
(ii) What is the recursion depth of $f ( 5 )$ ?

Now let $g ( n )$ be a function, defined for all integers $n \geqslant 0$, as follows:

$$g ( n ) = \left\{ \begin{array} { c c } 
0 & \text { if } n = 0 \\
1 + g ( n / 2 ) & \text { if } n > 0 \text { and } n \text { is even } \\
1 + g ( n - 1 ) & \text { if } n > 0 \text { and } n \text { is odd }
\end{array} \right.$$

(iii) What is $g ( 5 )$ ?\\
(iv) What is $g \left( 2 ^ { k } \right)$, where $k \geqslant 0$ is an integer? Briefly explain your answer.\\
(v) What is $g \left( 2 ^ { l } + 2 ^ { k } \right)$ where $l > k \geqslant 0$ are integers? Briefly explain your answer.\\
(vi) Explain briefly why the value of $g ( n )$ is equal to the recursion depth of $f ( n )$.