this recursion behavior baffles me

This is a discussion on this recursion behavior baffles me within the C Programming forums, part of the General Programming Boards category; I have a questions in regards to what is happening to this code wile debugging. Code: #include <stdio.h> #include <stdlib.h> ...

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    42

    this recursion behavior baffles me

    I have a questions in regards to what is happening to this code wile debugging.
    Code:
        #include <stdio.h>
        #include <stdlib.h>
    
    
        void a(int x){
            if (x >= 5) {
                a(x-5);
                printf("%i\n", x);
            }
        }
        
        int main(){
            a(25);
            system("pause");
        }
    I understand that func a calls itself with x-5 until the value of x is 0, when x==0 the if statement does not execute any code within the block and the next line to execute is the ending brace of the function. This is where Im confused. I would expect the function to end and return to main but the compiler then points to a(x-5) then the printf and then the function end brace. It does this 5 times, printing out 5, 10, 15, 20 and 25. I know the first in, first out is why the values get printed out in reverse order but I would love to know the reasoning behind the function not exiting when the if statement returns false because the printf is within the if's block.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,181
    Remember, the first call to a calls the next call to a. Therefore, when the next call to a returns, it returns to the first call to a, not to the main function. It is the first call to a that returns to the main function.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jan 2013
    Posts
    42
    Ok, that makes sense but what is it that makes the compiler execute the remaining code 5 times. Is it because each call remains on the stack and that is how it knows how many times to execute remaining code?
    Last edited by generaltso78; 04-18-2013 at 10:43 AM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,181
    Yes.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    I would love to know the reasoning behind the function not exiting when the if statement returns false because the printf is within the if's block.
    It does exit - but only when the escape condition is met - for all the other calls you are going 'down' another layer - like russian dolls, until you get to the call where x < 5 - then each call is exited succesively back to the original call which exits to main()


    maybe this example helps to visualise it, the code used is purely for illustration, I dont recommend writing something this way! ... the opening braces of the while loop are analgous to the recursive calls going 'down' (as i picture it) until the recursion depth limit is met and then the closing braces represent the exits being met and coming back out of the stack

    Code:
    #include <stdio.h>
    
    void CountDown(int x)
    {
       while(x >= 5)
        {
            x -= 5;
            printf("%d\n", x);
    
            while(x >= 5)
            {
                x -= 5;
                printf("%d\n", x);
    
                while(x >= 5)
                {
                    x -= 5;
                    printf("%d\n", x);
    
                    while(x >= 5)
                    {
                        x -= 5;
                        printf("%d\n", x);
    
                        while(x >= 5)
                        {
                            x -= 5;
                            printf("%d\n", x);
                        }
                    }
                }
            }
        }
    }
    int main()
    {
    
        int x = 25;
    
        printf("%d\n", x);
    
        CountDown(x);
    
        return 0;
    }
    Last edited by rogster001; 04-18-2013 at 01:59 PM. Reason: had written some C++
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  6. #6
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    and then the function end brace
    Ah - I think you have been using 'step' in the debugger - that's fine but with recursion it will kid you- you are at the closing brace.. but try using 'step into' when at the point of entry into the nested call - experiment with a breakpoint just on the call and then use step in - stuff like that - you should then be able to follow more exactly the flow
    Last edited by rogster001; 04-18-2013 at 01:49 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  7. #7
    Registered User
    Join Date
    Jan 2013
    Posts
    42
    Yes, I was using the step over command within the debugger. I did also try to use the step into command when the line being pointed to was a recursive call but never got any different order to the next line of code to be executed. I had to see it execute in a step by step motion because I would have never guessed that the printf would print anything at all based on what we had learned in C up to this point.

    p.s Thanks all, I am definitely still not knowledgeable using recursion but I do understand it better now.

    Thanks,

    Mike

  8. #8
    Registered User
    Join Date
    Jan 2013
    Posts
    42
    The strange thing is that 25, 20, 15, 10, 5, 0 passed during the recursive calls. The outputs prints out 5, 10, 15, 20, 25. I understand this is due to first in first out on the stack, but I dont understand why the printf doesnt output 5, 5, 5, 5, 5. There doesn't seem to any line of code which increments the value of x or a pointer to x, yet the value of x changes durring each iteration.
    Last edited by generaltso78; 04-18-2013 at 02:41 PM.

  9. #9
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    It is because you have put your recursive call before the printf(..) statement. - If you can understand the flow correctly, you will not escape to reach that point until the escape is reached, at which point 'that' function call exits to its calling point - and x will equal the local value of the frame it was called from - 5 - - then on the next escape up x will equal 10 which is what it was local to that call... etc

    That in mind it kind of breaks my code example earlier - but i just wanted to show a visual code pattern more than the out commands. - If i had put the print statements after the closing braces of the loops it would have stood up though. - But now i cant edit post :-(
    Last edited by rogster001; 04-18-2013 at 04:02 PM. Reason: read code incorrectly
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  10. #10
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    Quote Originally Posted by generaltso78 View Post
    The strange thing is that 25, 20, 15, 10, 5, 0 passed during the recursive calls. The outputs prints out 5, 10, 15, 20, 25. I understand this is due to first in first out on the stack, but I dont understand why the printf doesnt output 5, 5, 5, 5, 5. There doesn't seem to any line of code which increments the value of x or a pointer to x, yet the value of x changes durring each iteration.
    The value of x isn't actually changing. Each call to a() creates its own variable called x (the parameter is passed by value, meaning the function gets a copy of what was provided to the function call). Each of the 6 calls to a() will have its own variable, with a separate value. Those values never actually change.

    main() calls a with x = 25
    a calls a with x = 20
    a calls a with x = 15
    a calls a with x = 10
    a calls a with x = 5
    a calls a with x = 0

    The thing is, those are six different function calls and six different variables allocated. The sixth (deepest) function call doesn't print, it just returns control to the fifth call of a, which prints its value of x (5), then returns control to the fourth call of a, which prints its value of x (10), then returns control to the third call of a, etc., until eventually the first call of a prints its value of x (25) and returns control to main.

    If you passed a pointer to x (and altered how you were decrementing x), then each of the 6 calls to a() would have their own pointers, but they would all point to the same data, and you'd print the same value five times.
    Last edited by Cat; 04-18-2013 at 04:52 PM.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  11. #11
    Registered User
    Join Date
    Nov 2012
    Posts
    1,220
    Maybe your function would be easier to follow the flow onscreen if you print one message when you start and one message when you leave, something like

    Code:
    void a(int x) {
    	printf("started a(%d)\n", x);
    	if (x >= 5) {
    		a(x-5);
    	}
    	printf("ended a(%d)\n", x);
    }

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    1,322
    You could also include the level of recursion:

    Code:
    int recursion_level = 0;
    
    void a(int x) {
        printf("started a(%d), recursion level %d\n", x, recursion_level);
        if (x >= 5) {
            recursion_level += 1;
            a(x-5);
        }
        recursion_level -= 1;
        printf("ended a(%d), recursion level %d\n", x, recursion_level);
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Different behavior of gcc 3.x and 4.x
    By Sean M in forum C++ Programming
    Replies: 10
    Last Post: 08-10-2012, 03:49 PM
  2. Replies: 2
    Last Post: 04-08-2012, 11:32 AM
  3. Odd printf behavior?
    By tallen387 in forum C Programming
    Replies: 4
    Last Post: 04-10-2011, 09:35 AM
  4. Unexplainable behavior...
    By wpcarro in forum C Programming
    Replies: 6
    Last Post: 01-06-2011, 06:15 PM
  5. OT:Sorry for my rude behavior
    By moussa in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 06-03-2008, 07:20 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21