nth Fibonacci number using recursion
Hi :)
I have done the following code to find the Nth Fibonacci number. It works. But now I need to do find the Nth Fibonacci number using recursion. How do I do this?
I found the following link but still couldn't understand what to do? Please help me. Thanks a lot.
Link: Recursive Fibonacci Sequence - C++ - Source Code | DreamInCode.net
Code:
// fibo_recursion_simple.cpp
// finding nth Fibonacci number
#include <iostream>
#include <cstdlib>
using namespace std;
unsigned long fibo(unsigned long n);
int main()
{
int n;
unsigned long answer;
cout << "which Fibonacci number to find, e.g 5th,: ";
cin >> n;
answer = fibo(n);
cout << n << "th Fibonacci number is: " << answer << endl;
system("pause");
return 0;
}
//------------------------------------------------------
// fibo() definition
unsigned long fibo(unsigned long n)
{
if (n >= 3)
{
// fibo(n) = fibo(n-1) + fibo(n-2)
const unsigned long limit = 4294967295;
unsigned long next_to_last = 0;
unsigned long last = 1;
int i = 0;
while( next_to_last < limit/2 )
{
long new_last = next_to_last + last;
next_to_last = last;
last = new_last;
i = i++;
if ( i == n )
{
break;
}
}
return (next_to_last);
}
else
{
return 1;
}
}