• 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

Java recursive method for beginner

 
Greenhorn
Posts: 5
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I need a help with this task:

Write a method that by given chessboard filled with figures on some square, coordinates of knight and king, finds whether the knight can reach the king. The other figures are marked with 'X'; spaces are empty squares.

I wrote this, but doesn't work, I have a problem with the recursive method , The error is stackoverflow.
I don't know how to rewrite the recursion to work...

 
Bartender
Posts: 5465
212
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Vily,

the first rule when it comes to recursion is: make your code easy to read! The mere subject of recursion is already difficult enough...  

The number one reason for a stack overflow is some infinite loop. for instance:

you let your knight visit the field (Kx + 1, Ky +2). Okay. But in the recursion you let that same knight visit the field (Kx - 1, Ky - 2),
bringing it effectively back to its starting point, ad infinitum...

So, first thing is: make your code better to read. For instance: you do not need to check the Kings position, since that is constant
in your 'killKing' routine.

Second: whenever your knight enters a field, mark that field as 'visited',  for instance by setting a[x][y] = 'x'. Then, whenever you want the knight
to go to another field, check whether that field is empty, That pevents entering an infinite loop.

There are some more remarks to be made, but let's see how you get on. Succes!

Greetings,
Piet
 
Vily Ivanova
Greenhorn
Posts: 5
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you for your immediate answer  
I rewrote the two things you say
I try this one :

But I wont my method check the eight possibles movements for the knight . If there is a coincidence return true, and if there isn't return false and stop.
But I don't know how to make stop the recursive method at first check for every direction ...
If someone can help me?
Thanks !
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Vily,

well, it certainly looks a lot better now, don't you agree?

Now, let's put some more structure into your routine. As I said: recursion is not an easy subject, so at least make the code as readable as possible.

Therefore, I suggest the following pattern.

in your routine 'killKing(...)' you return a boolean, that is true if the horse position equals the kings position, and false otherwise.
(as an aside: a horse is called 'knight' in english chess)

Now, for one thing, this horse position can never equal the kings position if the horse field is outside of the board! So, let's check that as the very first thing (and also to avoid indexOuOfBound-errors in the rest of the routine):



Okay, coming here we know that the field is legal. But maybe it is occupied? (either in the set up or because our horse already visited this field?) Let's check for this as well:



allrright, coming here we have a legal field that is also unoccupied (apart from the king, that is!). so, lets check if the king is here:



Well, coming here, we have a legal field that is not occupied and does not contain the king. We enter our recursion!

But wait: before doing that, lets mark our field as occupied, to prevent entering this field yet another time


Here we go with our recursion:


Hmm. at this point we have to admit defeat: we are unable to reach the kings position.


Why do we now not see any stack overflow errors?

Success!

Greetings,
Piet
 
Vily Ivanova
Greenhorn
Posts: 5
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Piet,
Thanks for your precise replay.
Here, in bulgarian chess knight is call "horse" .  And I use it, because the letter is different from the letter 'k' of the king
After that I try it ,  Is that ok ?

Now i don't have stack over flow error, but I think there different error in my code ....
This code return all the time true, if the position of the knight is in the borders.
For example I tried with this call of the function : killKing(board, 0, 1, 4, 7)).
Why the behavior of my function is that?

Regards,
Vily

 
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

I think you meant
 
Piet Souris
Bartender
Posts: 5465
212
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Vily Ivanova wrote:Hi Piet,
Thanks for your precise replay.


You're welcome!


Here, in bulgarian chess knight is call "horse" .  And I use it, because the letter is different from the letter 'k' of the king
After that I try it ,  Is that ok ?


Here in Holland we also call it 'horse'. In my programs that relate to chess, I use an 'N' for 'kNight'. In Germany
they call it 'Springer', so an 'S' might be handy as well.


Now i don't have stack over flow error, but I think there different error in my code ....
This code return all the time true, if the position of the knight is in the borders.
For example I tried with this call of the function : killKing(board, 0, 1, 4, 7)).
Why the behavior of my function is that?


Well, there is a bug, but Carey already mentioned it. Thanks Carey.
Besides: it is always possible that a horse can jump from any field to any other field, on an NxM board.
(That is not true, by the way, for general NxM). In that case you could always get 'true' as the outcome.
So, it all boils down to a decent testing of your program.

As the very first thing in 'killKing' print out the position of the horse and the king.
Just before you return, print out the reasom for this return (for instance: field occupied').

And then, start testing it on a 3x3 chessboard, with the horse starting in the center. Then the outcome
must be 'false'. Et cetera.

But anyway: even in your opening post, you had a very nice recursion, and you also made use
of the code tags. All in all, reasons for a well deserved cow!

Greetings,
Piet
 
Vily Ivanova
Greenhorn
Posts: 5
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Piet and Carey for the help
I have learned interesting and helpful things
and I have understood where I have made mistakes
Thanks!

Greetins,
Villy
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic