Fibonacci Recursive and Non Recursive C++

Required Background

Basic knowledge of C++.

Using the Code

The code has been tested on Linux (Fedora13) platform. Users interested in running the code, please recompile using the C++ compiler on your system.

There are two class files and a program.cpp having the main function. The class files FibonacciNR.h / FibonacciNR.cpp implement Fibonacci numbers non-recursively. FibonacciR.h / FibonacciR.cpp has the recursive implementation.

Points of Interest

Complexity involved in recursive methods. Recursions can add significant overhead.

A non recursive implementation eliminates repeated calculation of Fibonacci numbers. This is a huge gain.

Users interested in the complexity of the two implementations can add the following code at the end of the method FibonacciR::Fibonacci().

std::cout<<*n_<<"th fibonaci number: "<<Fibonacci(n-1) + Fibonacci(n-2)<<std::endl;

Note: How the recursive implementation repeats the calculation of Fibonacci numbers. This no doubt can be avoided building an archive of fibonacci as and when they are calculated. Nevertheless the archive adds space and complexity.

The Non Recursive version is much cleaner and faster.

History

First release 1.0.1009.12

FibonacciNR.h

  1  /*
 2   * FibonacciNR.h
 3   *
 4   *  Created on: Sep 11, 2010
 5   *      Author: julian
 6   */
 7
 8  #ifndef FIBONACCINR_H_
 9  #define FIBONACCINR_H_
10
11  class FibonacciNR {
12  public:
13     FibonacciNR(const int &n);
14     virtual ~FibonacciNR();
15     void PrintFibonacci();
16  private:
17     FibonacciNR();
18     int Fibonacci(const int &n);
19     const int* n_;
20  };
21
22  #endif /* FIBONACCINR_H_ */

FibonacciNR.cpp

1  /*
 2   * FibonacciNR.cpp
 3   *
 4   *  Created on: Sep 11, 2010
 5   *      Author: julian
 6   */
 7
 8  #include "FibonacciNR.h"
 9  #include <iostream>
10
11  FibonacciNR::FibonacciNR() {
12
13  }
14
15  FibonacciNR::FibonacciNR(const int &n):n_(&n){
16
17  }
18
19  FibonacciNR::~FibonacciNR() {
20  }
21
22  int FibonacciNR::Fibonacci(const int &n)
23  {
24     int first =0;
25     int second=1;
26     int counter=2;
27     while(counter < n)
28     {
29         int temp=second;
30         second=first+second;
31         first=temp;
32         ++counter;
33     }
34     if(n==0)
35         return 0;
36     else
37         return first+second;
38  }
39  void FibonacciNR::PrintFibonacci(){
40     const int result = Fibonacci(*n_);
41     std::cout<<*n_<<"th fibonacci Number:"<<result<<std::endl;
42  }

FibonacciR.h

 1  /*
 2   * FibonacciR.h
 3   *
 4   *  Created on: Sep 10, 2010
 5   *      Author: julian
 6   */
 7
 8  #ifndef FIBONACCIR_H_
 9  #define FIBONACCIR_H_
10
11  class FibonacciR {
12  public:
13     FibonacciR(const int &n);
14     virtual ~FibonacciR();
15     void PrintFibonacci();
16  private:
17     FibonacciR();
18     int Fibonacci(const int &n);
19     const int *n_;
20  };
21
22  #endif /* FIBONACCIR_H_ */

FibonacciR.cpp

1  /*
  2   * FibonacciClass1.cpp
  3   *
  4   *  Created on: Sep 10, 2010
  5   *      Author: julian
  6   */
  7  
  8  #include "FibonacciR.h"
  9  #include <iostream>
 10  
 11  FibonacciR::FibonacciR() {
 12  }
 13  
 14  FibonacciR::FibonacciR(const int &n):n_(&n){
 15  }
 16  
 17  FibonacciR::~FibonacciR() {
 18  }
 19  
 20  int FibonacciR::Fibonacci(const int &n){
 21  	if(n==0)
 22  		return 0;
 23  	else if(n==1)
 24  		return 1;
 25  	return Fibonacci(n-1) + Fibonacci(n-2);
 26  }
 27  void FibonacciR::PrintFibonacci(){
 28  	int FibonaciNum=Fibonacci(*n_);
 29  	std::cout<<*n_<<"th fibonaci number: "<<FibonaciNum<<std::endl;
 30  }

Program.cpp

1  /*
 2   * Program.cpp
 3   *
 4   *  OS: Fedora 13
 5   *  Language: Native C++
 6   *  Compiler: GNU g++
 7   *  Created on: Sep 11, 2010
 8   *      Author: julian
 9   */
10
11  #include <iostream>
12  #include <stdlib.h>
13  #include "FibonacciR.h"
14  #include "FibonacciNR.h"
15  using namespace std;
16  void Usage(){
17     cout<<"Correct Usage:"<<endl;
18     cout<<"./Fibonacci [n]"<<endl;
19  }
20  int main(int argc, char** args) {
21     try{
22         const char* input; //Note: char by default initializes to '\0'
23         if(args[1]!=0)
24         {
25             cout<<"1st passed arguement: '"<<args[1]<<"'"<<endl;
26             input= args[1];
27         }
28         int n= atoi(input);
29         cout<<"Finding '"<<n<<"'th "<<"fibonacci number...."<<endl;
30         cout<<"Calling Recursive Fibonacci implementation"<<endl;
31         FibonacciR fr(n);
32         fr.PrintFibonacci();
33         cout<<"Calling Non-Recursive Fibonacci implementation"<<endl;
34         FibonacciNR fnr(n);
35         fnr.PrintFibonacci();
36         cout << "Done!!!!" << endl;
37         return 0;
38     }
39     catch(...)
40     {
41         cout<<"Oops an error occured! Please check usage"<<endl;
42         Usage();
43         return 1;
44     }
45  }