Recursion problem help C++

Question

I'm attempting to write code for checking if you can reach the end of the array by following a certain rule. You start at the first element of an array of integers and the number stored in that position is how many hops you can make forward or backwards. The goal is to reach the end of the Vector which is represented by the 0 value.

 bool Solvable(int start, Vector<int> & squares) {
        int steps = squares[start];
        int prev = start - steps;
        int forward = start + steps;
        if (prev >= 0) {
            if (squares[prev] != squares[start]) {
                return Solvable(prev, squares);
            }
        }
        if (forward < squares.size()) {
            if (squares[forward] == 0) return true;
            if (squares[forward] != squares[start]) {
                return Solvable(forward, squares);
            }
        }
        return false;
    }

The code does not seem to work because I think I am missing a base case, but I can't seem to figure out what other base case I need.

Thanks!

what do you mean when you say "does not seem to work"? does it reach an endless loop? behave wrongly? can you add an example of a squares vector and expected result? — NirMH
– NirMH, Commented Aug 17, 2011 at 4:58

john · Accepted Answer · 2011-08-17 05:49:02Z

4

There's a couple of problems. The first is that your code will only ever choose to go forwards or backwards, you never choose both. The reason is that you always say return Solvable. What you need instead is something like this

// try backwards
bool found = Solvable(prev, squares);
// did it work?
if (found)
  return true;
// oh well try forwards
return Solvable(forward, squares);

There's no check for the base case and no check for out of bounds here but hopefully you get the idea.

The second problem is your squares[forward] != squares[start] and squares[prev] != squares[start] tests. They don't seem to me to be part of the problem as you described it. I would drop them.

Nice problem to illustrate recursion BTW.

edited Aug 17, 2011 at 5:49

answered Aug 17, 2011 at 5:01

john

88.3k5 gold badges61 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

john Over a year ago

The more I think about this problem, the more I like it. A robust solution would also need a check that you are not in a cycle. You could for instance easily end up hopping forwards and backwards between two squares. Longer cycles would be possible as well. So you need to maintain a 'visited' boolean array. Initially this would be all false, and you would set it to true as you visited each square. That way you can make sure that you never visit the same square twice and so you avoid getting into an endless loop.

MSN Over a year ago

an easier way to detect loops is to run another loop twice as fast; if the two ever coincide without hitting the end point, you have a loop.

Matthieu M. Over a year ago

@MSN: it takes less memory and is usually advised for linked-lists of unknown length, but I think an array of bool would be much easier to understand. The OP is already struggling with recursion, let's not drown him!

molbdnilo Over a year ago

Or more concisely: return Solvable(prev, squares) || Solvable(forward, squares);.

john Over a year ago

@MSN: But this recusion isn't a simple loop. I don't think you can apply the hare and tortoise algorithm to it.

|

Ian Ross · Accepted Answer · 2011-08-17 07:55:46Z

Here's a version that detects cycles and keeps track of whether you've tried moving forwards or backwards from a particular square. The pattern of using a recursive helper function with a non-recursive front end to set up variables (here the fwd and bck vectors) to keep track of what you're doing is very common.

#include <iostream>
#include <vector>

using namespace std;

bool helper(int cur, const vector<int> &squares,
            vector<bool> &fwd, vector<bool> &bck)
{
  cout << "cur=" << cur << "  sq=" << squares[cur] << endl;
  if (squares[cur] == 0) return true;     // Found.
  if (fwd[cur] && bck[cur]) return false; // Cycle.
  if (!fwd[cur]) {                        // Try forwards.
    fwd[cur] = true;
    int up = cur + squares[cur];
    if (up < squares.size()) {
      cout << "Forwards" << endl;
      bool found = helper(up, squares, fwd, bck);
      if (found) return true;
    }
  }
  if (!bck[cur]) {                        // Try backwards.
    bck[cur] = true;
    int dn = cur - squares[cur];
    if (dn >= 0) {
      cout << "Backwards" << endl;
      bool found = helper(dn, squares, fwd, bck);
      if (found) return true;
    }
  }
  return false;
}

bool solvable(const vector<int> &squares)
{
  vector<bool> fwd(squares.size(), false);
  vector<bool> bck(squares.size(), false);
  return helper(0, squares, fwd, bck);
}

int sqs[] = { 2, 3, 1, 1, 4, 3, 4, 0, 1, 3, 1 };

int main(void)
{
  vector<int> sq(sqs, sqs + sizeof(sqs) / sizeof(int));
  cout << solvable(sq) << endl;
}

Collectives™ on Stack Overflow

Recursion problem help C++

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related