• Post Reply Bookmark Topic Watch Topic
  • New Topic

Discussion on recursion, stack overflows, & compiler optimization for tail recurssion  RSS feed

 
John Lockheart
Ranch Hand
Posts: 115
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Andrew


I got this far but can't get the code working properly. Recursion is sometimes difficult for me to grasp. The whole premise for this code is you are given the command "S 0 1" => Is set 0 a subset of set 1?

[ June 24, 2007: Message edited by: Andrew Monkhouse ]
 
Nicholas Jordan
Ranch Hand
Posts: 1282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Without digging through your code, your base question is easy.


Early compilers and computers would keep building up a stack, that would eventually run out of room on the computer, trying to call this function again and again.

Contemporary compilers quickly recognize this and produce code that does not fail from 'recursion'.

There are many mathematical problems that lend themselves to this type of function and it makes a good practice area to study coding.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I got this far but can't get the code working properly. Recursion is sometimes difficult for me to grasp.


From what you got so far, it looks like you have grasp of some of it. There are some bugs with it, which you should be able to work through with a bit of help... so...

Are you getting an exception? If so, what kind of exception are you getting? What is the result are you getting? What are you expecting? etc.

Henry
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).

Henry
 
Chad Clites
Ranch Hand
Posts: 134
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Isn't that an example of the computer science question "Can a computer recognize when it is in an infinite loop"?
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Really? Try it. Convert your example code to Java. And you will notice that you will run out of memory (overflow the stack).


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.
 
David McCombs
Ranch Hand
Posts: 212
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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"?


Sounds like it, and the simple answer is sometimes, but not every case. So even if a compiler tries to insert instructions to stop a buffer overflow from recursive calls I wouldn't trust it.

Also, I seriously doubt that any compiler could know what the return condition is supposed to be for any given recursive method.

Back to the original question, as already stated you are close. A good debugging method for these sorts of problems is very low tech: a pencil and paper and walk through the code, keeping track of the data for each recursive function. When I am close to a correct solution, but isn't quickly obvious, I find this to be extremely helpful.
[ June 24, 2007: Message edited by: David McCombs ]
 
David McCombs
Ranch Hand
Posts: 212
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.


Even with the posted code with no recursive exit condition?



Thanks for linking that article, it is very interesting.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Henry
 
Nicholas Jordan
Ranch Hand
Posts: 1282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Henry


Let me do some reading and give some thought to this, I have set an interim target of writing an over-simplified, beginner-grade parser (which I believe falls into the challenge domain) - this would be a useful tool.

For the moment, let me respond with citation:

Mastering Algorithms with C Chap 3: Tail Recursion, para 2:

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.

Kyle Loudon (author of above) has been developing user interfaces and application software out of San Jose, California (Silicon Valley) in the San Francisco Bay Area for nearly 15 years.. Kyle is reachable at his contact page His training is: Electrical Engineering Technology (EET) Bachelor of Science Degree Program (BS) with Computer Engineering Technology , which from looking at their web page appears heavily E.E. oriented to me.

Cay S. Horstmann's Computing Concepts with C++ Essentials chapter fourteen gives a deeper discussion of the issue, stating that how the function is written affects it's compilation / execution path.
  • ISBN 1-56592-453-3 ( Louden )
  • ISBN 0-471-16437-2 ( Horstmann )
  • I am so fasicnated by this computer science stuff that I cannot even seem to attend to routine duties, but you just put this on my list and would like to know if you feel a simple parser falls within the scope of // .... more code goes here and the problem domain generally.

    Nick
    I see you are having a nice day:
  • 76�F
  • Clear
  • Wind: N at 6 mph
  • Humidity: 37%


  • [ June 24, 2007: Message edited by: Nicholas Jordan ]
     
    Jim Yingst
    Wanderer
    Sheriff
    Posts: 18671
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Nicholas, the original poster is asking a question about Java programming. It really doesn't matter how recursion may be implemented in other languages. Your statement "Contemporary compilers quickly recognize this and produce code that does not fail from 'recursion'" is badly misleading in this context, and no help in answering the poster's question. Stack overflow errors can and do occur in Java. Please stop distracting this thread away from the original poster's question. This might be a good time to start a new thread if you've got an alternate topic you want to discuss.
     
    Nicholas Jordan
    Ranch Hand
    Posts: 1282
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Jim, I thought I was doing really well at isolating the concept of tail-recursion, which can be thought of in a language independent manner. In paticular, comments by Garrett Rowe and David McCombs seem to discuss recursion in a language independed manner - which is what original poster posited: "Recursion is sometimes difficult for me to grasp." It seems to me consideration of why the machine would fail leads to an understanding of the base concept. I do not feel my efforts were badly misleading.

    Would this example, which isolates recursion instead of building what looks to me to be a tree be more acceptable solely because it is written in Java ?


    It sounds to me like you are positing that code written without consideration as to whether it will actually run in a fail-resistant manner is normalized practice in Java. If so, then I have some deep reconsideration to do.
     
    Henry Wong
    author
    Sheriff
    Posts: 23295
    125
    C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Can this topic be split please? It is not fair to the originally poster to keep this topic hijacked.

    Henry
     
    Andrew Monkhouse
    author and jackaroo
    Marshal Commander
    Posts: 12156
    256
    C++ Firefox Browser IntelliJ IDE Java Mac Oracle
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    This is now the split topic - please use it to discuss the computer theory, the JVM specification, tail recursion, or anything else related.

    Regards, Andrew
    [ June 24, 2007: Message edited by: Andrew Monkhouse ]
     
    Jim Yingst
    Wanderer
    Sheriff
    Posts: 18671
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    [Nicholas]: It sounds to me like you are positing that code written without consideration as to whether it will actually run in a fail-resistant manner is normalized practice in Java.

    I said nothing of the sort. But I'm not interested in getting sucked into another of these prolonged conversations where we go back and forth trying to figure out what the other person is saying. It's too much work. Just, please, when a poster asks a question about programming in Java, try to stick to examples and texts that are applicable in Java. Not about how you think a programming language [i]should[/i[ work. As far as I know, most Java compilers do not optimize tail recursion, and so telling a poster otherwise does not help them.
     
    Garrett Rowe
    Ranch Hand
    Posts: 1296
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Sorry about my part in *hijacking* the previous post. For those interested, here is the RFE, which discusses the problems associated with implementing tail call optimization in Java. The biggest problems I've seen have to do with error reporting, and stack-crawling. I'm in the camp that wishes it could/would happen, but I don't lose sleep over it. It would be nice to be able to write a concise, tail-recursive *fib* function (who needs one anyway?) that would be able to operate in constant space. But since Java does have loops, its not absolutely necessary. I've also read about Java regexes failing on large inputs due to the recursive nature its implementation, but usually this can be defeated with a more well-crafted regex.
    [ June 24, 2007: Message edited by: Garrett Rowe ]
     
    Henry Wong
    author
    Sheriff
    Posts: 23295
    125
    C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I'm in the camp that wishes it could/would happen, but I don't lose sleep over it.


    I'm completely lukewarm about it. IMHO, tail recursion optimization is a solution looking for a problem.

    It was a great solution for languages like prolog, where loops didn't exist -- recursion was the norm, and tail recursion was common. In languages with loops, recursion is not the norm, and tail recursion probably mostly exists in homework assigments where instructors forbid the use of loops.

    Henry
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!