|
|
RecursionExercise
DescriptionRecursion Exercise
There is a trail in a forest that has many forks in it.
When you arrive at each fork, you can go either left or right,
each taking you down a new path.
Every path leads to a fork, a dead end, or an exit.
The trail starts with a single path that leads to the first of many forks.
Assume that given a path p,
you have methods p.isFork(), p.isDeadEnd(),
and p.isExit(), and if it is a fork,
p.left() and p.right() will return the left and right paths.
- Write a recursive algorithm that will allow you to traverse
through this forest until you find an exit, or determine there is none.
- Write an algorithm for the above problem that does not use recursion.
(Hint: You will need a stack.)
|