Consider the following function:

The number of function invocations for evaluating fun(16) is _

# Functions (algo)

given solution:

We can clearly see that the function fun() generates the nth Fibonacci number. Let f(n) be the number of function calls made to compute fun(n).

f(n) = 1, n < 2

2*fun(n+1)-1, n>=2
Let’s write the number series fun(17) generates
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597.
So, f(16) = 2*fun(17)-1 = 2*1597 - 1 = 3193

**Ashok_R**#5

No No you are evaluating the function value , but the question is about the number of function invocations

No he is right…

he evaluate the number of function calls using the mathematical equation.

here f(16) indicates number of function calls and fun(17) indicates result of the function when n=17.

if you want more about this go through this link http://vulms.vu.edu.pk/Courses/CS201/Downloads/p60-robertson.pdf