Sidebar Sidebar
Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.

macOS Need help understanding a recursive function in Xcode

A

admo

macrumors member
Original poster
Aug 24, 2009
94
0
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?
 
admo said:
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?
Click to expand...

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.
 
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.
 
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
 
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!
 
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.
 
You must log in or register to reply here.
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.
Top Bottom
Back