File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Java Recursion method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Java Recursion method" Watch "Java Recursion method" New topic
Author

Java Recursion method

Rivosk Hogerop
Greenhorn

Joined: Dec 16, 2011
Posts: 2
Hi,

I have a question about a small pathfinding problem.
I got a 2D table which symbolize a labyrinth.
The table only contains a ' '(white space), a 'B', a 'E' and a 'W'
B: begin position
E: end position
W: wall

I need to write out all the pads from B to E.
(a) I may not cross a wall
(b) I may not move to a position I have already been before. (in the same pad)

for example I have the following labyrinth: (ignore the [])
[M][ ][ ][ ][ ]
[B][ ][M][ ][E]
[M][ ][ ][ ][ ]

My java program needs to print out ALL the possible pads from B to E:
rurrrd
rurrdr
rurrddru
rdrrru
rdrrur
rdrruurd

I have written this little program.
It's an excercice from the exam from last year and I should be able to solve it with recursion.
But my program only print out 1 possible pad instead of ALL pads.
If someone can point me where and what I'm doing wrong I would be verry gratefull. (I'm practicing for my upcomming exam)
(excuse me for my bad english)

dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Are you sure that an Array is the best data structure to model your labyrinth? I might suggest exploring what you can do with a tree structure. I think a tree is better suited to your problem because the relationship of parent and child nodes is inherently suited to representing a path.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

i am not sure recursion is the best answer. i wrote an old homework that is similar to this. it only had to find one path though. i used an array and a stack of points. the code is here


SCJP
Visit my download page
Rivosk Hogerop
Greenhorn

Joined: Dec 16, 2011
Posts: 2
Hi thanks for your reactions.
It's not that i'm looking for the best way to solve this problem.
It's an exercise and we need to solve it with recursion. (on the exam I will have no other choice then recursion.)
(P.s.:we haven't seen any OOP)
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
I would create a node object which contains: the attribute of the room ('','B','E' or 'W'), a set of child nodes (the adjoining rooms), and a marker to tell whether or not it has been visited.

I would build out the tree from the labyrinth you have laid out in the arrays. We also need some indicator of how we are getting from room to room -- the path (u,d,l,r), and that will be the most difficult part of the problem.

But assuming you have that sorted, the pathfinding algorithm would be:



It is probably better, now I think of it, to wait until E is reached and then collect the path as we come out of the recursion, but you get the idea.
Mori Gad
Greenhorn

Joined: Dec 16, 2011
Posts: 16
The code itself, with very minor adjustments, does work. Not saying anything about recursion being the best option or arrays being worse.


Think about possible problems and ways of testing them.

You need to keep track of where you visited for the current path without blocking off the path for other solutions.

The large if statement could use some white space to make it more readable, for easier testing.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36452
    
  15
Welcome to the Ranch Curly Stoge.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3361
    
    9
Hi Rivosk. Problems like this become much easier when you first create some basic data structures to work with, which provide a few handy operations.

For instance, let's make a basic Labyrinth data type which provides methods to look at different directions, and to move into a new direction:
You now have a simple Labyrinth that has look(Direction) and move(Direction) methods. This should be plenty to implement some recursive method that finds all the paths to an exit.

Note that the trick here is that the move() method returns a new Labyrinth. You can call this method without worrying that your old labyrinth will be modified. In fact, the entire Labyrinth class here is immutable. This makes it very easy to work with.

As already has been mentioned, a tree is a good structure to represent paths with. If you don't want to use a tree, you can also use something like:List<List<Direction>>.
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Honestly, without a tree I don't know how you will be able to be sure that you have found every possible path. As Curly observed, your code works, but how can it be adapted to find more than one solution, let alone to exhaust all possibilities? With a tree you know definitively whether or not a branch has been explored.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3361
    
    9
The algorithm to find all the paths doesn't need to inspect a tree to figure out whether it exhausted all possibilities. Recursion takes care of this automatically.

You can write a simple recursive method getPathsToExit() that returns a list of paths, without ever using a tree.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

sure seems a lot harder than the homework i had
recursion is great, it is just hard for most of us mortals to figure out
glad you got some great help with it. i think i might have had a hard time with this one.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3361
    
    9
Some pseudo code:
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Java Recursion method
 
Similar Threads
Creating simple GUI interface for BattleShips
Using GridLayout as GUI
Brute Force
June Newsletter Puzzle
Two Dimensional Arrays