Help coderanch get a
new server
by contributing to the fundraiser
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Recursive class definition

 
Ranch Hand
Posts: 1032
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I just found out that you can't have a class with an instance member of its own type (and it is easy to conclude that it would be also a problem to have an instance member of any of its subclasses.) It is possible however to have a static member of the same type as the class it is in.

This is because when you create the first instance of the class, that object will have a member of that class, so the constructor will run again, and will continue so until you get a stack overflow. The compiler doesn't detect this, but it fails at runtime (StackOverflow is not checked.)

Example:


[ December 18, 2008: Message edited by: Ruben Soto ]
 
Sheriff
Posts: 9708
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


If you remove the initialization of the recursive object, then it will be no problem...
 
Ruben Soto
Ranch Hand
Posts: 1032
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That's a good point, thanks. The main thing is not to initialize the member.
 
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

In the above code we will get StackOverflowError
BUT

In this case output will be "This will never print".

Please correct me if I am wrong.

Anand
 
Ankit Garg
Sheriff
Posts: 9708
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
yes anand you are right. Since the field is static, so it will only be created once and not when every instance of the class is created...
 
author
Posts: 23956
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Ruben Soto:
That's a good point, thanks. The main thing is not to initialize the member.



No. It's perfectly valid to initialize the member. You just can't do it blindly -- with any recursive call, you need a way to exit from it.

Henry
 
Ruben Soto
Ranch Hand
Posts: 1032
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I didn't meant that it is illegal to do so, only that it leads to bad consequences. Out of curiosity, how would you avoid the stack overflow in the above scenario? When an object is instantiated, top-level initialization code (including initialization blocks and top-level instance member initializations) is executed before the code within the constructor that comes after the implicit super() call, or the explicit this() or super() call, which means that a call to the constructor for the instance member would take place even before the call to the constructor for the containing instance would have completed. The static initialization code runs before that, but I think it would be impossible to have any code in the static initialization code that would prevent the constructor for the recursive instance member from being initiated.

Back to my question, how could you avoid the stack overflow in the above scenario then? I'm sure I must be missing something.
[ December 18, 2008: Message edited by: Ruben Soto ]
 
Henry Wong
author
Posts: 23956
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Back to my question, how could you avoid the stack overflow in the above scenario then? I'm sure I must be missing something.



What you are missing is a way to stop the recursion. This is true when you do anything recursively. You need boundary cases, where the algorithm can solve the problem without making a recursive call.

Now, this example is totally silly (meaning useless, doesn't do anything). But regardless... here is another silly example that doesn't have the stack overflow problem.



Henry
 
Ruben Soto
Ranch Hand
Posts: 1032
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I can see that the code you provide avoids boundless recursion (and thus a stack overflow,) but your code deviates from the premise that the recursive instance member must be initialized in the top-level of the class in which it is defined (not within any method, because in that case it is not a top-level initialization.)

My hypothesis, for the reasons I explained in my previous post, is that in that scenario a stack overflow can't be avoided. Am I missing something?

Also, I am aware of the high degree of silliness of the code. Most of these questions are silly (as in useless, worthless, of no practical value) when taken in their own, but they are useful in that they prove theoretical points, and in that they can be of value when taking the SCJP exam (which appears to have its own share of "silly" questions.)

Thanks for taking the time to respond.

Edit: I just reread my post, and I think I might have not made it sufficiently clear that I meant initialization to take place exclusively at the top-level. My apologies for that.
[ December 18, 2008: Message edited by: Ruben Soto ]
 
Henry Wong
author
Posts: 23956
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

but your code deviates from the premise that the recursive instance member must be initialized in the top-level of the class in which it is defined (not within any method, because in that case it is not a top-level initialization.)




First of all, what the heck is "top-level initialization"?

Second, it isn't a method call. It is part of the constructor for the class. Initialization of instance variables, instiance initializers, and constructors are all called during the construction of an object -- some just gets called before others. So, this is called as part of the "new" operator -- which initializes the object.

Henry
 
Ruben Soto
Ranch Hand
Posts: 1032
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
By top-level-initialization I mean explicit initialization at the class definition's top level (not within a constructor, not within a method.) For example:



Regardless of whether the recursive instance member gets called from within the class's own constructor or one of its methods, it isn't at the top level. My original question is: If the initialization of the recursive member (using an explicit constructor call for the same class it is defined in) happens at the top level (outside any methods or constructors) is a stack overflow avoidable or not?

Sorry if I am not making myself clear enough, let me know if I can clarify farther.
[ December 18, 2008: Message edited by: Ruben Soto ]
 
Henry Wong
author
Posts: 23956
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
To clarify a bit more... Initialization of instance variables, and execution of instance initializer are done during the construction of an object. The compiler actually copies the initialization code into every constructor for you...

This means that this code...



And this code...



Are the same thing (should generate the same bytecodes) !! There is no different level of initialization by avoiding the use of a constructor. Everything is done in the constructor.

Henry
[ December 18, 2008: Message edited by: Henry Wong ]
 
Ruben Soto
Ranch Hand
Posts: 1032
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you for the explanation, Henry. That clarifies things. I still think though that even it is true that the listings that you provide are equivalent, a stack overflow can be avoided in the second case, whereas in the first case is unavoidable. Let me give it a try:



The code above avoids stack overflow. However, there is no possible way that I can think of to avoid stack overflow in the first case, if you do not modify the line

If you want to avoid stack overflow that line must go (which is my original hypothesis.) At least, that's what it looks like.

Thanks for your explanations, they are much appreciated!
[ December 18, 2008: Message edited by: Ruben Soto ]
 
I love a woman who dresses in stainless steel ... and carries tiny ads:
We need your help - Coderanch server fundraiser
https://coderanch.com/t/782867/Coderanch-server-fundraiser
reply
    Bookmark Topic Watch Topic
  • New Topic