Click here to Skip to main content
11,495,524 members (66,550 online)
Click here to Skip to main content

Tagged as

Fibonacci Recursive and Non Recursive C++

, 18 Sep 2010 CPOL 17.3K 4
Rate this:
Please Sign up or sign in to vote.
Non Recursive and Recursive implementation of Fibonaci series in C++. Emphasis is on the complexity involved in the different implementations.
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  }

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

No Biography provided

Comments and Discussions

 
GeneralReason for my vote of 2 Gratuitous use of pointers and refer... Pin
Aescleal18-Sep-10 22:31
memberAescleal18-Sep-10 22:31 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.150520.1 | Last Updated 18 Sep 2010
Article Copyright 2010 by joseph.arul83@gmail.com
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid