Thread: nth Fibonacci number using recursion

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    254

    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;
        }
    }
    I'm an outright beginner. Using Win XP Pro and Code::Blocks. Be nice to me, please.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    So now that you've found the answer, instead of trying to coming up with it on your own you, you'd like to put some time into understanding how it works before doing a copy and paste?
    I think the code is pretty self-explanatory. If there's any bit you can't work out, just ask questions about it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    254
    Hi

    Quote Originally Posted by iMalc View Post
    So now that you've found the answer, instead of trying to coming up with it on your own you,
    Thanks for the reply. In my previous post I included the code for finding the nth Fibonacci number using the while only to show you that I know how to tackle the problem generally. I didn't (still don't) understand how to do it using recursion.

    So, you find the below given code sel-explanatory! The code given below is completely wrong. I have compiled it and run it. Please help me.

    Code:
    #include <iostream>
    
    using namespace std;
    
    long fibcalc(unsigned long n);
    
    int main()
    {
    
    	    int n;
    	    cout << "Please enter a number for the fibonacci sequence. " << endl;
    	    cin >> n;
    	    fibcalc(n);
    
    }
    
    	long fibcalc(unsigned long n)
    	{
    
    	    if (n <= 1)
    	    {
    	        cout << n;
    	        return n;
    	    }
    	    else
    	    {
    	        return fibcalc(n-1)+fibcalc(n-2);
    	    }
    
       }
    I'm an outright beginner. Using Win XP Pro and Code::Blocks. Be nice to me, please.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    If you don't do
    Code:
    cout << fibcalc(n);
    how do you have any idea what value your function is calculating?

  5. #5
    Registered User xentaka's Avatar
    Join Date
    May 2011
    Posts
    60

    lol

    I would probably get kicked out of school for this, but here is what I came up with.

    Code:
    #include <iostream>
    
    using namespace std;
    
    long fibonA(long numO, long numT, long findN, int plOne, int plTwo, int plThree) {
        long sumInt;
        sumInt = numO + numT;
        if (plOne == findN) {
            return numO;
        }
        if (plTwo == findN) {
            return numT;
        }
        if (plThree == findN) {
            return (numO + numT);
        }
        plOne += 3;
        plTwo += 3;
        plThree += 3;
    
        return fibonA((sumInt + numT), ((sumInt + numT) + sumInt), findN, plOne, plTwo, plThree);
    
    }
    
    int main() {
        long findNum, numOne = 0, numTwo = 1;
        cout << "Which number do you want to find : ";
        cin >> findNum;
        cout << endl << "The number is : " << fibonA(numOne, numTwo, findNum, 1, 2, 3) << endl;
        return 0;
    }
    EDIT: For clarity I should add that I count 0 as 1. (sequence A000045 in OEIS) off the Wikipedia page.

    Also seems from the algorithm that wikipedia gives you that they want to start at 1,2,3,5,8 ... if that's the case then I just plugged in the algorithm on the site, and it works.
    Not sure why you posted though as it took me about a minute to bring a website up with full code ( I was just curious after my laughable code above ). hehe.

    Code:
    #include <iostream>
    
    using namespace std;
    
    long fiboN(long varA)
    {
       if ((varA == 0) || (varA == 1))
          return 1;
       else
          return fiboN(varA - 1) + fiboN(varA - 2);
    }
    
    int main()
    {
    
        long checkN;
        cout << "Enter fibonacci number to check : ";
        cin >> checkN;
        cout << endl << fiboN(checkN) << endl;
        return 0;
    
    }
    Last edited by xentaka; 05-21-2011 at 10:55 PM.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by jackson6612 View Post
    The code given below is completely wrong. I have compiled it and run it. Please help me.

    Code:
    #include <iostream>
    
    using namespace std;
    
    long fibcalc(unsigned long n);
    
    int main()
    {
    
    	    int n;
    	    cout << "Please enter a number for the fibonacci sequence. " << endl;
    	    cin >> n;
    	    fibcalc(n);
    
    }
    
    	long fibcalc(unsigned long n)
    	{
    
    	    if (n <= 1)
    	    {
    	        cout << n;
    	        return n;
    	    }
    	    else
    	    {
    	        return fibcalc(n-1)+fibcalc(n-2);
    	    }
    
       }
    It's not completely wrong, the only wrong bits are the cout statement you added inside the recursive function, and a lack of outputting the value that it returned back to the call from main.

    If you want to check if a car's emission levels are okay, do you put the sensor inside one of the cylinders of the engine, or do you put it where stuff is emitted from the tailpipe?
    Last edited by iMalc; 05-22-2011 at 02:34 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Mar 2011
    Posts
    254
    Thanks a lot, tabstop, xentaka, iMalc. You guys have really helped me. I genuinely appreciate this.

    Regards
    Jackson
    I'm an outright beginner. Using Win XP Pro and Code::Blocks. Be nice to me, please.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fibonacci number help
    By anirban in forum C Programming
    Replies: 2
    Last Post: 08-24-2009, 03:20 PM
  2. fibonacci using recursion?
    By n3cr0_l0rd in forum C Programming
    Replies: 12
    Last Post: 02-25-2009, 08:49 AM
  3. Fibonacci series using recursion
    By IPCHU in forum C Programming
    Replies: 1
    Last Post: 12-07-2006, 06:05 AM
  4. The highest Fibonacci number ever calculated
    By dwks in forum C Programming
    Replies: 19
    Last Post: 07-27-2005, 05:57 PM
  5. Fibonacci using Recursion
    By jazzistoobad in forum C Programming
    Replies: 21
    Last Post: 10-04-2004, 11:06 PM