c++ - 递归问题求助C++

Question

我正在尝试编写代码来检查您是否可以按照特定规则到达数组的末尾。您从整数数组的第一个元素开始，存储在该位置的数字就是您可以向前或向后跳跃的次数。目标是到达由 0 值表示的 Vector 的末尾。

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

代码似乎不起作用，因为我认为我缺少一个基本案例，但我似乎无法弄清楚我还需要什么其他基本案例。

谢谢!

Answer 1

有几个问题。首先是你的代码只会选择前进或后退，你永远不会选择两者。原因是你总是说return Solvable。你需要的是这样的东西

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

这里没有检查基本情况，也没有检查越界，但希望您明白了。

第二个问题是您的 squares[forward] != squares[start] 和 squares[prev] != squares[start] 测试。在我看来，它们并不是您所描述的问题的一部分。我会放弃它们。

说明递归的好问题。