Subscribe to our RSS
Fibonacci in C++
Fibonacci is a well known number sequence that models the growth of a rabbit population amongst other things found in nature.
The Fibonacci Numbers Sequence
Below is the Fibonacci numbers computed up to the 11th term.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
The formula for Fibonacci
Computing for Fibonacci is simple. The formula is below.
Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2);
To computer for Fibonacci of 7, simply add the values of Fibonacci of 6 and Fibonacci of 5. In other words, the sum of the previous two values.
Fibonacci(7) = Fibonacci(6) + Fibonacci(5);
Fibonacci(7) = 8 + 5;
Fibonacci(7) = 13;
Iterative version of Fibonacci
This is an iterative version of Fibonacci.
int fib1 = 0;
int fib2 = 1;
int fib;
for ( int i = 2; i < n; i++ )
{
fib = fib1 + fib2;
fib1 = fib2;
fib2 = fib;
}
Recursive version of Fibononacci
The recursive version of Fibonacci in C++ is below. This recursive function computes the sum of the previous two fibonacci numbers recursively.
{
if ( n == 0 ) return 0;
if ( n == 1 ) return 1;
return fib(n-1) + fib(n-2);
}
An image of how this recursive solution works is below. Each bubble is a function call.
Dynamic Programming version of Fibonacci
The dynamic programming version of Fibonacci in C++ is below. This snippet of code computes the fibonacci by traversing a vector.
vector <int> fib;
fib.push_back(0);
fib.push_back(1);
int n; //N is the number of fibonacci numbers we are going to compute.
for ( int i = 2; i < n; i++ )
{
fib.push_back( fib[i-1] + fib[i-2] );
}
Finishing remarks
So, which one do you think is the fastest version?
(1 votes, average: 5.00 out of 5)
December 19th, 2008 at 2:23 am
OnlineCompiler.org
Now You can create, run, upload, and download your C, C++ Programs/ Projects Online.
OnlineCompiler.org is a completed online development environment for C/C++ in Linuc/Unix Style and built over Php.
You can access onlineCompiler.org here. This is a joint project by CodeControl and Ajay Jain. OnlineCompiler.org has a lot of features that will make online development quite comfortable and fun. You can save your prohects over there, take a backup and retrieve it later, or may be download it. It is specially useful in cases when you need to do something and they don’t have a compiler.
Currently onlinecompiler.org supports only Unix/Linux GCC based C/C++. We are planning to introduce Python support very soon. But no official dates. :-)
July 22nd, 2009 at 11:27 am
thx 4 these full informations :)
January 18th, 2010 at 1:35 am
Tail Recursive version of Fibononacci ??
plz write for it also..