1 reply to this topic

[jackson6612]

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

// 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;

    }

}

[Alexander]

Essentially you must calculate the Fibonacci sequence (much as you are in the while loop), instead of assigning variables to the new sequence such as next_to_last, you will pass it to itself.

In very simple code:

fibo(n) {
   check n here
   calc = next sequence in algorithm
   return fibo(calc)
}

And it will recursively call itself until the checks tell it to return (if n >= 3 for example, although you may need to make sure the checks are right), when the sequence is completed the very first step of fibo will return the result.

As a side note, you should always include <limits.h> and use ULONG_MAX instead of 4294967295. This will represent the safe maximum of which the compiler specifies.