• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursion and stackoverflow  RSS feed

 
Abhi Pande
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • 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.

 
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
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
 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • 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:

 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • 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
 
Liutauras Vilda
Sheriff
Posts: 4918
334
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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)".
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!