September 8, 2013

Fibonacci Numbers using Recursion

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.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
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;
}

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


2 comments:

ShareThis