Suppose that a recursive routine were invoked to calculate F(4). How many times would a recursive call of F(1) occur?



Asked on

2 Answers | Add Yours

lfryerda's profile pic

Posted on

Although you haven't said so explicitly, it seems as though you are talking about Fibonacci sequences, since the usual notation for that in Mathematics/Computer Science classes is F(n), and the routines are recursive.  The Fibonacci sequence is defined as:

`F(n)=F(n-1)+F(n-2)` , where `F(2)=1` and `F(1)=1` .

which means that 


And we can see that the recursive calls continue as


This means that the call of `F(1)=1` is called only once.

winnie7's profile pic

Posted on

F(4) = F(3) + F(2)

       = F(2) + F(1) + F(1) + F(0)

       = F(1) + F(0)+ F(1) + F(1) + F(0)

       = 3F(1) + 2F(0)

So, it gets call 3 times.

We’ve answered 288,567 questions. We can answer yours, too.

Ask a question