logo CodeStepByStep logo

travel

Language/Type: C++ recursion exhaustive search
Author: Marty Stepp (on 10/18)

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).
travel

You may assume that the x/y values passed are non-negative. If x and y are both 0, print a blank line.

The table below shows several calls to your method 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      

Constraints: Your solution must be recursive. Do not use any loops in solving this problem.

Type your C++ solution code here:


This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.


Log In

Need help?

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.