Discrete Math/Computer Science Fibonacci problem

Question

me and my math group are trying to find out this problem for our exam. We have to to find a fibonacci recurrence for this pseudocode and how many times the function Pow() is called. Here is the problem specifically. Hopefully point us in the right direction.

Answer 1

Start with small examples. For inductive/recursive problems you need them for your base case anyway, plus in most of the math I've seen working with small problems gives you the experience you need to figure out the general pattern.

For convenience, let $f(n)$ denote the number of times $\text{Pow}$ is called to compute $\text{Pow}(n)$. You don't really need to do this, but I'm super lazy and don't want to write that horrendously long phrase every time.

• What's $f(0)$? Well, when we call $\text{Pow}(0)$ we're in case #2 and immediately exit, so we only call $\text{Pow}$ once. In other words, $f(0)=1$.
• Similarly, $f(1)=1$.
• When we get up to $2$ things get a little more interesting. We call $\text{Pow}$ once and find ourselves in case #4. Then, we call $\text{Pow}(2-1)$ and $\text{Pow}(2-2)$. What's interesting is that we really don't care how those are computed -- we immediately know that whatever the number happens to be we have a total of $1+f(2-1)+f(2-2)$ calls to $\text{Pow}$. Since we've already computed $f(1)$ and $f(0)$, we'll actually add those up now to get $f(2)=3$.

As you said, this is a homework problem that ends with the recurrence formula and not with a closed-form solution, so I'm not going to go any further in my explanation. Keep working with a few small examples if this isn't enough to get started, but hopefully the pattern is clear by now.