C# 递归步骤方法

Question

我正在尝试使用递归方法来检查整数数组(所有 > 0 整数)中的最后一个数字(始终为 0)是否可以通过增加(或减少)数组的索引来达到当前索引的数组元素，同时保持在数组的边界内。

例子:

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

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

step 0 : index = 0, value = 3

step 1 : index = 3, value = 1

step 2 : index = 4, value = 3

step 3 : index = 7, value = 5

step 4 : index = 2, value = 4

step 5 : index = 6, value = 2

step 6 : index = 8, value = 3

step 7 : index = 5, value = 4

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

问题是它只适用于可解决的情况，所有其他情况都会导致 stackoverflow 异常。

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

编辑:

我只能使用参数:(int index, 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
}

I can only use the two parameters i included in my code snippet

您可以通过将-1 放入arr 本身来标记您访问过的索引。为了保留数组的原始状态，将旧值存储在局部变量中，并在返回前将其设置回 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;
    }
}