# CodeStepByStep

## travel

Language/Type: PHP recursion recursive backtracking

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.
Function: Write a PHP function as described, not a complete program.