macOS Having an issue getting my brain around this program.

[PinkyMacGodess]

I've been a programmer for decades, but for languages like Dyl-280 and SAS. I'm trying to get back into programming and am working my way through the Big Nerd Ranch Objective-C book. I ran into a program that I can't seem to understand. I know it must be simple, on some level, but it's eluding me...

The code is as shown here:

unsigned long SumNumbersTo (unsigned long);
unsigned long sum;

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); // debug print
    
    return 0;
}

unsigned long SumNumbersTo (unsigned long N)
{
    printf ("Pre if loop (N) (sum) %3lu, %3lu\n", N, sum); // debug print
    if (N == 0) {
        printf("If loop N = 0, N = %3lu, sum = %3lu\n", N, sum); // debug print
        return 0;
    } else {
    printf("N greater than 0, PreRecurse sum value = %3lu\n", sum); // debug print
    sum = N + SumNumbersTo (N-1);  // Look recursion here!
    printf ("Recurse N = %3lu, sum = %3lu\n", N, sum); // debug print
    }
    
   printf ("Sum numbers from 1 to %3lu = %3lu\n", N, sum);
   printf ("N = %3lu, sum = %3lu\n", N, sum); // debug print
    return sum;
}

and it puts out the following:

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.

What I'm having a hard time understanding is the flow of the program. It looks like the code tests for N being zero, and it does eventually get to zero, and then goes above it, but the real issue is the printf statement after the recursion. It looks like it is constantly calling itself, and looping through the if statement, and N is greater than zero at some point, and the code looks like it should then go back to recursion and just keep running off and looping until time freezes. Instead, it looks like it loops through the last printf statement of the else, and then the two outside the if, and then loops somehow back...

Setting breakpoints isn't helping because the breakpoints don't show that much different than the test output.

I guess I need a brain reboot to understand it. A different way of looking at it perhaps... It *looks like* strangeness is happening... It looks like it's looping at the wrong spots.

Help?

 

[ArtOfWarfare]

You need to know about the stack.

1. Your program starts, all that's on the stack is main.
2. main calls SumNumbersTo(10). Your stack is now main > SumNumbersTo(10)
3. that calls SumNumbersTo(9). Your stack is now main > SumNumbersTo(10) > SumNumbersTo(9).
...
At some point you have main > SumNumbersTo(10) > SumNumbersTo(9) > ... > SumNumbersTo(1) > SumNumbersTo(0).
Then SumNumbersTo(0) returns 0 to SumNumbersTo(1), who then returns 1 to SumNumbersTo(2)... so on... SumNumbersTo(9) returns 45 to SumNumbersTo(1) returns 55 to main(), which then prints the number and returns 0 to the command line, indicating that it finished without any errors.

Each time a function gets called, it's pushed onto the stack. Each time a function returns, it gets popped off the stack and the function that was below it continues execution from where it left off when it pushed another function onto the stack.

 

[subsonix]

One way of looking at it is that each time the function reaches SumNumbersTo(), it's interupted and called again with a new value of N.

Each function call is placed on a stack and it's not until N reaches 0 that it's allowed to return. When it does return, the stack is emptied in reverse order, ie the last call before N reached 0 will come first until the entire stack is empty.

It may help to single step through each instruction instead of using break points in the debugger, then you can see how sum and N changes over time.

 

[lee1210]

I wrote a lot, then Safari crashed.

Draw it out. Change N to 3. Write out each line as it executes. Write the value of each variable. If there's a print statement, write what it prints. Indent when you call a method and be sure to write the value of the incoming arguments, reduce your indentation when it returns. Write the value it's returning. When there's a print statement write down what is printed. At the end you'll see the order statements are run, and what is printed when.

From the looks of it you print twice at the beginning of your method, before a return or recursive call, and three times after the recursive call.

-Lee

 

[PinkyMacGodess]

One way of looking at it is that each time the function reaches SumNumbersTo(), it's interupted and called again with a new value of N.

Each function call is placed on a stack and it's not until N reaches 0 that it's allowed to return. When it does return, the stack is emptied in reverse order, ie the last call before N reached 0 will come first until the entire stack is empty.

It may help to single step through each instruction instead of using break points in the debugger, then you can see how sum and N changes over time.

And that's where it is getting weird for me. I understand that main calls SumNumbersTo. I understand that SumNumbersTo recursively calls itself.

• Why does 'sum' not increment with each recursive call?
• Why, when N does equal zero, does the execution then start at the next statement in the else part of the loop, and then go between the printf inside the loop, and the two outside the loop. It's like it's looping through the bottom of the if loop again, but not recursing: hitting the printf statement at the end of the loop, and at the end of the function, returning 'sum' to *something*, that I can't determine, and looping back to the end of the else in the if loop and doing the printfs again.

I guess the 'stack' concept is the stumbling block for me. And how the printf's are handling the stack without 'recursion'. Do they just 'print the stack' because that's what they do?

I mean, I see some funky looping going on, and that's what's throwing me. And perhaps I'm not explaining myself correctly too, that's a possibility.

Is there a better way to illustrate the stack concept?

I also added inline comments to the program for the print statements I added to try to see what was happening.

----------

You need to know about the stack.

1. Your program starts, all that's on the stack is main.
2. main calls SumNumbersTo(10). Your stack is now main > SumNumbersTo(10)
3. that calls SumNumbersTo(9). Your stack is now main > SumNumbersTo(10) > SumNumbersTo(9).
...
At some point you have main > SumNumbersTo(10) > SumNumbersTo(9) > ... > SumNumbersTo(1) > SumNumbersTo(0).
Then SumNumbersTo(0) returns 0 to SumNumbersTo(1), who then returns 1 to SumNumbersTo(2)... so on... SumNumbersTo(9) returns 45 to SumNumbersTo(1) returns 55 to main(), which then prints the number and returns 0 to the command line, indicating that it finished without any errors.

Each time a function gets called, it's pushed onto the stack. Each time a function returns, it gets popped off the stack and the function that was below it continues execution from where it left off when it pushed another function onto the stack.

How does the printf know about the stack? Why does it appear to be looping in an odd way? Is it going through the if/else loop again?

I also added inline comments to the program for the print statements I added to try to see what was happening.

 

[subsonix]

Why does 'sum' not increment with each recursive call?

Because sum gets its value from the return of SumNumbersTo(), which returns after SumNumbersTo() it called in the middle of the function.

Why, when N does equal zero, does the execution then start at the next statement in the else part of the loop, and then go between the printf inside the loop, and the two outside the loop. It's like it's looping through the bottom of the if loop again, but not recursing: hitting the printf statement at the end of the loop, and at the end of the function, returning 'sum' to *something*, that I can't determine, and looping back to the end of the else in the if loop and doing the printfs again.

It's because that's the point where the function gets interupted and called again with a new value, it's not until the end condition is met that it's allowed to continue.

I guess the 'stack' concept is the stumbling block for me. And how the printf's are handling the stack without 'recursion'. Do they just 'print the stack' because that's what they do?

I mean, I see some funky looping going on, and that's what's throwing me. And perhaps I'm not explaining myself correctly too, that's a possibility.

Is there a better way to illustrate the stack concept?

Each process has a call stack, functions are pushed onto this stack and poped when they return along with their variables and state which are local to each stack frame. A stack is also called a LIFO (Last In, First Out) queue, it's just like a stack of paper, the last item you put on the stack is the first that can be removed.

 

[lee1210]

This is what I suggested before. I'm going to put this in a code block since most of it is code:

I’ll leave out main, it calls SumNumbersTo (3)

In SubNumbersTo(3)
sum = 0, N = 3
printf ("Pre if loop (N) (sum) %3lu, %3lu\n", N, sum);		// prints: Pre if loop (N) (sum) 3, 0
if (N == 0) { //evaluates to false, so go to the else
printf("N greater than 0, PreRecurse sum value = %3lu\n", sum); //prints: N greater than 0, PreRecurse sum value = 0
sum = N + SumNumbersTo (N-1);  // Look recursion here! // N is 3, calls SumNumbersTo (2)
	In SumNumbersTo(2)
	sum = 0, N = 2
	printf ("Pre if loop (N) (sum) %3lu, %3lu\n", N, sum);		// prints: Pre if loop (N) (sum) 2, 0
	if (N == 0) { //evaluates to false, so go to the else
	printf("N greater than 0, PreRecurse sum value = %3lu\n", sum); //prints: N greater than 0, PreRecurse sum value = 0
	sum = N + SumNumbersTo (N-1);  // Look recursion here! // N is 2, calls SumNumbersTo (1)
		In SumNumbersTo(1)
		sum = 0, N = 1
		printf ("Pre if loop (N) (sum) %3lu, %3lu\n", N, sum);		// prints: Pre if loop (N) (sum) 1, 0
		if (N == 0) { //evaluates to false, so go to the else
		printf("N greater than 0, PreRecurse sum value = %3lu\n", sum); //prints: N greater than 0, PreRecurse sum value = 0
		sum = N + SumNumbersTo (N-1);  // Look recursion here! // N is 1, calls SumNumbersTo (0)
			In SumNumbersTo(0)
			sum = 0, N = 0
			printf ("Pre if loop (N) (sum) %3lu, %3lu\n", N, sum);		// prints: Pre if loop (N) (sum) 0, 0
			if (N == 0) { //evaluates to true, so go to the if block
			printf("If loop N = 0, N = %3lu, sum = %3lu\n", N, sum);	// prints: If loop N = 0, N = 0, sum = 0
			return 0
		sum = N + 0 // value returned was 0, N is 1, sum is set to 1
		//sum = 1, N = 1
		printf ("Recurse N = %3lu, sum = %3lu\n", N, sum);	//prints: Recurse N = 1, sum = 1
		printf ("Sum numbers from 1 to %3lu = %3lu\n", N, sum); //Sum numbers from 1 to 1 = 1
		printf ("N = %3lu, sum = %3lu\n", N, sum); // N = 1, sum = 1
		return sum; //return 1
	sum = N + 1; // value returned was 1, N is 2, sum is set to 3
	//sum = 3, N = 2
	printf ("Recurse N = %3lu, sum = %3lu\n", N, sum);	//prints: Recurse N = 2, sum = 3
	printf ("Sum numbers from 1 to %3lu = %3lu\n", N, sum); //Sum numbers from 1 to 2 = 3
	printf ("N = %3lu, sum = %3lu\n", N, sum); // N = 2, sum = 3
	return sum; //return 3
sum = N + 3 // value returned was 3, N is 3, sum is set to 6
printf ("Recurse N = %3lu, sum = %3lu\n", N, sum);	//prints: Recurse N = 3, sum = 6
printf ("Sum numbers from 1 to %3lu = %3lu\n", N, sum); //Sum numbers from 1 to 3 = 6
printf ("N = %3lu, sum = %3lu\n", N, sum); // N = 3, sum = 6
return sum; //return 6
//Back in main
printf ("Numbers from 1 to %3lu sum to %3lu.\n", N, sum); //prints: Numbers from 1 to 3 sum to 6

 

[Dranix]

I think part of the problem stems from the insane writing to a global variable in the function. This is a total nogo and I wonder why a modern book shows such bad coding style.

 

[ArtOfWarfare]

I think part of the problem stems from the insane writing to a global variable in the function. This is a total nogo and I wonder why a modern book shows such bad coding style.

That's so weirdly unnecessary that I didn't even notice sum was declared as a global instead of being local to the function.

In fact, I'd go as far as saying that it's more a coincidence that this code works than it was designed to work.

 

[whooleytoo]

Is there a better way to illustrate the stack concept?

If it helps for now, ignore how the stack is actually implemented. Perhaps if you just think of it this simplistic way: when one function calls another, a 'frozen copy' ("stack frame") of the calling function is created, which unfreezes and resumes when the called function finishes. And each of those 'frozen copies' has their own local variables and parameters.

That also is true if one function calls itself. If SumNumbersTo calls itself several times, each 'frozen copy' has its own value of N.

So, working through the sequence slowly:

SumNumbersTo(4)
sum = 4 + SumNumbersTo(3) // first "copy" , N = 4
sum = 3 + SumNumbersTo(2) // second copy, N = 3
sum = 2 + SumNumbersTo(1) // third copy, N = 2
return 1 + SumNumbersTo(0) //fourth copy, N = 1
return 0 // fifth copy, N = 0, no more recursive calls so go back to the previous copy
return sum (1 + 0) // back to forth copy!, N = 1
return sum (2 + 1) // back to 3rd copy!, N = 2
return sum (3 + 3) // back to 2nd copy!, N = 3
return sum (4 + 6) // back to 1st copy!, N = 4

It's very important to have the "If N == 0" test case, or else the programme would endlessly keep creating more and more copies / stack frames and eventually run out of memory and crash/be halted.

 

[subsonix]

If it helps for now, ignore how the stack is actually implemented. Perhaps if you just think of it this simplistic way: when one function calls another, a 'frozen copy' ("stack frame") of the calling function is created, which unfreezes and resumes when the called function finishes. And each of those 'frozen copies' has their own local variables and parameters.

That also is true if one function calls itself. If SumNumbersTo calls itself several times, each 'frozen copy' has its own value of N.

I'd add that an important difference is that in this case the function is not allowed to return, so additional copies of the function are added to the stack, each keeping the current "state" of N and sum.

 

[PinkyMacGodess]

That's so weirdly unnecessary that I didn't even notice sum was declared as a global instead of being local to the function.

In fact, I'd go as far as saying that it's more a coincidence that this code works than it was designed to work.

But if 'sum' were local to the function, main wouldn't have access to it for the final print, unless it passed it to main on a return.

What I though cheeky was the define and call being on one line. I thought that a little advanced for someone picking up programming (C programming) from scratch. I mean, it works, but it's probably a programmer shortcut that I'd pickup later... But now that I look at it again, perhaps that was the best way to do that...

But anyway...

OH, where this came from was in trying to explain this program, and how that last printf does the recycle bin part:

#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); //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[])
{
    singSongFor(4);
    return 0;
}

Apparently many people can't figure out how that last printf works, without calling itself or recursing somehow... I guess it sort of recurses, and blows through the stack. How would someone program around that if they only wanted it to happen once?

 

[ArtOfWarfare]

But if 'sum' were local to the function, main wouldn't have access to it for the final print, unless it passed it to main on a return.

The Suming function already returns sum at the end of the function. Not only does it do that, but main assigns that returned value to a new local variable named sum (which shadows the global variable of the same name).

All the weirdness here with that variable makes me think a mistake was definitely made somewhere. Properly written, there shouldn't be a global variable called sum and the Suming function should declare a local variable called sum before using it.

 

[subsonix]

Apparently many people can't figure out how that last printf works, without calling itself or recursing somehow...

It works by the same mechanism as above, the function is not allowed to reach the bottom and return, instead it's called again and new stack frames are added until the end condition is met. At that point the stack "unwinds" backwards until all stack frames are gone. The variables in each stack frame are local, unique copies with values that reflect the state at the moment the function was called.

Consider this function that prints a string in reverse, putchar() prints the first character in the string, what ever that was at the time the function was called. The variable *string is a unique copy in each stack frame, keeping the state from the time the function was called.

void reverseString(char *string) {
    if(string[0] != '\0') {
        reverseString(string +1);
    }
    putchar(string[0]);
}

Since *string is a char pointer, string +1 just advances the address to the next character. '\0' is the null character which terminates a C string.

If you want to control how many times the last printf if called you need to wrap it in a conditional that prints for a given value of numberOfBottles, or add it to the end condition if you only want it to print the last time.

 

[PinkyMacGodess]

Here's where I'm getting lost.

unsigned long SumNumbersTo (unsigned long N)
{
    printf ("Pre if loop (N) (sum) %3lu, %3lu\n", N, sum); // debug print
    if (N == 0) {
        printf("If loop N = 0, N = %3lu, sum = %3lu\n", N, sum); // debug print
        return 0;
    } else {
    printf("N greater than 0, PreRecurse sum value = %3lu\n", sum); // debug print
    sum = N + SumNumbersTo (N-1);  // Look recursion here!
    printf ("Recurse N = %3lu, sum = %3lu\n", N, sum); // debug print
    }
    
   printf ("Sum numbers from 1 to %3lu = %3lu\n", N, sum);
   printf ("N = %3lu, sum = %3lu\n", N, sum); // debug print
    return sum;
}

Function is called.
enter if loop.
N > 0 do else
print
sum = N + SumNumbersTo (N-1) -- recurse
enter if loop
N > 0 do else
sum = N + SumNumbersTo (N-1) -- recurse
enter if loop
N > 0 do else
sum = N + SumNumbersTo (N-1) -- recurse
enter if loop
N = 0
return to main()
print Numbers from 1 to 10 sum to 0
done.

The reason why I read it this way is the 'if' loop. It's basically do this (N == 0), or do that (the stuff between the {}'s after the else. Between the breakpoints and the test/debug output, it looks like there is a loop going between the last printf of the else and the three lines outside the if/else loop at the end of the function.

I'm beginning to feel embarrassed that I haven't 'gotten it' yet... Maybe I need to start over at a slower pace...

 

[chown33]

Here's where I'm getting lost.

unsigned long SumNumbersTo (unsigned long N)
{
    printf ("Pre if loop (N) (sum) %3lu, %3lu\n", N, sum); // debug print
    if (N == 0) {
        printf("If loop N = 0, N = %3lu, sum = %3lu\n", N, sum); // debug print
        return 0;
    } else {
    printf("N greater than 0, PreRecurse sum value = %3lu\n", sum); // debug print
    sum = N + SumNumbersTo (N-1);  // Look recursion here!
    printf ("Recurse N = %3lu, sum = %3lu\n", N, sum); // debug print
    }
    
   printf ("Sum numbers from 1 to %3lu = %3lu\n", N, sum);
   printf ("N = %3lu, sum = %3lu\n", N, sum); // debug print
    return sum;
}

Function is called.
     enter if loop.
     N > 0 do else
          print
          sum = N + SumNumbersTo (N-1) -- recurse
               enter if loop
               N > 0 do else
               sum = N + SumNumbersTo (N-1) -- recurse
                    enter if loop
                    N > 0 do else
                    sum = N + SumNumbersTo (N-1) -- recurse
                         enter if loop
                         N = 0
                         return to main()
                         print Numbers from 1 to 10 sum to 0
done.

The reason why I read it this way is the 'if' loop. It's basically do this (N == 0), or do that (the stuff between the {}'s after the else. Between the breakpoints and the test/debug output, it looks like there is a loop going between the last printf of the else and the three lines outside the if/else loop at the end of the function.

I'm beginning to feel embarrassed that I haven't 'gotten it' yet... Maybe I need to start over at a slower pace...

First, the 'if' is not a loop. It's a simple conditional test. There's no loop there.[1]

Second, there is no explicit "return to main()". There is only a return to caller.

That is, at no point does the function itself "return to main()". All it does is return to whoever called it. That means you have to unwind all the calls to the function, along with the if's or else's that got you there. In other words, when you see a 'return', you have to go back to the line after whatever call to SumNumbersTo() got you there. That's what 'return' does: it returns to the caller, immediately after whatever function-call got you into the function.

The unwinding is possible because there's a stack, which is a list of who the callers are. The top of the stack holds the most recent caller. Why? Because that's how a stack works. Return to the caller and continue tracing the execution. You'll then return to the previous caller. And so on until the previous caller is main(). At that point (and ONLY that point), you will have returned to main.

If you don't understand that callers are being stored on a stack, precisely so they can be returned to, then you don't understand how subroutines or a stack works. Figure out subroutines (go to the function and remember who told us to go there (the caller)) and a stack (save the most recent caller), and the rest should fall into place. Without those, you're not going to see it.

http://en.wikipedia.org/wiki/Stack_(abstract_data_type)


[1] The observed looping is a consequence of the recursion. That is, you're seeing an effect of a recursive call. You're not seeing an actual iterative loop with a 'while' or 'for' or even a 'goto'. If that doesn't make sense yet, it's ok. You need to understand exactly how calling a function and a 'return' works first.

 

[firewood]

Note that a recursive function call can usually be replaced by a loop or a GOTO statement or two and some arrays. Just stuff all the parameters and local variables in arrays, increment the array index and GOTO the top of the recursive function.

It's really just a loop where the compiler and/or CPU hides all the interesting details to "simplify" things for the programmer. A stack is just a variant array.

 

[mfram]

Let's make something easier to understand. Maybe that will help for the O.P. Factorial(n) = n * (n-1) * (n-2) * ... until the sequence goes to 1.

#include <stdio.h>

int factorial(int num)
{
        int v;

        printf("Factorial called with %d\n", num);

        if (num == 0)
        {
                v = 1;
                printf("Factorial called with %d returning %d\n", num, v);
                return v;
        }
        else
        {
                v = num * factorial(num - 1);
                printf("Factorial called with %d returning %d\n", num, v);
                return v;
        }
}

int main()
{
        printf("final value: %d\n", factorial(5));
}

Output:

Factorial called with 5
Factorial called with 4
Factorial called with 3
Factorial called with 2
Factorial called with 1
Factorial called with 0
Factorial called with 0 returning 1
Factorial called with 1 returning 1
Factorial called with 2 returning 2
Factorial called with 3 returning 6
Factorial called with 4 returning 24
Factorial called with 5 returning 120
final value: 120

 

[gnasher729]

That's so weirdly unnecessary that I didn't even notice sum was declared as a global instead of being local to the function.

In fact, I'd go as far as saying that it's more a coincidence that this code works than it was designed to work.

If you made the harmless looking change from

    sum = N + SumNumbersTo (N-1);  // Look recursion here!

to

    sum = N;
    sum += SumNumbersTo (N-1);  // Look recursion here!

it would totally break. Challenge to everyone thinking they are clever (including me ) Find out what the function would return with this change, without actually running it.

 

[gnasher729]

The reason why I read it this way is the 'if' loop. It's basically do this (N == 0), or do that (the stuff between the {}'s after the else. Between the breakpoints and the test/debug output, it looks like there is a loop going between the last printf of the else and the three lines outside the if/else loop at the end of the function.

I'm beginning to feel embarrassed that I haven't 'gotten it' yet... Maybe I need to start over at a slower pace...

You picked a bad example for learning C, because it uses recursion which is a bit difficult and rarely used in C programming. But it can be helpful. Many times, software is complex. You can't understand everything completely. Instead, you understand one thing, then remember _what_ it does, ignore completely _how_ it does it, and trust that it does what you figured out what it does. Let's use this principle.

Question: What does a call SumNumbersTo (0) do?
Answer: It prints some stuff and returns 0.

Question: What does a call SumNumbersTo (1) do?
Answer: It prints lots of stuff, sets sum = 1 + SumNumbersTo (0) which is 1 + 0 = 1 according to the previous question, and returns 1.

Question: What does a call SumNumbersTo (2) do?
Answer: It prints lots of stuff, sets sum = 2 + SumNumbersTo (1) which is 2 + 1 = 3 according to the previous question, and returns 3.

Question: What does a call SumNumbersTo (3) do?
Answer: It prints lots of stuff, sets sum = 3 + SumNumbersTo (2) which is 3 + 3 = 6 according to the previous question, and returns 6.

and so on. When you answered the last question, you just went through the code, and _believed_ the answer to the previous question about SumNumbersTo (2). So with the intermediate answers all written down, the question "what does a call SumNumbersTo (10) do" is quite easy. You don't have to follow the code all these levels deep.

 

[Dranix]

Btw I can't find that program in my Big Nerd Ranch:Objective-C book... Where is it supposed to be?

The following is the program from the book's chapter on recursion:

 

[ArtOfWarfare]

recursion [is] rarely used in C programming.

I disagree. Recursion is regularly used in just about all programming languages (I can't think of any language where it isn't regularly used, but I'll accept the possibility that there is one where it isn't). This is not a difficult example of it (Hanoi is - I have no freaking idea why so many schools use that as their first example of recursion).

Understanding recursion is vital to being able to write good algorithms. There are some domains of programs where it will be more regularly used than others - often it ends up being used in boilerplates or libraries that you won't have to write yourself on every project - but from time to time you'll need to write them yourself or need to be able to understand one written by someone else (or yourself in the past).

 

[Catfish_Man]

I disagree. Recursion is regularly used in just about all programming languages (I can't think of any language where it isn't regularly used, but I'll accept the possibility that there is one where it isn't). This is not a difficult example of it (Hanoi is - I have no freaking idea why so many schools use that as their first example of recursion).

Understanding recursion is vital to being able to write good algorithms. There are some domains of programs where it will be more regularly used than others - often it ends up being used in boilerplates or libraries that you won't have to write yourself on every project - but from time to time you'll need to write them yourself or need to be able to understand one written by someone else (or yourself in the past).

Perhaps a better way of putting it would be "recursion is dangerous in C". Because there's no way to force tail calls, any recursive function that runs on user input can likely be turned into a stack overflow.

You can work around it by capping input sizes, or examining the generated asm to make sure you're getting a tail call, but those are both pretty unfortunate and fragile.

 

[PinkyMacGodess]

Btw I can't find that program in my Big Nerd Ranch:Objective-C book... Where is it supposed to be?

The following is the program from the book's chapter on recursion:

Image

I got it from one of the authors in response to a question on how that beer program works.

Sorry for the untimely response, I've been on holiday...

 

[PinkyMacGodess]

You picked a bad example for learning C, because it uses recursion which is a bit difficult and rarely used in C programming. But it can be helpful. Many times, software is complex. You can't understand everything completely. Instead, you understand one thing, then remember _what_ it does, ignore completely _how_ it does it, and trust that it does what you figured out what it does. Let's use this principle.

Taking a week off to soak my brain in alcohol and prog rock helped me to see that this program is pretty complex for a noob. It does a lot that is 'magic' at my current level, and uses a rather advanced syntax for the given level of noobness.

Recursion is used a lot, for certain things, and this function is kinda odd.

But I think I just figured it out!

After the recursions, it has x number of calls. N == 0, so it issues a return that drops to the next statement after the recursive call and hits the printf, exits the if/else and does those last lines, flips back to the if/else, returns to the line after the recursion, etc, until it's done and blows out of the function, and ends. Big magic, and not too clear what's going on, and the breakpoints don't help as they obliterate/obfuscate the flow...

Warm?