数组移动可达性判断递归代码异常：为何无法输出正确结果？

先明确下问题场景：给定整数数组，从索引0出发，最多移动m次，每次可以选择向前或向后走当前索引对应的arr[i]步；当m用完时，若处于数组最后一个位置则返回True，否则返回False。比如示例[2,3,1]、m=1时，从索引0向前走2步到索引2（数组末尾），应该返回True。

现在看你写的这段代码：

bool fun(int arr[],int m,int i,int num_ele) {
    if(m==0) {
        if(i==(num_ele) return true;
        else return false;
    }
    fun(arr,m-1,i+arr[i],num_ele);
    fun(arr,m-1,i-arr[i],num_ele);
}

这里有几个关键问题导致无法得到正确结果：

1. 数组末尾索引判断错误 #

数组的索引是从0开始的，长度为num_ele的数组，最后一个元素的索引是num_ele - 1，而不是num_ele。比如示例数组长度是3，最后一个索引是2，但你的代码里判断i == num_ele（也就是3），这会直接把正确到达末尾的情况误判为False，这是核心错误之一。

2. 递归调用没有传递返回值 #

你的递归函数在调用子问题（向前/向后移动）时，只是执行了函数，但没有把这些子调用的结果返回给上层调用。递归的核心是将子问题的结果向上传递——只要其中一条路径能成功到达末尾（返回True），当前函数就应该返回True；只有当两条路径都失败时，才返回False。现在的写法会导致函数最后没有return语句，行为是未定义的（通常会返回随机的垃圾值）。

3. 缺少索引越界检查（可选但关键） #

在递归过程中，i可能会变成负数，或者超过/等于数组长度（比如向前走太多步），这些情况下后续的移动已经没有意义，而且访问arr[i]会导致数组越界的运行时错误。提前检查i的合法性，可以避免错误并减少不必要的递归。

修正后的代码示例 #

bool fun(int arr[], int m, int i, int num_ele) {
    // 先检查当前索引是否合法，不合法直接返回false
    if (i < 0 || i >= num_ele) {
        return false;
    }
    // 移动次数耗尽，判断是否在数组最后一个位置
    if (m == 0) {
        return i == num_ele - 1;
    }
    // 尝试向前和向后移动，只要任意一条路径成功就返回true
    return fun(arr, m-1, i + arr[i], num_ele) || fun(arr, m-1, i - arr[i], num_ele);
}

这个修正版本解决了上述所有问题：

• 正确判断数组末尾索引
• 通过||运算符合并两个递归调用的结果，只要有一个路径成功就返回True
• 增加了索引越界检查，避免非法访问数组

内容的提问来源于stack exchange，提问作者k_learner