C#递归步长法

Question

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

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

步骤0：索引=0，值=3

步骤1：索引=3，值=1

步骤5：索引=6，值=2

步骤6：索引=8，值=3

步骤7：索引=5，值=4

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

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
}

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

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