Let \(f(n)\) be a function defined, for any integer \(n \ge0\), as follows: \[f(n)= \begin{cases} 1 & \text{if } n=0,\\ (f(n/2))^2 & \text{if $n>0$ and $n$ even,}\\ 2f(n-1) & \text{if $n>0$ and $n$ odd.} \end{cases}\]
- 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)\).
- What is the recursion depth of \(f(5)\)?
On our way to calculating \(f(5)\), we also had to calculate \(f(4)\), \(f(2)\), \(f(1)\) and \(f(0)\), so the recursion depth is \(4\).
If we write down the first few terms of the sequence \(f(n)\), it appears that \(f(n) = 2^n.\)
We have the sequence defined by \(u_{2n} = (u_n)^2, u_{2n-1} = 2u_n, u_0 = 1,\) and it is easy to show using induction that \(u_n = 2^n\).
So we could get this sequence more simply by defining \(u_n = 2u_{n-1}\) for all \(n\), \(u_0 =1.\)
This definition, however, has a larger recursion depth than the one in the question.
Now let \(g(n)\) be a function, defined for all integers \(n \ge 0\), as follows: \[g(n)= \begin{cases} 0 & \text{if } n=0,\\ 1+g(n/2) & \text{if $n>0$ and $n$ is even,}\\ 1+g(n-1) & \text{if $n>0$ and $n$ is odd.} \end{cases}\]
- What is \(g(5)\)?
- What is \(g(2^k)\), where \(k \ge 0\) is an integer? Briefly explain your answer.
\(2^k\) is even for all \(k>0\), and \(2^0=1\), which is odd, therefore:
\[\begin{align*} g(2^k) &= 1+g(2^{k-1})\\ &=1+(1+g(2^{k-2}))\\ &=\\ &\qquad\vdots\\ &=k+g(2^0)\\ &=k+g(1)\\ &=k+1. \end{align*}\]- What is \(g(2^l+2^k)\), where \(l> k \ge 0\) are integers? Briefly explain your answers.
As above, \(2^l\) and \(2^k\) are both even for \(l,k>0\), so
\[\begin{align*} g(2^l+2^k)&=1+g(2^{l-1}+2^{k-1})\\ &=\\ &\qquad \vdots\\ &=k+g(2^{l-k}+1)\\ &=k+1+g(2^{l-k})\\ &=k+1+(l-k+1)\\ &=l+2. \end{align*}\]To explain the above; when \(k=0\), \(2^k=1\) so we need to calculate \(g(2^{l-k}+1)\). This has an odd input, so the output is \(1+g(2^{l-k})\). We can then use our answer from (iv), finding \(g(2^{l-k})=(l-k)+1\) and simplify our expression.
It is interesting to reflect on how \(g(n)\) works if \(n\) is written in binary.
The rule for \(g\) tells us that if \(n\) is even, \(g(n)\) is \(1 + g(n/2)\), that is, \(1\) + the binary number given by removing the \(0\) at the end of \(n\).
If \(n\) is odd, \(g(n)\) is \(1 + g(n-1)\), that is, \(1 +\) the binary number given by changing the final \(1\) to a \(0\).
Suppose \(n\) in binary has \(j\) 1s and \(k\) 0s. It is easy to see, therefore, that \(g(n)\) is \(2j + k - 1\) (the \(-1\) comes in because we don’t remove the final \(0\)).
- Explain briefly why the value of \(g(n)\) is equal to the recursion depth of \(f(n)\).
Imagine calculating \(f(n)\) and \(g(n)\) at the same time, so we take it in turns to carry out one step in the calculation.
With every step we carry out on \(f(n)\) we create an expression in terms of \(f(c)\) where \(c\) is an integer less than \(n\).
With each corresponding step for \(g(n)\), we make \(g(n)\) the sum of \(g(c)\) and the total number of steps we’ve taken so far (this is equal to the number of different \(c\) values we’ve used so far).
Eventually we’ll reach an expression for \(f(n)\) in terms of \(f(0)\), and \(g(n)=g(0)+\text{(number of values of c used)}=0+\text{(number of values of c used)}\).
That is, \(g(n)\) is the recursion depth of \(f(n)\).
