# Recursion help

Tiffany Rich
Greenhorn
Posts: 4
Hey Guys

New here so bear with me... I have a program that reads a text file into a two dimensional array. The text files that are read in can change so this is just an example. The file that is read in looks something like this>>

x x - - x - - - - - - x x - -
x x - - x - - - x - - - x - -
x x - - x - - x - - - - - - -
x - x - x x - - - - - - x - -
- - x - x x - x x x - - x - x
x x x - x x - x - - - - x - x
x x - - - - - - - - - - - - x
x x - x x - - x x x x - - - -
x x - x - - - - - - - - - x x
x x - x x x x x x x x x x - x

I have to use recursion that takes connected edges (diagonals don't count) so the output will look like this>>

A A - - B - - - - - - C C - -
A A - - B - - - D - - - C - -
A A - - B - - E - - - - - - -
A - F - B B - - - - - - G - -
- - F - B B - H H H - - G - I
F F F - B B - H - - - - G - I
F F - - - - - - - - - - - - I
F F - J J - - K K K K - - - -
F F - J - - - - - - - - - L L
F F - J J J J J J J J J J - L

My question is I don't even know where to start to come up with code to detect the appropriate edges. Any help or hints would be great!

David Harkness
Ranch Hand
Posts: 1646
Your first task, as with any program, is to break it down into discrete steps. This is an iterative process, meaning that you start with a single step -- "solve the problem" -- and break that step into smaller steps. You then recursively break those steps into smaller steps, and so on until all of the steps are "sufficiently small." Defining this latter term comes with experience.

One first cut at breaking it apart might be
• Read the input file into a data structure.
• Find all of the contiguous blocks.
• Write the complete solution to the screen of file (whatever assignment says).

• Clearly, these are still pertty big steps. You'll need to think about how to break it down further. Instead of having us do it for you, which will teach you nothing, try it out yourself and post what you can get. I'm sure you have some ideas about this, so let's have 'em!

Now, you don't necessarily have to break all the steps down into detail before you start. This is key! If you start by working on the first step, you can ignore the other two for now. I'd even recommend that you do #1 and #3 before attempting #2 for the simple reason that without #3 you won't know when you have #2 working.*

[ * True, you could write up an algorithm to programmatically test your solution, but I think that's a bit beyond the beginner level. ]
[ February 03, 2005: Message edited by: David Harkness ]

Marcus Laubli
Ranch Hand
Posts: 116
Hey Tiffany,

This one looks like lots of fun.

I'll be watching to see how David helps you. Like he said, just take one small step at a time.

I'm sure that there's lots of help here on this site, but as one of my mentors says, I'd rather you sweat for half an hour before I give you the answer!

... as he tiptoes away, hoping that Marilyn doesn't see this!

She's actually right.
[ February 03, 2005: Message edited by: Marcus Laubli ]

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
I'm absolutely with David on breaking this down. Get the file & data structure stuff out of the way before you try to solve the real problem. For that I'll give you some hints, but no Java ...

It's fun to think about these problems as if you're walking among the squares on your board, or if you're old enough to remember adventure games "You are standing in a maze of twisty passages, all alike."

Imagine you are standing in the top left square. It has a * so mark the square with an A, then look around. Look East and you see another *, so you go to that square, mark it with an A and look around. Look East, find an empty, look South, see another * and ... well, the same darned thing over and over. When you finally reach a dead-end, start backtracking until you reach a square where you have not yet looked all four directions.

See if you can translate that to Java. Recursion hurts your brain the first time, but after that it's great fun.

Marc Peabody
pie sneak
Sheriff
Posts: 4727
I would make my first step to get the program working without the recursive part. In other words, make it so your output is:
A B - - C - - - - - - D E - -
F G - - H - - - I - - - J - -
K L - - M - - N - - - - - - -
etc.

After that, you can slip the recursion in without having to change what you've already done.

marc weber
Sheriff
Posts: 11343
Hmmm... Reminds me of Minesweeper -- figuring out which adjacent tiles to automatically "open."