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

    Join Date
    Dec 2002
    Posts
    296
    Rep Power
    12

    the whole recursive function is run each time?


    there's something about this recursion example i don't understand:

    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. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2001
    Location
    ISRAEL
    Posts
    35
    Rep Power
    14
    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.
  4. #3
  5. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    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.
  6. #4
  7. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    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! :)
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

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

    and with no offence for balance, I think he has some more basic misunderstanding than your explanation.
    "Gravitation can NOT be responsible for people falling in Love"
    (one of the most significant characters in the history, can you guess?)

    Gmorph.
  10. #6
  11. No Profile Picture
    .
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2002
    Posts
    296
    Rep Power
    12
    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.
  12. #7
  13. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    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.
  14. #8
  15. No Profile Picture
    .
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2002
    Posts
    296
    Rep Power
    12
    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.

IMN logo majestic logo threadwatch logo seochat tools logo