CODEWITHSUNDEEP
c++algorithmrecursionpuzzle
user871303
user871303

Reputation: 515

Recursion problem help C++

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!

Upvotes: 1

Views: 581

Answers (2)

Ian Ross
Ian Ross

Reputation: 987

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;
}

Upvotes: 0

john
john

Reputation: 87959

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.

Upvotes: 4

Related Questions