• 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

Recursion and stackoverflow

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am trying to solve this https://www.hackerrank.com/challenges/java-1d-array
I am using recursion for this but it gives me this error Exception in thread "main" java.lang.StackOverflowError at Solution.game(Solution.java:76)
I don't how to optimize this program though I've no mentor and I can't afford it but I can work hard. For few days I'm struggling with my own code.
Its very frustrating. Please see my code and tell me I'm fit for programing or I should move or Please tell me how to optimize this code.

 
author
Posts: 23951
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

Abhi Pande wrote:
I am using recursion for this but it gives me this error Exception in thread "main" java.lang.StackOverflowError at Solution.game(Solution.java:76)
I don't how to optimize this program though I've no mentor and I can't afford it but I can work hard. For few days I'm struggling with my own code.



A stack overflow basically means that you ran out of stack memory -- you went too deep in your recursive algorithm. Now, it is theoretically possible for your recursive algorithm to go ridiculously deep, but more commonly, this is a problem due to a bug.

I recommend printing out the state, before and after a recursive call. This way, you can tell how deep your recursion is going -- and how much, or even if, you are making any progress.

Henry
 
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You are trying to do too much with discrete logic where recursion can make it much simpler. The rules for moves are pretty straight forward: -1, +1, or +m. You'll just need to call game() three times; one for each. You'll also need to keep track of which positions you've already visited so that you don't end up in an endless loop.

Just a piece:

 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Abhi Pande wrote:Its very frustrating. Please see my code and tell me I'm fit for programing...


Well, you've certainly put some effort into it, and that's a good sign. You also clearly have a grasp of Java language basics, which is another.
I'm afraid frustration comes with the territory - even for us so-called "experts" - so we can't help you there.

The main problem I see is that you're trying to code a solution, and that's not likely to work. When you write a class like 'HelloWorld' you can dive straight into code, but as problems get harder - and yours actually says "(Hard)" - you have to StopCoding (←click) and think.

Coding is a linear process, and I suspect you're getting yourself tied in knots trying to think it through step-by-step (what Campbell refers to as "discrete logic"), when what you need to do is step back and look at the problem as a whole.

Here's a couple of questions for you:
1. Forget about the rules and Java for a moment. What is the object of the game?
  Your answer shouldn't take more than about five words.

  (Hint: what if I told you that the game was called 'Escape'?)

2. The instructions refer to a "move". Describe to me, in English, exactly what a single move is.

HIH

Winston
 
Marshal
Posts: 8857
637
Mac OS X VI Editor BSD Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In addition to what Winston nicely trying to help you to come up with.

Always remember one three things about recursion.
A recursive function on its own normally has two parts:

1. Stopping condition.
Processing the case where the recursive function does not call itself.

2. Recursive step.
Processing the case where the recursive function calls itself.

Most important part:
The recursive call must have different parameter values than those of the calling function because otherwise the program gets into an in finite loop.
And the infinity loop usually means one single thing which you already discovered.
 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just some minor comments on your code in general.
Please fix the indentation. I had to reformat it in order to follow what you were trying to do. Consistently use either spaces or tabs, not both.
game() should return a boolean instead of an int.
"move = move + m;" is better written as "move += m;"
"move = move + 1;" is better written as "move++;" (ditto for "move = move - 1;")
The variable you have called move, seems more like a position to me. I would consider the act of changing the position to be a move (e.g. position++).

Your efforts are applaudable, it is after all, "(hard)".
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic