Need help understanding a recursive function in Xcode

Discussion in 'Mac Programming' started by admo, Jan 22, 2012.

  1. macrumors member

    Joined:
    Aug 24, 2009
    #1
    In the book "Objective-C Programming), I just did an exercise where I wrote a program in C (OSX - command line) where 99 bottles of beer song is printed to the screen. Here is the code:


    Code:
    #include <stdio.h>
    
    void singTheSong(int numberOfBottles)
    {
        if (numberOfBottles == 0) {
            printf("There are simple bo more bottles of beer on the wall.\n");
        } else {
            printf("%d bottles of beer on the wall. %d bottles of  beer.\n",
                   numberOfBottles, numberOfBottles);
            int oneFewer = numberOfBottles - 1;
            printf("Take one down, pass it around, %d bottles of beer on the wall.\n",
                   oneFewer);
            singTheSong(oneFewer); // This function calls itself!
            printf("Put a bottle in the recycling, %d empty bottles in the bin.\n",
                   numberOfBottles);
        }
    }
    
    int main (int argc, const char * argv[])
    {
    
        singTheSong(99);
        
        return 0;
    }
    Now, I see how at the line
    singTheSong(oneFewer); // This function calls itself!
    the function starts over at the top, with the variable "numberOfBottles is reduced by 1 to 98, and so on all the way to 0.
    What I don't get is how once the song gets to the point where all the bottles are off the wall, the function then continues about the recycling, going from 1 all the way up to 99. For example, the first time the line is printed Put a bottle in the recycling, 1 empty bottles in the bin, I don't see how it gets to the next line of output where there are 2 bottles in the bin. I think it has something to do with the stack, and it is just popping off the variable at the top of the stack. Is this somewhat right?

    Basically, when I look at this code, I would think (incorrectly) that it counts the bottles on the wall from 99 all the way to 0, then print about putting 1 bottle in the bin, and then the program would end.

    Any help understanding how that last printf function is recursive, and am I right that it jut keeps running until all the variables in the stack are gone?
     
  2. macrumors regular

    Joined:
    Nov 30, 2005
    #2
    Recursion works like this:
    You call and a function, if some parameters allow it, the function will call itself from within, In this case if the number of beers is >0.

    Function will do this,
    Print # of bottles of beer on the wall.
    Remove one bottle.
    Take one down...
    Than calls itself, at this point the current function "Freezes" It will be the bottom Frame, and the last line of code will be the last one called. Since it was put onto the stack. You can think of last line as a stack of papers.

    So put a bottle in the recycling will layer them, the first one being at the bottom last one at the top, than when they are all done layering, they will execute. Starting from the top. Recursion is a technique to reverse the order of something.
     
  3. macrumors G5

    gnasher729

    Joined:
    Nov 25, 2005
    #3
    Change the initial call to singTheSong (2), set a breakpoint on that call, and step through the code. It will become obvious what's happening.
     
  4. macrumors 6502

    Joined:
    May 29, 2011
    Location:
    Littleton, Colorado, USA
    #4
    Each function call is unique, and none of them finish until the last one - then the whole thing unwraps, which each function call printing the recycling bit as it finishes.

    Déjà vu
     
  5. thread starter macrumors member

    Joined:
    Aug 24, 2009
    #5
    Thanks everyone. So that last line about the bottles going into the bin just keeps repeating itself until each item in the stack is gone. Very funny about that other thread from December that asked the exact same thing. Gotta search next time!
     
  6. macrumors Pentium

    KnightWRX

    Joined:
    Jan 28, 2009
    Location:
    Quebec, Canada
    #6
    C is procedural. Recursion is nothing special. Think about it as if this code was written this way instead :

    Code:
    #include <stdio.h>
    
    void singTheSong(int numberOfBottles)
    {
        if (numberOfBottles == 0)
       {
            printf("There are simple bo more bottles of beer on the wall.\n");
        }
        else
        {
            printf("%d bottles of beer on the wall. %d bottles of  beer.\n", numberOfBottles, numberOfBottles);
                   
            int oneFewer = numberOfBottles - 1;
            printf("Take one down, pass it around, %d bottles of beer on the wall.\n", oneFewer);
                   
            if (oneFewer == 0)
            {
                printf("There are simple bo more bottles of beer on the wall.\n");
            }
            else
            {
                printf("%d bottles of beer on the wall. %d bottles of  beer.\n", oneFewer, oneFewer);
                   
                int anotherOneFewer = oneFewer - 1;
                printf("Take one down, pass it around, %d bottles of beer on the wall.\n", anotherOneFewer);
                   
                if (anotherOneFewer == 0)
                {
                    printf("There are simple bo more bottles of beer on the wall.\n");
                }
                else
                {
                    printf("%d bottles of beer on the wall. %d bottles of  beer.\n", anotherOneFewer, anotherOneFewer);
                   
                    int lastOneFewer = anotherOneFewer - 1;
                    printf("Take one down, pass it around, %d bottles of beer on the wall.\n", lastOneFewer);
                    printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", anotherOneFewer);
    	    }
                printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", oneFewer);
            }
            printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", numberOfBottles);
        }
    }
    
    int main (int argc, const char * argv[])
    {
    
        singTheSong(2);
        
        return 0;
    }
    Code:
    $ gcc -o test -Wall test.c
    $ ./test
    2 bottles of beer on the wall. 2 bottles of  beer.
    Take one down, pass it around, 1 bottles of beer on the wall.
    1 bottles of beer on the wall. 1 bottles of  beer.
    Take one down, pass it around, 0 bottles of beer on the wall.
    There are simple bo more bottles of beer on the wall.
    Put a bottle in the recycling, 1 empty bottles in the bin.
    Put a bottle in the recycling, 2 empty bottles in the bin.
    See how I replaced all the function calls with basically repeating the function ? That's basically how it's working, except it's using the stack to repeat the code in the function call. This doesn't end the function itself once another is called, it simply runs the code in the function and then comes back and continues where it left off.

    Really, calling your own function is the same as calling API functions. Do you expect your code to stop where you call printf() ? No, once the runtime is done executing printf()'s code, it simply returns and continues to execute your own code where it left off. Recursion is the same.
     
  7. macrumors 604

    chrono1081

    Joined:
    Jan 26, 2008
    Location:
    Isla Nublar
  8. macrumors 6502a

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
  9. macrumors 603

    Joined:
    Aug 9, 2009
    #9
    After so many beers, I start talking like that, too.
     
  10. thread starter macrumors member

    Joined:
    Aug 24, 2009
    #10
    LOL. Already fixed that. Haven't started yet. Waiting for the Giants game to start.
     
  11. macrumors newbie

    Joined:
    Mar 17, 2014

Share This Page