# Fibonacci Numbers using Recursion

Sunday, September 08, 2013 3 Comments

Problem:
Write a C++ program which prints the Fibonacci sequence or the Fibonacci numbers.
Fibonacci sequence is named after Leonardo Fibonacci. Fibonacci numbers starts with the first two numbers 0 and 1, and each subsequent numbers takes as the sum of its previous two numbers.

Ex. 0, 1, 1, 2, 3, 5
The first two numbers in the sequence are 0 and 1.
The 3rd number which is 1 is the sum of its previous two numbers - 0 and 1.
The 4th number which is 2 is the sum of its previous two numbers  - 1 and 1.
So on and so forth...
In mathematical equation, Fibonacci sequence can be represented as:

Fn = F(n-1) + F(n-2) where F0 = 0, F1 = 1

The following program shows the Fibonacci sequence using recursion.

```/*
Fibonacci series using Recursion
*/
#include <iostream>

using namespace std;
int fibonacci(int);

int main(void)
{
int count;
char waitInput;

cout << "How many numbers in the Fibonacci sequence do you want to show? ";
cin >> count;

for (int i = 0; i < count; i++)
{
cout << " " << fibonacci(i) << " ";
}

cin>>waitInput;

return 0;
}

//fibonacci function
int fibonacci(int num)
{
if (num == 1)
{
return 1;
}
else if (num == 0)
{
return 0;
}
else
{
return fibonacci(num - 1) + fibonacci(num - 2);
}
}
```

thnx