BeerSong

TheRojo · February 3, 2014, 6:56am

I’m having an issue wrapping my head around the beerSong code.

#include <stdio.h> void singSongFor(int numberOfBottles) { if (numberOfBottles == 0) {printf("there are simply no more bottles of beer on the wall. \n\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\n", oneFewer); singSongFor(oneFewer); printf("Put a bottle in the recycling, %d empty bottles in the bin. \n", numberOfBottles); } } int main(int argc, const char * argv[]) { singSongFor(4); return 0; }

I’m not sure how it’s adding back up to 4 from 0. Any help with explanation would be great!

ibex10 · February 3, 2014, 7:47am

The machinery that supports the recursive function calls, saves the value of the numberOfBottles variable just before the function calls itself. The same machinery restores the value of the variable to the saved value when the function returns. If you understand this, then you can explain what’s going on.

Note that the function keeps calling itself as long as the value of numberOfBottles is not zero:

void singSongFor(int numberOfBottles)
{
    if (numberOfBottles == 0)
        ...
    } else {
        ...
        int oneFewer = numberOfBottles - 1;
        singSongFor (oneFewer);  // function calling itself - this is called recursion
        ...
    }
    // The function returns when numberOfBottles reaches the value of zero.
}

The function starts returning when numberOfBottles reaches the value of zero:

call
call
call
...
numberOfBottles == 0    // start returning
...
return   // for each call there is a return and the value of the variable is restored
return
return

TheRojo · February 3, 2014, 8:03am

I guess what is still confusing me is why the machine says “hey, no bottles!” and then just continue looping “there are simply no more bottles…”

Another thing that crosses my mind is with the call / return, how does it know to skip to the last line and not get a bottle from return and then say “oops, I have a bottle again, better take it down?” The way my brain is processing it (or isn’t) is the numberOfBottles becomes ‘oneFewer’ while the program is running and so oneFewer eventually becomes 0 and it should just continue looping.

I hope I’m explaining myself well enough. I appreciate the help.

ibex10 · February 3, 2014, 3:01pm

To visualise what’s happening, try the following exercise for: singSongFor (4).

Take a blank sheet of paper, and cut it into four equal pieces.

Start building a call stack:

numberOfBottles == 4
1. Take a blank piece and write the number 4 on it, and put it aside.
    --> singSongFor (3)

numberOfBottles == 3
2. Take another blank piece and write the number 3 on it, and place it on top of number 4.
    --> singSongFor (2)

numberOfBottles == 2
3. Take another blank piece and write the number 2 on it, and place it on top of number 3.
    --> singSongFor (1)

numberOfBottles == 1
4. Take another blank piece and write the number 1 on it, and place it on top of number 2.
    --> singSongFor (0)

numberOfBottles == 0

You have no more blank pieces left.
And you have a stack of 4 pieces numbered 1, 2, 3, and 4 - 1 at the top and 4 at the bottom.
This is akin to function calling itself four times.

Now start emptying the stack, by removing the pieces of paper one at a time:

numberOfBottles == 0
1. Remove the top piece (number 1) from the stack, you see the number 2.
    --> return 

numberOfBottles == 1
2. Remove the top piece (number 2) from the stack, you see the number 3.
    --> return

numberOfBottles == 2
3. Remove the top piece (number 3) from the stack, you see the number 4.
    --> return

numberOfBottles == 3
4. Remove the top piece (number 4) from the stack, the stack is empty now.
    --> return

numberOfBottles == 4

This is akin to function returning four times.

TheRojo · February 3, 2014, 9:55pm

I think I’m starting to understand. Could it also be put that SingSongFor has 4… after those 4, though, it has to empty the new stack.

Phumez · February 6, 2014, 9:53pm

Funny, I was actually going to ask exactly the same thing.

From the above, I understand the stacking part but I’m still not sure about ‘returning’ the value.
I understand how it triggers, I understand how it works it way down.
I also understand the ‘else’ printf statement (There are simply no more bottles…") and I understand how it would finally say “Put a bottle in the recycling…”)
I just don’t see why it would repeat that final printf message 4 times again…

Maybe for me it’s because I was under the ‘illusion’ that memory needs to be cleared after a function before it can be used again (although for exactly the same thing in this case, but just one value less).
So I don’t understand how somehow it can ‘remember’ it now needs to call back up to 4 bottles of beer in the bin.

// Print a message just before the function ends printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", numberOfBottles);
At the point this is executed, ‘numberOfBotles’ = 0 (otherwise this wouldn’t be executed)…?

ibex10 · February 7, 2014, 4:16am

[quote]So I don’t understand how somehow it can ‘remember’ it now needs to call back up to 4 bottles of beer in the bin.
[/quote]
Let’s say a function (Foo) invokes (calls) another function Bar).
After Bar returns, Foo executes the statement immediately following the statement that invoked Bar. Furthermore, just before the invocation, the values of all local variables of Foo are saved; when Bar returns, the values of the local variables are restored.

void Bar (int);
void Foo (int v)
{
    Bar (v-1);
    printf ("%s: Returned from Bar: v = %d\n", __func__, v);
}

void Bar (int v)
{
    printf ("%s: v = %d\n", __func__, v);
}

int main(int argc, const char * argv[])
{
    Foo (4);
    return 0;
}

Bar: v = 3
Foo: Returned from Bar: v = 4

The same thing applies even if a function calls itself:

void Foo (int v)
{
    if (v == 0) {
        return;
    }
    Foo (v-1);
    printf ("%s: Returned from Foo: v = %d\n", __func__, v);
}

int main (int argc, const char * argv[])
{
    Foo (4);
    return 0;
}

Foo: Returned from Foo: v = 1
Foo: Returned from Foo: v = 2
Foo: Returned from Foo: v = 3
Foo: Returned from Foo: v = 4

AJGolf · March 1, 2014, 6:08pm

I found a decent way to follow what was happening was to set a break point at this line singSongFor(oneFewer);

I was then able to see the flow of the program and what the values of the variables were each time the program “looped” through.

It made this concept much easier to understand.

macsolns · March 18, 2014, 9:07pm

My problem is with getting results in the stacks as shown on pp. 38-39. No matter which frame I look at, I get numberOfBottles = -1 and oneFewer = -1. However, the printf statements are printing the correct results each time.

robcow · March 27, 2014, 11:43pm

Sorry to be dense, but it’s been a long day.

I still do not understand how that line “printf(“Put a bottle in the recycling, %d empty bottles in the bin.\n”, numberOfBottles);” keeps looping.

I guess if I have to just ‘trust’ that it does, that is what I’ll have to do. I put many breakpoints in the program and watch the variables, and the calls, but my mind keeps coming back to ‘Huh?’

I guess throwing in something more about the ‘stack’ concept and how a function like printf can call itself as well before this point might be a good idea, at least my brain would feel better about it I think… It’s just surprising that this works like it does… I assume that printf calls itself somehow?

Interesting…

I remember reading some horrible code once, and there was a comment in a function ‘And magic happens’, and no one could quite follow what the heck the original programmer was doing. Some called it job security. Didn’t work, for him, but magic does happen I guess…

Thanks…

ibex10 · March 28, 2014, 12:22pm

It is not the printf calling itself; it is the function that is calling the printf calling itself.

Here is a simple example which you can wrap your mind around:

//  main.m

#import <stdlib.h>

unsigned long SumNumbersTo (unsigned long);

int main (int argc, const char * argv[])
{
    unsigned long N = 10;
    unsigned long sum = SumNumbersTo (N);
    printf ("Numbers from 1 to %3lu sum to %3lu.\n", N, sum);
    
    return 0;
}

unsigned long SumNumbersTo (unsigned long N)
{
    if (N == 0) {
        return 0;
    }
    unsigned long sum = N + SumNumbersTo (N-1);  // Look recursion here!
    
    printf ("Sum numbers from 1 to %3lu = %3lu\n", N, sum);

    return sum;
}

robcow · March 28, 2014, 5:29pm

I breakpointed everything, and don’t see where it’s looping for that last printf, but I see where it hits the return so that’s part of the loop and not some magic of printf. I do see memory use growing with the loops too, so it is ‘stacking’ the results, and printf is popping them off. What was confusing me is that ‘N’ goes nonzero.

robcow · March 29, 2014, 7:53pm

The breakpointing in xCode seems a work in progress.

Your program starts with the declaration of N, then jumps right to the test if it’s zero in the function. Then the recursion, bouncing back and forth from the test in the if statement to the recursion as each call is made to itself. All of the time with sum = 0. N hits 0, and it falls through to the return statement and drops to the printf statement, and bounces back ad forth between the printf to the return statement in the function. What is it returning sum to?

Then it pops out of the function and printf’s the last line and ends.

Can you imagine the confusion some people have had?

ibex10 · March 30, 2014, 5:57am

[quote]Then it pops out of the function and printf’s the last line and ends.

Can you imagine the confusion some people have had?[/quote]
Yes, I can because the recursion could be hard to understand sometimes.

This is how the function SumNumbersTo works: For N = 0, it immediately returns to main. For all other values of N, it invokes itself repeatedly many times, returning the partial sums to itself, before finally returning the final sum to main.

Add another printf to it to see what is really going on, you don’t need to use the debugger:

unsigned long SumNumbersTo (unsigned long N)
{
    printf ("Sum numbers from 1 to %3lu...\n", N);

    if (N == 0) {
        return 0;
    }
    
    unsigned long sum = N + SumNumbersTo (N-1);  // Look recursion here!
    
    printf ("Sum numbers from 1 to %3lu = %3lu\n", N, sum);

    return sum;
}

Look at the values of N:

Sum numbers from 1 to  10...
Sum numbers from 1 to   9...
Sum numbers from 1 to   8...
Sum numbers from 1 to   7...
Sum numbers from 1 to   6...
Sum numbers from 1 to   5...
Sum numbers from 1 to   4...
Sum numbers from 1 to   3...
Sum numbers from 1 to   2...
Sum numbers from 1 to   1...
Sum numbers from 1 to   0...
Sum numbers from 1 to   1 =   1
Sum numbers from 1 to   2 =   3
Sum numbers from 1 to   3 =   6
Sum numbers from 1 to   4 =  10
Sum numbers from 1 to   5 =  15
Sum numbers from 1 to   6 =  21
Sum numbers from 1 to   7 =  28
Sum numbers from 1 to   8 =  36
Sum numbers from 1 to   9 =  45
Sum numbers from 1 to  10 =  55
Numbers from 1 to  10 sum to  55.

The key to understanding recursion is this: when a function (caller) calls another function (this includes itself), its (caller’s) local variables are saved; when the called function returns to the caller, the caller’s local variables are restored.

robcow · April 2, 2014, 3:04pm

[code]unsigned long SumNumbersTo (unsigned long N)
{
printf (“Pre if loop (N) (sum) %3lu, %3lu\n”, N, sum);
if (N == 0) {
printf(“If loop N = 0, N = %3lu, sum = %3lu\n”, N, sum);
return 0;
} else {
printf(“N greater than 0, PreRecurse sum value = %3lu\n”, sum);
sum = N + SumNumbersTo (N-1); // Look recursion here!
printf (“Recurse N = %3lu, sum = %3lu\n”, N, sum);
}

printf (“Sum numbers from 1 to %3lu = %3lu\n”, N, sum);
printf (“N = %3lu, sum = %3lu\n”, N, sum);
return sum;
}[/code]

I did the above, and got this as output:

Pre if loop (N) (sum) 10, 0 N greater than 0, PreRecurse sum value = 0 Pre if loop (N) (sum) 9, 0 N greater than 0, PreRecurse sum value = 0 Pre if loop (N) (sum) 8, 0 N greater than 0, PreRecurse sum value = 0 Pre if loop (N) (sum) 7, 0 N greater than 0, PreRecurse sum value = 0 Pre if loop (N) (sum) 6, 0 N greater than 0, PreRecurse sum value = 0 Pre if loop (N) (sum) 5, 0 N greater than 0, PreRecurse sum value = 0 Pre if loop (N) (sum) 4, 0 N greater than 0, PreRecurse sum value = 0 Pre if loop (N) (sum) 3, 0 N greater than 0, PreRecurse sum value = 0 Pre if loop (N) (sum) 2, 0 N greater than 0, PreRecurse sum value = 0 Pre if loop (N) (sum) 1, 0 N greater than 0, PreRecurse sum value = 0 Pre if loop (N) (sum) 0, 0 If loop N = 0, N = 0, sum = 0 Recurse N = 1, sum = 1 Sum numbers from 1 to 1 = 1 N = 1, sum = 1 Recurse N = 2, sum = 3 Sum numbers from 1 to 2 = 3 N = 2, sum = 3 Recurse N = 3, sum = 6 Sum numbers from 1 to 3 = 6 N = 3, sum = 6 Recurse N = 4, sum = 10 Sum numbers from 1 to 4 = 10 N = 4, sum = 10 Recurse N = 5, sum = 15 Sum numbers from 1 to 5 = 15 N = 5, sum = 15 Recurse N = 6, sum = 21 Sum numbers from 1 to 6 = 21 N = 6, sum = 21 Recurse N = 7, sum = 28 Sum numbers from 1 to 7 = 28 N = 7, sum = 28 Recurse N = 8, sum = 36 Sum numbers from 1 to 8 = 36 N = 8, sum = 36 Recurse N = 9, sum = 45 Sum numbers from 1 to 9 = 45 N = 9, sum = 45 Recurse N = 10, sum = 55 Sum numbers from 1 to 10 = 55 N = 10, sum = 55 Numbers from 1 to 10 sum to 55.

It didn’t make it much clearer…

I will move on though.

fthorton · May 30, 2014, 1:36pm

[quote=“ibex10”]To visualise what’s happening, try the following exercise for: singSongFor (4).

Take a blank sheet of paper, and cut it into four equal pieces.

Start building a call stack:

numberOfBottles == 4
1. Take a blank piece and write the number 4 on it, and put it aside.
    --> singSongFor (3)

numberOfBottles == 3
2. Take another blank piece and write the number 3 on it, and place it on top of number 4.
    --> singSongFor (2)

numberOfBottles == 2
3. Take another blank piece and write the number 2 on it, and place it on top of number 3.
    --> singSongFor (1)

numberOfBottles == 1
4. Take another blank piece and write the number 1 on it, and place it on top of number 2.
    --> singSongFor (0)

numberOfBottles == 0

You have no more blank pieces left.
And you have a stack of 4 pieces numbered 1, 2, 3, and 4 - 1 at the top and 4 at the bottom.
This is akin to function calling itself four times.

Now start emptying the stack, by removing the pieces of paper one at a time:

numberOfBottles == 0
1. Remove the top piece (number 1) from the stack, you see the number 2.
    --> return 

numberOfBottles == 1
2. Remove the top piece (number 2) from the stack, you see the number 3.
    --> return

numberOfBottles == 2
3. Remove the top piece (number 3) from the stack, you see the number 4.
    --> return

numberOfBottles == 3
4. Remove the top piece (number 4) from the stack, the stack is empty now.
    --> return

numberOfBottles == 4

This is akin to function returning four times.[/quote]

So Ibex10, is the “function returning” something that recursion does automatically regardless of whether you log it to the user using the printf function? I took out the line printf(“Put a bottle in the recycling, %d empty bottles in the bin.\n”, numberOfBottles); and recompiled it and the build was successful and it printed out everything above that line just fine – so in trying to understand how recursion works in general, I’m wondering if the return of each value is just something that happens in that it’s “built in to the machinery that supports recursive function calls” as you say? Thanks for helping.

ibex10 · May 30, 2014, 3:03pm

Recursion does not require a function to return a value; it only requires the function to terminate the recursion:

#include <stdio.h>

void CountDown (int startNumber)
{
    if (startNumber == 0) {
        printf ("%s: Terminating...\n", __func__);
    }
    else {
        printf ("%s: Remaining: %d \n", __func__, startNumber);
        int next = startNumber-1;
        CountDown (next);
        printf ("%s: Start Number: %d \n", __func__, startNumber);
    }
}

int main (int argc, const char * argv[])
{
    CountDown (7);
    return 0;
}

CountDown: Remaining: 7 
CountDown: Remaining: 6 
CountDown: Remaining: 5 
CountDown: Remaining: 4 
CountDown: Remaining: 3 
CountDown: Remaining: 2 
CountDown: Remaining: 1 
CountDown: Terminating...
CountDown: Start Number: 1 
CountDown: Start Number: 2 
CountDown: Start Number: 3 
CountDown: Start Number: 4 
CountDown: Start Number: 5 
CountDown: Start Number: 6 
CountDown: Start Number: 7

Let us know if this does not answer your question.

bpmckim · June 10, 2014, 6:17pm

I am very new to programming and this book is my first shot at it, so this might not even make sense but it is how I got my head around it. I think of each frame as a task list. And for this there are two main “tasks” in each frame, the traditional song and the new recycling verse. Each time it is called it completes the traditional song task, and that gets checked off, but because it calls itself again it starts over, never completing the new recycling verse, so it gets put on the stack uncompleted. Over time you have a stack of uncompleted new recycling verse tasks. Once numberOfBottles == 0 is goes back through the stack completing all the unchecked tasks, which is only the recycling verse.

Like I said this might not even make sense, but it works in my head and got me through it.

cesarjardim · June 24, 2014, 1:57pm

Hey Everyone, I’m using XCode 5 and Mavericks. I don’t know if this has any influence in the scope/stack management but in my case it kinda starts returning me negative values. I guess that in my case it is doing the right thing, subtracting from the argument (in this case 4) but it doesn’t stop when it hits 0. Am I doing something awfully wrong here?

[quote]-14199 bottles of beer on the wall. -14199 bottles of beer.
Take one down, pass it around, -14200 bottles of beer on the wall.[/quote]

#include <stdio.h>

[code]
void singSongFor(int numberOfBottles) {
if (numberOfBottles == 0) {
printf(“There are simply no more bottles of beer on the wall.\n\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\n”, oneFewer);

singSongFor(oneFewer);//this function calls itself

//print a message just before the function ends
printf("Put a bottle in the recycling, %d empty bottles in the bin.\n", numberOfBottles);

}

int main(int argc, const char * argv[])
{
// insert code here…
singSongFor(4);
return 0;
}[/code]

jbacal · July 16, 2014, 3:36am

I found this thread since I was baffled by the same thing. I am not sure if I am correct, here, but here’s what I have synthesized.

Once numberOfBottles == 0, the stuff in the if block executes, and then, for the first time ever, the function actually gets to the last bracket.
THIS means it’s time to try to get to the end of the main program, to start RETURNING.
But four independent calls to singSongFor() have literally stacked up and need to be taken care of for main() to really be the only frame left around, to finally be officially done.

The explanation that makes the most sense to me is what bmpckim said, that the four calls left on the stack have unfinished business, specifically, that they each put in the recycling the number of bottles that existed when they were written as tasks. That’s what I’m going to settle on for now, but look forward to understanding things better as I go.

Second edit - OK getting it more now. Each time a new frame is created that instance of the function is temporarily paused (not paused, but busy creating a new version of itself), then, when returning can happen, it simply goes to the next step like nothing ever happened.

Topic		Replies	Views
How does numberOfBottles increment in BeerSong? 3. Variables and Types	4	1392	August 20, 2015
Period 5. Functions	1	1418	December 14, 2015
Please help General Book Discussion	1	1323	May 16, 2014
Stacks showing during BeerSong debug 5. Functions	3	1642	October 29, 2016
Recursion my own example 5. Functions	1	1370	May 27, 2014

BeerSong

Related Topics