Fibonacci Numbers are numbers defined mathematically as
n = n_1 + n_2
where n_1 and n_2 are the two number preceding n in the sequence.
Because the nth number in the sequence is entirely dependent on the
two previous numbers, recursion is an excellent solution for building an algorithm to
provide its user with the numbers in the sequence.
Let's look at some code that solves Fibonacci Numbers using recursion.
//includes
#include <iostream>
//namespace
using namespace std;
//forward declaration (recursive fibonacci algorithm)
int fibonacci(int, unsigned long&);
//MAIN FUNCTION
int main(){
//local variables
int input;
unsigned long temp;
//get max nth number from user
cout << "enter a number for n: ";
cin >> input;
//call fibonacci numbers to nth number where n is the user input
if(input > 0){
for(int i=1; i<=input; i++)
//print current nth fibonacci number to the screen
cout << fibonacci(i, temp) << endl;
}
//hold screen for user
system("pause");
//exit
return 0;
}
//fibonacci function
//gets nth fibonacci number using recursion
int fibonacci(int term, unsigned long& n_2){
unsigned long temp, temp2;
//if n is greater than 1, use recursion to find nth fiboncacci number
if(term > 1){
// n = (n-1) + (n-2)
temp2 = fibonacci(term-1, n_2);
temp = n_2;
n_2 = temp + temp2;
} else {
//if n is zero or one (first two numbers in sequence), fibonacci number is 1
n_2 = 1;
return 1;
}
return temp;
}
|
