Thread: the whole recursive function is run each time?

1. No Profile Picture
.
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2002
Posts
296
Rep Power
16

the whole recursive function is run each time?

Code:
```void printd(int n)
{
if(n < 0) {
putchar('-');
n = -n;
}
if(n / 10)
printd(n / 10);
putchar(n % 10 + '0');
}```
the part i don't uderstand is that if say you called printd with printd(123); the line with putchar in at the end gets called 3 times, but the putchar is *after* the recursive printd call. so how can the putchar line be run on all 3 printd calls? it seems to me that putchar would only get called once: on the last prind call, the one that doesn't call itself. but that obviously isn't what happens. how come?
2. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2001
Location
ISRAEL
Posts
35
Rep Power
17
all the lines of the recursion gets called. it doesn't matter if it is after or before the recursion call.

let's simulate the function with 123:
(each "->" indicates level into the recursion)

1st call: printd(123)
-> n = 123
-> n<0? no...
-> n/10 = 12
-> if (12) // evaluates TRUE because 12 is nonzero
-> printd(12)
-> -> n = 12
-> -> n < 0? no...
-> -> n/10 = 1
-> -> if (1) // evaluates TRUE because 12 is nonzero
-> -> printd(1)
-> -> -> n=1
-> -> -> n<0? no...
-> -> -> n/10 = 0
-> -> -> if (0) // evaluate FALSE
-> -> -> putchar(1 % 10 + '0') // printing '1'
-> -> -> returning...
-> -> // continue from the line we call the recursion
-> -> putchar(12 % 10 + '0') // printing '2'
-> -> returning...
-> // continue from the line we call the recursion
-> putchar(123 % 10 + '0') // printing '3'
-> returning...
3. Perhaps the easiest way to understand what is going on (and perhaps the most convincing) is to run through the program yourself, keeping track of all variables.

But, here's my simple answer which may also suffice:

the putchar at the end of the function is not called from within an if-statement. And there are no return or exit calls that enable the function to quit before it reaches the end. Therefore, this putchar will be executed each time the function is called. If you can understand that this function is called 3 times, then you must also understand that this putchar is called 3 times.
4. Originally posted by Gmorphus
"Gravitation can NOT be responsible for people falling in Love"
(one of the most significant characters in the history, can you guess?)
Einstein! :)
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2001
Location
ISRAEL
Posts
35
Rep Power
17
Yup :)

and with no offence for balance, I think he has some more basic misunderstanding than your explanation.
6. No Profile Picture
.
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2002
Posts
296
Rep Power
16
thanks for the replies.

all the lines of the recursion gets called. it doesn't matter if it is after or before the recursion call.
yup this is the point i'm trying to get at. i spose i'd worked out that this is the case, but i would have thought that, at the printd recursive function call, it would start at the top of the printd function immediately after/from that printd call, not carry on and finish the whole function first.

the answer is, as you say, all lines of the recursion gets called. simple as that.

it's just that that seems a bit counter logical to me. normally when you call a function the thread of the code jumps to that function immediately from the function call, not carry on and do other lines first.

ok, thanks.
7. Ok, I think I better understand where you are thinking incorrectly.

Pretend that the call to printd from within the function is actually a call to some other function. What would you expect happen? You would expect that all lines before the function call are executed. Then the function is called, and it executes (it does whatever it is supposed to do, then returns). Then all lines after the function call are executed.

The exact same holds true for a recursive call. The fact that you are calling the same function from within itself means nothing. From the CPU's perspective, it doesn't even know, nor does it care that it is calling the same function. When a function is called, the CPU reserves new memory for its variables - so it is not the same variables being used during recursive calls. This is the same as a call to some other function, the CPU makes memory for these variables that exist only when the function's lines are being executed.
8. No Profile Picture
.
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2002
Posts
296
Rep Power
16
i see. the main body gets run three times and *then* the three final printchar lines.

it's the order or occurance and the fact that there are three returns and therefore three putchar lines, that i'd missed for some reason.

great, thanks :)
Last edited by balance; March 9th, 2003 at 07:07 PM.