Problem 5 In lecture, we have seen one implementation of generating Fibonacci nu
ID: 667707 • Letter: P
Question
Problem 5 In lecture, we have seen one implementation of generating Fibonacci numbers, as follows: This implementation is correct, but not very efficient. The reason is that two recursive function calls are made at each induction step. a) (3pt) Given the implementation above, how many function calls (including recursive ones) of fib is made for an arbitrary integer n > or = to 1? Provide your answer and justify it. For example, when n = 3, the answer is 3, which includes one top-level call (fib 3) and two recursive function calls (fib 2) and (fib 1) when (fib 3) is computed. b) Define a recursive function fib Fast. which makes only one recursive call at each induction step. c) (2pt) Given fib Fast, how many calls (including recursive ones) to fib Fast is made for an arbitrary integer n > or = to 1?Explanation / Answer
(define (fib n)
(cond ((= n 1) 1 )
(( = n 2 ) 1 )
(#t ( + (fib ( - n 1 ) ( fib ( -n 2 )))))
Here
Let f(n) be the number of calls made to calculate fib(n).
If n < 2 then f(n) = 1.
Otherwise, f(n) = 1 + f(n - 1) + f(n - 2).
So, f is at least O(fib(n)). In fact, f(n) is 2 * fib(n) - 1. We show this by induction:
Base cases (n < 2, that is, n = 0 or n = 1):
f(n) = 1 = 2 * 1 - 1 = 2 * fib(n) - 1.
Induction step (n >= 2):
f(n + 1) = f(n) + f(n - 1) + 1
f(n + 1) = 2 * fib(n) - 1 + 2 * fib(n - 1) - 1 + 1
f(n + 1) = 2 * fib(n + 1) – 1
(define (fib n)
(cond ((= n 1) 0 )
(( = n 2 ) 1 )
(#t (fib ((0),(1),( - n 1 ))))
Java Implementation:
public class fibonacci
{
public static void main(String args[])
{
int a = 10;
for(int i=1;i<=a;i++)
System.out.println(fibonacci(0,1,i));
}
static int fibonacci(int first, int second, int n)
{
if(n == 1)
return first;
else if(n == 2)
return second;
else
return fibonacci(second, first+second, n-1);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.