c#递推步进法

Question

我试图创建一个递归方法来检查整数数组中的最后一个数字(总是0)是否可以通过增加(或减少)数组的索引来达到，同时保持在数组的范围内。

示例：

假设我们有以下数组，并且开始索引== 0：

int[] arr = {3, 6, 4, 1, 3, 4, 2, 5, 3, 0};

步骤0:索引= 0，值=3 步骤1:索引= 3，值=1 步骤2:索引= 4，值=3 步骤3:索引= 7，值=5 步骤4:索引= 2，值=4 步骤5:索引= 6，值=2 步骤6:索引= 8，值=3 步骤7:索引= 5，值=4 步骤8: index = 9，value =0- end

我现在的代码是：

        static bool Solveable(int index, int[] arr)
        {
            if (arr[index] == 0)
                return true;
            if (index + arr[index] < arr.Length)
                return Solveable(index + arr[index], arr);
            if (index - arr[index] >= 0)
                return Solveable(index - arr[index], arr);

            return false;
        }

与此相关的是，它只适用于可解决的情况，所有其他情况都将导致堆栈溢出异常。

如果不使用全局变量来存储先前的结果，我如何才能解决这个问题？

编辑：

我只能使用参数：(int索引，int[] arr)

Answer 1

对于无法解决的情况，堆栈溢出是正确的:递归代码的行为就像狗追逐自己的尾巴，直到达到堆栈极限为止。

幸运的是，如果要到达数组的末尾，则可以通过观察最多需要N步骤来打破这种无限递归。因此，您可以添加第三个参数来指示您已经执行了多少步骤。如果在步骤数通过N之前达到零，则有一个路径；否则，您就没有路径。

static bool Solveable(int index, int[] arr, int stepsSoFar) {
    if (arr[index] == 0)
        return true;
    if (stepsSoFar > arr.Length)
        return false;
    ...
    // The rest of your code; pass stepsSoFar+1 down to the next level
}

我只能使用代码片段中包含的两个参数。

您可以通过在arr中放置-1来标记在它们中访问过的索引。为了保留数组的原始状态，将旧值存储在局部变量中，并在返回之前将其设置为arr：

static bool Solveable(int index, int[] arr) {
    if (arr[index] == 0)
        return true;
    if (arr[index] == -1)
        return false;
    int oldArrAtIndex = arr[index];
    arr[index] = -1;
    try {
        ...
        // The rest of your code
    } finally {
        arr[index] = oldArrAtIndex;
    }
}

Answer 2

传递第三个参数，跟踪你已经走过的指数。如果您已经尝试过当前索引，则停止处理。

此外，你也可能想改变一下在下列两个方向旅行的原因：

var solvable = false;
//...

if (index + arr[index] < arr.Length)
   solvable = Solveable(index + arr[index], arr);
if (!solvable && index - arr[index] >= 0)
   solvable = Solveable(index - arr[index], arr);

return solvable;

Answer 3

无论学校作业与否，递归课都没有增加所有的复杂性。

private static void Main()
{
    int[] array = {3, 6, 4, 1, 3, 4, 2, 5, 3, 0};
    Console.WriteLine(IsSolveable(array));
    Console.ReadKey();
}

private static bool IsSolveable(int[] array)
{
    if (array.Length <= 1)
        return false;

    int index = array[0];
    if (index < array.Length && array[index] == 0)
        return true;

    // this is where the recursion magic happens
    return IsSolveable(array.Skip(1).ToArray());
}