Write a recursive function named travel that accepts integers $x
and $y as parameters and uses recursive backtracking to print all solutions
for traveling in the 2-D plane from (0, 0) to ($x, $y)
by repeatedly using one of three moves:
- East (E): move right 1 (increase
$x)
- North (N): move up 1 (increase
$y)
- Northeast (NE): move up 1 and right 1 (increase both
$x and $y)
The following diagram shows one such path to the point (5, 3).
You may assume that the x/y values passed are integers. If either $x or
$y are negative, your function should throw an Exception
with the message, "Error: arguments must both be non-negative integers." If
$x and $y are both 0, print a blank line.
The table below shows several calls to your function and the lines of output.
Your lines can appear in any order; our output shown tries the possibilities
in the order listed above: East, then North, then Northeast.
| Call |
Output |
Call |
Output |
travel(1, 2);
|
E N N
N E N
N N E
N NE
NE N
|
travel(2, 2);
|
E E N N
E N E N
E N N E
E N NE
E NE N
N E E N
N E N E
N E NE
N N E E
N NE E
NE E N
NE N E
NE NE
|
travel(2, 1);
|
E E N
E N E
E NE
N E E
NE E
|
travel(1, 1);
|
E N
N E
NE
|
Hint: It may help to define a private helper function that accepts different
parameters than the original function. In particular, consider building up
a set of characters as an array for eventual printing.
Constraints:
- Do not use any loops in solving this problem; you must use recursion.
