long fibr (int n) { // Recursive Fibonacci generator // fibr (46) is largest val

Question

long fibr (int n) { // Recursive Fibonacci generator // fibr (46) is largest value that fits in a long Assert ( (n > 0) && (n < 47), "Input out of range"); if ( (n == 1) || (n == 2) return 1; // Base cases return fibr(n-1) + fibr(n-2); // Recursion }

Data Structures and Algorithm Analysis in C++ by Clifford Shaffer This algorithm turns out to be very slow, calling Fibr a total of Fib(m) times. Contrast this with the following iterative algorithm: long fibi (int n) Iterative Fibonacci generator ert (46) is largest value that fits in a long (in 0) (n 47), Input out of range") long past prev, curr; store temporary values past prev curr 1; initialize for (int i 3 n; it Compute next value past. prev past holds fibi (i-2) prev curr prev holds fibi (i-1) curr Past previ curr now holds fibi (i) return curr Function Fibi executes the for loop m 2 times (a) Which version is easier to understand? Why? (b) Explain why Fibr is so much slower than Fibi.

Explanation / Answer

1.Fibi executes for loop n-2 times this is recursive implementation when fibi executes for loop n times this iterative implementation

2.As per big O notation fibi(n) , fibi is slower than fibr because execution for loop is greater than fibi for loop n-2 times

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.