3. Compare the number of operations and time taken to compute Fibonacci numbers

Question

3. Compare the number of operations and time taken to compute Fibonacci numbers recursively versus that needed to compute them iteratively.
4. Use the above functions to write a C++ program for solving each of the following computational problems.
I. Find the exact value of f100, f500, and f1000, where fn is the nth Fibonacci number. What are times taken to find out the exact values?
II. Find the smallest Fibonacci number (1) greater than 1,000,000, and (2) greater than 1,000,000,000.
III. Find as many prime Fibonacci numbers as you can. It is unknown whether there are infinitely many of these. Find out the times taken to find first 10, 20, 30, 40…up to 200 and draw a graph and see the pattern.

Explanation / Answer

3) The number of iterations required in recurisve function is more than compared to iterative calls.Also the speed of recursive function is slower than iterative approach and reason is in first apporach we are calling function which means keeping the current value & parameters in stack and once function call is done then return values is pushed to stack and calling function gets its state by loading state and its value from stack. Lots of store and load instructions required.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

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