Thread: fibonnaci question...

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    255

    fibonnaci question...

    ok so i have to do a fibonnaci algorithm. not to terrible to write. however it wasnt working so i set break points all the place to see why it might be failing.

    and heres what i discovered its doing and why im confused by it.


    Code:
    int recurvsiveFibonacci(int n)
    {
    //there is a breakpoint on each of the lines of code
    	 if (n == 1 || n == 0)
    {
    		 return n;
    }
    	else{
    		return (recurvsiveFibonacci(n-1) + recurvsiveFibonacci(n-2));}
    }
    what happens is it goes through the if statement find the first two times(im reading numbers from a file and just passing the counter in as n(ya im not sure if that part of my program is being done right but can deal with that next wont do me any good if the recursion wont work properly)

    so the first two numbers i pass through are 0 and 1. it goes to the if checks it and returns it as it should. then it passes in 2 and from here on out it goes up to 9 or 10. and now anytime from passing 2 and above in as the variable n what happens is it seems to go nuts. it goes back to the if statement when it drops to 1. then goes to the return n statement and just skips over it. then goes back to the if statement where n is now 0. passes it. goes to return n and again just goes to it without returning n. then n ends up changing to some random number like 4 or maybe 7 not really sure the order of it other than my output is the same every time.

    also it might even goto the if statement as n. goto the return statement and do nothing about it. then n might change from 1 to 3.

    i seriously have no clue how or why n is changing values at seemingly random(though not random as i get the same output every time)

    if anybody can drop a hint or two or outright explain this crazyness i love that. it would be much appreciated.
    hooch

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    But does it produce the right answer?

    If the compiler has performed "tail recursion optimization" on the code, then you won't see nice recursive calls, only weird jumps and other effects.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Works perfectly for me, maybe you're doing something weird instead of printing the function's output.

    Code:
    #include <iostream>
    
    int recurvsiveFibonacci(int n)
    {
        //there is a breakpoint on each of the lines of code
        if (n == 1 || n == 0)
        {
            return n;
        }
        else
        {
            return (recurvsiveFibonacci(n-1) + recurvsiveFibonacci(n-2));
        }
    }
    
    int main()
    {
        for (int i = 0; i != 10; ++i)
            std::cout << recurvsiveFibonacci(i) << ' ';
    
        std::cout << std::endl;
    
        return 0;
    }
    Output:
    Code:
    0 1 1 2 3 5 8 13 21 34

  4. #4
    Registered User
    Join Date
    Nov 2001
    Posts
    255
    oh well i was under the impression since it jumped around all the time it was messing up. is there a reason it does this? how does that optimize it?

    lol i guess i just didnt know those were the right answers. i guess i assumed it was wrong because n was jumping all over the place. oh well would of been nice if the teacher explained hey your compiler might jump all over the place doing recursion functions.
    hooch

  5. #5
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    That's why it's better to just build a project without optimization when debugging.
    Devoted my life to programming...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 03-23-2011, 09:00 AM
  2. *szString = things question/memory question
    By Jang in forum C Programming
    Replies: 3
    Last Post: 01-20-2011, 04:59 AM
  3. Newbish Question file reading question....
    By kas2002 in forum C Programming
    Replies: 23
    Last Post: 05-17-2007, 12:06 PM
  4. Self regiserting DLLs question and libraries question.
    By ApocalypticTime in forum Windows Programming
    Replies: 2
    Last Post: 03-22-2003, 02:02 PM
  5. A question of color...(not a racial question)
    By Sebastiani in forum Windows Programming
    Replies: 7
    Last Post: 01-15-2003, 08:05 PM