Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
March 9th, 2003, 04:36 PM
 balance
.

Join Date: Dec 2002
Posts: 296
Time spent in forums: < 1 sec
Reputation Power: 11
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
March 9th, 2003, 05:07 PM
 Gmorphus
Contributing User

Join Date: Sep 2001
Location: ISRAEL
Posts: 35
Time spent in forums: < 1 sec
Reputation Power: 13
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...
__________________
"Gravitation can NOT be responsible for people falling in Love"
(one of the most significant characters in the history, can you guess?)

Gmorph.

#3
March 9th, 2003, 05:09 PM
 Jason Doucette
jasondoucette.com

Join Date: Feb 2003
Posts: 378
Time spent in forums: 7 h 23 m 8 sec
Reputation Power: 11
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
March 9th, 2003, 05:11 PM
 Jason Doucette
jasondoucette.com

Join Date: Feb 2003
Posts: 378
Time spent in forums: 7 h 23 m 8 sec
Reputation Power: 11
Quote:
 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
March 9th, 2003, 05:17 PM
 Gmorphus
Contributing User

Join Date: Sep 2001
Location: ISRAEL
Posts: 35
Time spent in forums: < 1 sec
Reputation Power: 13
Yup

and with no offence for balance, I think he has some more basic misunderstanding than your explanation.

#6
March 9th, 2003, 05:56 PM
 balance
.

Join Date: Dec 2002
Posts: 296
Time spent in forums: < 1 sec
Reputation Power: 11
thanks for the replies.

Quote:
 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
March 9th, 2003, 06:35 PM
 Jason Doucette
jasondoucette.com

Join Date: Feb 2003
Posts: 378
Time spent in forums: 7 h 23 m 8 sec
Reputation Power: 11
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
March 9th, 2003, 07:54 PM
 balance
.

Join Date: Dec 2002
Posts: 296
Time spent in forums: < 1 sec
Reputation Power: 11
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 08:07 PM.

 Viewing: Dev Shed Forums > Programming Languages > C Programming > the whole recursive function is run each time?