Write a recursive function that will calculate Fibonacci numbers using a recursi

Question

Write a recursive function that will calculate Fibonacci numbers using a recursive definition. Write a short program to test it. The input of this program must be a positive integer N; the output is the corresponding Fibonacci number FN.

Write an iterative function to calculate Fibonacci numbers. Write a test driver for it. The input of this program must be a positive integer N; the output is the corresponding Fibonacci number FN.

Write a program that will compare running time of the recursive and iterative functions for calculating Fibonacci numbers. Call each function for the same size of input N (the index of a Fibonacci number to be calculated) and find their running times. In C and C++, you may use the function gethrtime from a C library sys/time.h.

In this part of the project, write a function that will implement each Fibonacci number with the help of an integer array of size 100 (elements of this array will be digits of the Fibonacci number). When the function is called to find , it will calculate all Fibonacci numbers from to using the basic formula . To add two Fibonacci numbers, the function will add elements of two arrays corresponding to and and store their sums in the array corresponding to . (You are NOT supposed to store ALL arrays.) Write a program that will calculate Fibonacci numbers containing up to 100 digits. Display the biggest Fibonacci number that has less than 100 digits. Make sure that your program will display the error message when a Fibonacci number has 100 digits or more.

Explanation / Answer

both solution methods

complexity O(2^n)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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