Better Students Ask More Questions.
Suppose that a recursive routine were invoked to calculate F(4). How many times would a...
2 Answers | add yours
High School Teacher
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.
Posted by lfryerda on March 31, 2013 at 8:29 PM (Answer #1)
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.
Posted by winnie7 on July 14, 2013 at 9:21 PM (Answer #2)
Join to answer this question
Join a community of thousands of dedicated teachers and students.