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

    Join Date
    Jul 2003
    Posts
    78
    Rep Power
    12

    Recursion, 2 ways of it ending?


    Hello all,

    I'm trying to remember a statement my C++ instructor told me about recursion, some 5 years ago. Something about there only being 2 ways for it to stop running.

    1. A condition is met and processing control leaves the method.
    2. System memory is reached and the whole machine crashes.

    Does this sound right or am I missing something?
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2002
    Location
    NYC
    Posts
    79
    Rep Power
    13
    The point is, without a terminating condition, a recursive call will just keep running.

    How the system deals with it is up to the system. It might simply say that there are only so many levels of calls it will allow, or throw up when it runs out of memory.

    Csaba
  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    10
    Rep Power
    0
    Also, for most operating systems the whole machine won't crash, but your process will encounter an error - most likely stack overflow. Maximum stack size is often considerably less than the system's total memory, and it's usually configurable. You can often catch the error for debugging purposes, though the mechanism depends on your platform.
  6. #4
  7. Perl Monkey
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    May 2003
    Location
    the far end of town where the Grickle-grass grows
    Posts
    1,860
    Rep Power
    109
    You mean it either stops or loops endlessly (until a possible crash)? Isn't that true of any program?
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    78
    Rep Power
    12
    I meant that the program cause instability on the system. Of course the way it would deal with the problem depends on platform, language, swap, etc.

    By having the associated overhead for calling a function continue to be allocated for each call in the thread stack, it acts as a memory leak and eventually will use up all of the memory on the machine.

    Nevermind, I just remembered the 3rd reason recursion would stop.

    1. A condition is met and processing control leaves the method.
    2. System memory is reached and the operating environment becomes unstable (possible process crash).
    3. Process terminated by user.
  10. #6
  11. Doggie
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2003
    Location
    Seattle, WA
    Posts
    751
    Rep Power
    13
    Wouldn't #3 be a condition for #1?
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    78
    Rep Power
    12
    Not really, I was thinking kill -9 instead of System.exit();
  14. #8
  15. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    28
    Rep Power
    0
    basically, unless you are using 'tail end recursion' with a recognising compiler (you probably arent), each time you call a function (even from itself), you add a new stack frame. eventually you run out of room on the stack.

    then you will get a stack error.

IMN logo majestic logo threadwatch logo seochat tools logo