Homework Help

Suppose that a recursive routine were invoked to calculate F(4). How many times would a...

user profile pic

dcunfer7394 | eNoter

Posted February 21, 2013 at 11:35 AM via web

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

Tagged with math, recursive routine

2 Answers | Add Yours

user profile pic

lfryerda | High School Teacher | (Level 2) Educator

Posted March 31, 2013 at 8:29 PM (Answer #1)

dislike 1 like

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 

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

And we can see that the recursive calls continue as

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

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

user profile pic

winnie7 | eNotes Newbie

Posted July 14, 2013 at 9:21 PM (Answer #2)

dislike 0 like

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.

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes