programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Java recursive method for beginner

Greenhorn
Posts: 5
1
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...

Master Rancher
Posts: 2289
76
• 1
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

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
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
Master Rancher
Posts: 2289
76
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
Hi Piet,
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: 3713
47
• X 2

I think you meant

Piet Souris
Master Rancher
Posts: 2289
76
• 1

Vily Ivanova wrote:Hi Piet,

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
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