• 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Junilu Lacar
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • Devaka Cooray
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Paweł Baczyński
  • Piet Souris
  • Vijitha Kumara

java.lang.StackOverflowError caused by recursion

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I want to design a method to compute the sum of numbers store in an array using recursion. This is what I have came up with.
   
This would cause the said error, I've checked it for anything that could cause the recursion to never terminate but still don't know what's wrong with it. Help :((
 
Marshal
Posts: 14337
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your bug is pos++ on line 6.

Think about it... what is the value you are passing?
 
Junilu Lacar
Marshal
Posts: 14337
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
and Welcome to the Ranch!
 
Marshal
Posts: 7264
492
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I also disagree with your base case, even though it doesn't affect final outcome.

Logically it doesn't look correct to me to add 0 just because you don't have more indices to look for elements at.
 
Junilu Lacar
Marshal
Posts: 14337
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why not, Liu? 0 is the identity value for addition so to me it does make sense. You can't return nothing since that wouldn't compile.
 
Liutauras Vilda
Marshal
Posts: 7264
492
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:Why not, Liu? 0 is the identity value for addition so to me it does make sense. You can't return nothing since that wouldn't compile.

After submitting a post had a second thought, but the initial thing came to mind wast just return the last number from an array at index arr.length-1 (meaning that's the base case), but I might mistaken about that.
 
Junilu Lacar
Marshal
Posts: 14337
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That would give wrong results for the code OP wrote. The identity value for addition is the appropriate value to return for the base case OP is using here.
 
Liutauras Vilda
Marshal
Posts: 7264
492
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:That would give wrong results for the code OP wrote.


What I had in mind probably it wouldn't produce a wrong result, but I agree now, that probably that would be a more complicated solution than OP came up with.

@OP
Apologies for confusion. Indeed, the error is there where Junilu mentioned, other than that - it is a great solution.

By the way, please improve formatting. Your braces alignment isn't conventional, it should be at the same line with method's declaration start:

 
Liutauras Vilda
Marshal
Posts: 7264
492
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:...but the initial thing came to mind wast just return the last number from an array at index arr.length-1 (meaning that's the base case)...


I was thinking more... if I could somehow justify, why this answer would be more approapriate. Not saying it is, but just tried to come up with some argument.

If somebody would ask, now improve the algorithm so it would count the number of sum operations made. I think that approach in the quote would be very easy to modify.
 
Liutauras Vilda
Marshal
Posts: 7264
492
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@OP

The algorithm you got right, so I guess we just need to clarify, whether you understand why passing pos++ as an argument really was a mistake?
 
Marshal
Posts: 66189
250
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:. . . last number from an array at index arr.length-1 . . .

What about the corner case where the array is length 0?
 
Junilu Lacar
Marshal
Posts: 14337
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Having dabbled with Scala, I tend to think of these things in more abstract terms, like head:tail

The expression pos == arr.length translates to head == nil and tail == nil

The expression pos == arr.length - 1 also translates to tail == nil in a way but it also says "if head is the last element" so that's why you have to return head instead of the identity value of 0 in your base case. Your approach does one less recursive call than OP's but OP's seems like a "purer" recursion in my opinion, if there is such a thing, because it goes all the way down to the degenerate case and returns the identity value, 0.
 
Junilu Lacar
Marshal
Posts: 14337
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Liu and of course there's what Campbell pointed out. It looks like the solution you have in mind can't handle empty arrays.
 
Liutauras Vilda
Marshal
Posts: 7264
492
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Indeed, Campbell's point putted all in the right places. The approach I had in my mind wouldn't handle that. Good, all on the same page. That just shows how one's mind can't always foresee all the cases without throughout testing solution.
 
Campbell Ritchie
Marshal
Posts: 66189
250
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry not to have been active recently; I had a busy day yesterday, including treading the boards as some people already know. You have raised an interesting point there. Liutauras has already show the correct way to call a recursive method: use  + 1 (or  − 1).
 
Saloon Keeper
Posts: 6416
60
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When I have recursive methods that require a parameter that is a fixed known starting point then I also supply an overloaded form of the method with a simpler interface that guarantees that the correct starting point will be passed.
 
Bartender
Posts: 3606
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Absolutely agree

@all
I do not like returning a 0 when the array is empty. After all, what is the sum of some non-existing numbers? Reminds me of that Zen parabel: what is the sound of one clapping hand?  

 
Carey Brown
Saloon Keeper
Posts: 6416
60
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey Brown wrote:When I have recursive methods that require a parameter that is a fixed known starting point then I also supply an overloaded form of the method with a simpler interface that guarantees that the correct starting point will be passed.

Also minimized magic numbers creeping into application.
 
Campbell Ritchie
Marshal
Posts: 66189
250
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:. . . what is the sum of some non-existing numbers? . . .

0

If 0 is the identity value for addition, then the sum of no numbers vacuously reduces to 0.

I see I didn't get my HTML tags right earlier; I shall go back and correct them.I see I didn't get my HTML tags right earlier; I shall go back and correct them.
 
Piet Souris
Bartender
Posts: 3606
151
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My collegue used to warn the IT'ers in the 80's: beware: 0 is not nothing!

Is the product of some non-existing numbers 1, for the same reason?
 
Campbell Ritchie
Marshal
Posts: 66189
250
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes. I did say vacuously.
 
Junilu Lacar
Marshal
Posts: 14337
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Wikipedia entry for 0 wrote:Zero is a number which quantifies a count or an amount of null size


Math theory and pedantics aside, either return 0 or throw an exception for an empty collection of numbers. Those are the two most sensible things I can think of doing, the former IMO being the more sensible of the two.
 
Carey Brown
Saloon Keeper
Posts: 6416
60
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Or "Optional".
 
Piet Souris
Bartender
Posts: 3606
151
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Yes. I did say vacuously.


You did indeed, but I did not know what 'vacuously' meant. Just googled for it, and I still don't know what you mean. Anyway, I would not return an empty Optional, but I would throw some horrible error, that'll teach the sender of the arguments.
 
Carey Brown
Saloon Keeper
Posts: 6416
60
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:I would not return an empty Optional, but I would throw some horrible error, that'll teach the sender of the arguments.


Indeed.
 
Bao Truong
Greenhorn
Posts: 3
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:@OP

The algorithm you got right, so I guess we just need to clarify, whether you understand why passing pos++ as an argument really was a mistake?


I need to use pos+1 instead because pos++ will only increment pos after the method have used it?
 
Bao Truong
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you very much guys for the help.
 
Campbell Ritchie
Marshal
Posts: 66189
250
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:. . . I still don't know what you mean.

Vacuous means “empty” in the sense of “empty‑headed”. Something is evaluated vacuously as the default value when there is no information to change it. So you would return the identity value. The identity for ∀ or ∧ is true, the identity for ∃ or ∨ is false, the identity for multiplicative operations is 1 and for additive operators it is 0. At least I think they are.

Anyway, I would not return an empty Optional . . .

Agree. Even though the value is arrived at vacuously, there still is a value, so an empty Optional would be inappropriate.

If you go into program semantics, you find that the weakest precondition for a program guarded by false to establish postconditions even dafter than theChequesInThePost evalutes to true. That is because the program never runs, so it is never possible to un‑establish that postcondition. The weakest condition becomes true vacuously because the set of circumstances causing that program to run is empty. Yes, you can get at best confusing results from such an evaluation.
 
Sheriff
Posts: 6363
172
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Bao Truong wrote:Thank you very much guys for the help.


Good job figuring it out!
 
Piet Souris
Bartender
Posts: 3606
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Campbell
Thanks for the explanation! New to me. But the Zen is getting worse, here: what is the sound of ZERO  clapping hands?    

But I guess it will have some uses, like 0!. Gonna dust off some very old texts on Logic, see if I missed something. But I suspect the saying "never too old to learn" has its exceptions.    
 
Saloon Keeper
Posts: 10762
229
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:what is the sound of ZERO  clapping hands?


Zero oscillations of my eardrum.
 
Junilu Lacar
Marshal
Posts: 14337
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:But the Zen is getting worse, here: what is the sound of ZERO  clapping hands?    


At the risk of pushing this even closer to the edge of MD, I'd offer "The same sound that ZERO falling trees make in the forest when ZERO people are around to hear it."
 
Liutauras Vilda
Marshal
Posts: 7264
492
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

so an empty Optional would be inappropriate


Can someone please elaborate a bit more why an empty Optional would be an inappropriate option here? To me it seems it is equally (or might even more) appropriate as throw an exception of some kind.

If somebody passes an array to a sum function with a hope to calculate sum of elements, and appears there is none elements to sum up, there should be some indication at least that there were no elements. Which in turn to return 0.0 makes me a worst handling strategy for that.

So what would you prefer? Optional or throw an exception? Why?

Piet saying that for the purpose of training user. Ok. What else?

Junilu in one of threads mentioned, that he barely sees Optional used in production codebases, maybe that's one of reasons, that people really don't understand its exact use along with use cases. I must admit I need to work on that too to understand it better.
 
Junilu Lacar
Marshal
Posts: 14337
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't understand why returning 0.0 when there are no elements to be added is such a big deal or why it would be considered worse than other options. To me, a 0.0 return value would be the LEAST surprising behavior and the most convenient because I wouldn't need to check for an empty collection unless I really needed to.

[rant]
How much do I have to pay if I have zero items in my shopping cart? A BIG FAT ZERO.

How much tax do I have remit if I have zero taxable items? A BIG FAT ZERO.

If having nothing to add is really a big deal, then I can always do a precheck before calling the method that adds things up:

Why make things any more complicated than it needs to be?
[/rant]
 
Carey Brown
Saloon Keeper
Posts: 6416
60
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
 
Stephan van Hulst
Saloon Keeper
Posts: 10762
229
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Returning 0 is the only acceptable option to me.

If we didn't have zero to express the lack of things to sum together, we'd be back in the time before Fibonacci introduced Arabic numerals to Europe.
 
Stephan van Hulst
Saloon Keeper
Posts: 10762
229
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My last post was in response to the sum of a collection of numbers.

The product of an empty collection of numbers is 1. It's the only thing that makes sense mathematically.
 
Liutauras Vilda
Marshal
Posts: 7264
492
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:I don't understand why returning 0.0 when there are no elements to be added is such a big deal


I guess I wouldn't have any doubt if it were:


Junilu Lacar wrote:

But in order to ensure, that returned result (sum) is in fact the result of the collection/array you intended to pass (and not somewhat wiped out, meaning with no elements), one has to introduce such check. Isn't that what Optional would serve, just in nicer way?
 
Junilu Lacar
Marshal
Posts: 14337
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:But in order to ensure, that returned result (sum) is in fact the result of the collection/array you intended to pass (and not somewhat wiped out, meaning with no elements), one has to introduce such check. Isn't that what Optional would serve, just in nicer way?


I've always preferred to make design choices based on present needs, not on speculation that something might happen. To me, the most sensible first cut would be:

and expect that to show $0.0 if the cart was empty.

Now, if somebody said, "We need to display the message 'Your cart is empty' because users might get confused if they see $0.00 when they haven't even picked anything to buy yet."

I would be like "Hmmm... ok..." (mumble grumble under my breath and say something along the lines of "If you make a program that even idiots can use, only idiots will use it."). Then I'd write something like this:

Then someone on the team says, "Hey, we should use Optional because that's supposed to be better." So I might say, "Ok..." and refactor to this:

Then I'd go back to that person and review the code. I'd probably say, "So this is better, huh?"  

EDIT: Of course, that person might say, "Did you test this? Because that code is backwards." (I went ahead and edited it from before, where the display logic was backwards. What you're seeing now is the corrected version)  
 
Opportunity is missed by most people because it is dressed in overalls and looks like work - Edison. Tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!