Question

In: Computer Science

Part 1: Write a recursive function that will calculate Fibonacci numbers using a recursive definition. Write...

Part 1: 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 F(n)

Part 2: 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 F(n).

Part 3: 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 and find their running times. For part (E) of this project you will have to run this program multiple times to find out how the running time of each function depends on the value of n

Part 4: This part of the project is a written analysis of two algorithms of calculating Fibonacci numbers: recursive (part 1) and iterative (part 2). Show the theoretical order of growth of the running time for both algorithms. Then include experimental results based on part (3) and explain them

Write the Test programs in C..

Solutions

Expert Solution

Solution:

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

Fn = Fn-1 + Fn-2

with seed values

   F0 = 0 and F1 = 1.

Code:

//Fibonacci Series using Recursion

#include<stdio.h>

int fib(int n)

{

   if (n <= 1)

      return n;

   return fib(n-1) + fib(n-2);

}

int main ()

{

  int n = 9;

  printf("%d", fib(n));

  getchar();

  return 0;

}

Output:34

Part-2:

#include<stdio.h>
int main()
{
int first=0, second=1, i, n, sum=0;
printf("Enter the number of terms: ");
scanf("%d",&n);
//accepting the terms
printf("Fibonacci Series:");
for(i=0 ; i<n ; i++)
{
if(i <= 1)
{
sum=i;
}
//to print 0 and 1
else
{
sum=first + second;
firs}t=second;
second=sum;
//to calculate the remaining terms.
//value of first and second changes as new term is printed.
}
printf(" %d",sum)
}
return 0;

Output:01123


Related Solutions

Write a MIPS assembly program to calculate the Fibonacci numbers from 1..n using the recursive method....
Write a MIPS assembly program to calculate the Fibonacci numbers from 1..n using the recursive method. The definition of a Fibonacci number is F(n) = F(n-1) + F(n-2). The implementation must follow the following guidelines: Prompt the user for a number n Allocate heap memory to hold the exact number of elements in the Fibonacci sequence for n Implement recursive Fibonacci method as a subprogram Print the Fibonacci sequence array
. (a) Write a C++ program to find Fibonacci numbers. (For the definition of Fibonacci numbers...
. (a) Write a C++ program to find Fibonacci numbers. (For the definition of Fibonacci numbers and the recursive formula please refer to problem 5 of Chapter 2 at page 81 in the text-book.) The program asks the user to input an integer and outputs the corresponding Fibonacci number. For example, if the user inputs 4, the program outputs the fifth Fibonacci number, which is 3. Introduce two local variables in the recursion function (suppose we call it fib(n)), one...
Python: Using Jupyter Notebook 1. Write code to generate Fibonacci series. Fibonacci numbers – 1, 1,...
Python: Using Jupyter Notebook 1. Write code to generate Fibonacci series. Fibonacci numbers – 1, 1, 2, 3, 5, 8, … 2. Check if a number is an Armstrong number A positive integer is called an Armstrong number of order n if abcd... = a^n + b^n + c^n + d^n + ... In case of an Armstrong number of 3 digits, the sum of cubes of each digits is equal to the number itself. For example: 153 = 1*1*1...
In this assignment, you will calculate and print a list of Fibonacci Numbers . Fibonacci numbers...
In this assignment, you will calculate and print a list of Fibonacci Numbers . Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones: The sequence Fn of Fibonacci numbers is defined by the recurrence relation:  which says any Nth Fibonacci number is the sum of the (N-1) and (N-2)th Fibonacci numbers. Instructions Your task will be...
Determine if each of the following recursive definition is a valid recursive definition of a function...
Determine if each of the following recursive definition is a valid recursive definition of a function f from a set of non-negative integers. If f is well defined, find a formula for f(n) where n is non-negative and prove that your formula is valid. f(0) = 1, f(n) = -f(n-1) + 1 for n ≥ 1 f(0) = 0, f(1) = 1, f(n) = 2f(n-1) +1 for n ≥ 1 f(0) =0, f(n) = 2f(n-1) + 2 for n ≥...
Provide a recursive definition of some sequence of numbers or function (e.g. log, exponent, polynomial). Choose...
Provide a recursive definition of some sequence of numbers or function (e.g. log, exponent, polynomial). Choose one different from that of any posted thus far. Write a recursive method that given n, computes the nth term of that sequence. Also provide an equivalent iterative implementation. How do the two implementations compare?
In Python Write a Fibonacci class to calculate next number in the 'Fibonacci' class by the...
In Python Write a Fibonacci class to calculate next number in the 'Fibonacci' class by the 'nxt' method. In this class, the 'val' member is a Fibonacci number. The 'nxt' method will return a 'Fibonacci' object whose value is the next number in Fibonacci series. class Fibonacci (): """A Fibonacci number. >>>a = Fibonacci(): >>>a 0 >>>a.nxt() 1 >>>a.nxt().nxt() 1 >>>a.nxt().nxt().nxt() 2 >>>a.nxt().nxt().nxt().nxt() 3 >>>a.nxt().nxt().nxt().nxt().nxt() 5 >>>a.nxt.nxt().nxt().nxt().nxt().nxt() 8 """ def __init__(self): self.val = 0 def nxt(self): """YOUR SOURCE CODE HERE"""...
In java, Write a recursive function to calculate the sum of the nodes only on even...
In java, Write a recursive function to calculate the sum of the nodes only on even levels of the subtree. please do not add any parameters to do this function. private int sumEvenLevels(Node current){ //you can only pass in root. //code }
Define the following function f(n) = 5(2^n)-(2^(n-1)), n ≥ 1. Write a recursive definition for the...
Define the following function f(n) = 5(2^n)-(2^(n-1)), n ≥ 1. Write a recursive definition for the function f(n)? Consider the following recurrence: an= 2an-1 + 3 (where a1 = 1). Compute the values of an for n ≤ 5. Find a solution for the recurrence definition and validate its correctness. Consider the following recurrence: an=2an-1 +an-1an-2 (where a1 = 1). Compute the values of an for n ≤ 5.
Write a recursive function to calculate and return factorial of a given number 'n'. in C...
Write a recursive function to calculate and return factorial of a given number 'n'. in C progrmaining
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT