Thread: question on functions --> ch 9 qn 19 : modern c programming by KING

Hi,

I have the below code which I do not understand. The problem is: which instruction is to be executed after pb(n/2) is called? My guess is that once pb(n/2) is encountered, program goes to void pb(int n) and starts executing again from there. But that means that putchar() is never executed. Wondering if someone can show me how to trace this small program.

Code:

#include <stdio.h>

/*function declaring*/
void pb(int n)
{
	if (n != 0)
	{
		pb(n/2);
		putchar('0' + n % 2);
	}
}

int main()
{
	pb(10);

	getchar();getchar();
	return 0;
}

The following table is a list of variables and statements defining how I think the program is executing.
http://i44.tinypic.com/21an0ol.png
http://i41.tinypic.com/14cd3t4.png

Originally Posted by bos1234

My guess is that once pb(n/2) is encountered, program goes to void pb(int n) and starts executing again from there. But that means that putchar() is never executed.

You're right that the function calls itself. But putchar WILL eventually be executed since the function does not ALWAYS call itself.
If n is 0 it simply returns. At that point, all the previous calls (whose state has been stored on the stack) return in reverse order and execute the putchar call.

Have you figured out what the program does and how it does it?

When n reaches 0, control is now in the last of the chain of calls of pb. Therefore, the pb function returns... to the previous call of pb.

I doubt you know about the abstract concept of stacks yet but to add to laser's fine answer I'll try and illustrate...

(Note, this is all very simplified and not really how C does it, or necessarily does it, but the concept is sound)

When you call a function, one of the things it does it puts the *next* instruction in the current context onto a stack. I.e. where the program execution should continue from when returning from the function.

Code:

1. void pb(int n)

2. {

3.     if (n != 0) {

4.        pb(n/2);

5.        putchar('0' + n % 2);

6. }
7. int main() {
8. pb(2);
9. return 0;

}

I've changed your code a bit but not much. Pretend the numbers down on the left hand side are "addresses".

Ok, so the program will start executing on line 8. Line 8 is a function call, so it will put the "address" 9 onto the top of the stack (called PUSHing onto the stack). This is the address where the program "jumps to" when the function pb() is finished; i.e. where program execution will continue from. The stack now looks like this:

Code:

9                 <--- Top of stack

NB: Stacks are last in, first out (LIFO), so when you grab something off the stack (POPping off the stack) the last thing pushed onto it is what you grab. Think of it as a pile off books maybe. You put a book onto the stack (push), and when you take from the stack (pop) you take the last book you put on the top.

Ok, so now we get to line 3. n is current not 0, it's 2 (as you correctly identified in your trace). So now the function pb needs to be called. It doesn't matter that it's the same function, what gets pushed onto the top of the stack is still the next instruction to execute after the function finishes (in this case [line] 5].

The stack now looks like

Code:

5                 <--- Top of stack
9

Notice that 5 is on the top.

Where are we now? Line 3 again. Is n == 0? No it's 1. So we call pb() again... repeat the above stuff pushing onto the stack and the stack now looks like:

Code:

5                 <--- Top of stack
5
9

Back at line 3 (again!) :-) Is n == 0? Yes! Yay!

What do we do? Return from the function. Where do we return to (and continue execution from)? Line 5 (it's what's on top of the stack). So it takes 5 off the top and starts whizzing away again at line 5. The stack will look like:

Code:

5                 <--- Top of stack
9

So we go to line 5. Line 5 prints whatever '0' + n % 2 is and then looks for where to return to? Whatever address is at the top of the stack. In this case, 5.

Stack is now

Code:

9

So we go to line 5. Line 5 prints whatever '0' + n % 2 is and then looks for where to return to? Whatever address is at the top of the stack. Now it's 9.

thanks I got it now.
Just another question on the inner workings of the program..
Same code but passing value 3.

Code:

(a) 3 != 0   /*next instruction pushed onto stack*/
(b) pb(n / 2) /*and putchar('0' + n % 2) is pushed onto stack!*/

At this point in time, what is putchar('0' + n % 2)?
I thought it is '0' + 1 % 2 , since n/2 was executed in the previous line?

edit: "When you call a function, one of the things it does it puts the *next* instruction in the current context onto a stack" - Sirprattlepod
Answer is '0' + 3 % 2. Can I say this? The current instruction is pb(3/2) and the next instruction to be executed is putchar('0' + 3%2).

Code:

#include <stdio.h>

/*function prototype*/
void pb(int n)
{
	if (n != 0)
	{
		pb(n/2);
		putchar('0' + n % 2);
	}
}			/* We are here once n hits 0*/

int main()
{
	pb(3);

	getchar();getchar();
	return 0;
}