|This is a split of this post which was originally intended to discuss a specific problem with recursion.|
The original topic got hijacked into a discussion of stack overflows and compiler optimizations. While this topic could be very interesting, it is likely to be a distraction to the original poster. Hence the split. The original poster's question, and all the posts since that point are listed below.
I got this far but can't get the code working properly. Recursion is sometimes difficult for me to grasp.
Contemporary compilers quickly recognize this and produce code that does not fail from 'recursion'.
Really? Try it. Convert your example code to Java. And you will notice that you will run out of memory (overflow the stack).
Originally posted by Chad Clites:
Isn't that an example of the computer science question "Can a computer recognize when it is in an infinite loop"?
Originally posted by Garrett Rowe:
That holds true if you're using the Sun JVM, IBM's or Microsoft's JVM may optimize a tail recursive call replacing it with a loop.
Originally posted by Henry Wong:
Well, let's try it...I purposely didn't implement any "more code goes here" because it may have a memory footprint.... and... well, I have a Sun JVM. Do anyone have an IBM JVM to try to with? As predicted, I got a stack overflow error.
When a compiler detects a call that is recursive, it overwrites the activation record instead of pushing a new one onto the stack. The compiler can do this because the recursive call is the last one to be executed in the current activation; thus, there is nothing left to do in the activation when the call returns. Consequently, there is no reason to keep the activation around. By replacing the current activation record instead of stacking another one on top of it, stack useage is greatly reduced, which leads to better performance in practice. Thus, we should make recursive functions tail recursive whenever we can.
I'm in the camp that wishes it could/would happen, but I don't lose sleep over it.