Java数组递归问题：寻找从array[0]到array[length-1]的路径

我来帮你排查这个递归方法里的问题，然后给出能正常工作的修正方案～

首先明确你的需求：从数组的索引0出发，每次可以选择将当前索引加上或减去当前元素的值，移动到新的位置，判断是否存在一条路径能到达数组的最后一个索引（即a.length - 1）。你的示例数组{2,4,1,6,4,2,4,3,5}确实存在这样的路径：0 → 0+2=2 → 2-1=1 →1+4=5 →5+2=7 →7-3=4 →4+4=8，最终到达索引8（数组最后一位）。

原代码的核心问题 #

1. 语法错误：公共方法isWay(int[] a)的返回语句里，参数不能写int[] a，应该直接传变量名a，而且初始调用的参数逻辑完全不对。
2. 递归逻辑混乱：
   • 终止条件错误：原代码里if(way==0) return true完全不符合需求，我们需要的是当当前索引等于最后一个索引时返回true。
   • 参数传递错误：way参数的定位模糊，递归调用时对way的加减操作完全偏离了“跟踪当前索引位置”的核心需求。
3. 栈溢出根源：没有记录已经访问过的索引，导致递归进入循环（比如索引A→B→A→B...），无限递归最终触发栈溢出。

修正后的代码实现 #

我们需要添加一个已访问标记来避免循环递归，同时梳理清楚递归的逻辑：

public static boolean isWay(int[] a) {
    // 处理边界情况：空数组直接返回false，单个元素默认已在终点
    if (a == null || a.length == 0) {
        return false;
    }
    if (a.length == 1) {
        return true;
    }
    // 用boolean数组记录已访问的索引，防止循环递归
    boolean[] visited = new boolean[a.length];
    // 从索引0开始递归
    return isWay(a, 0, visited);
}

private static boolean isWay(int[] a, int currentIndex, boolean[] visited) {
    // 终止条件1：当前索引越界，无法到达终点
    if (currentIndex < 0 || currentIndex >= a.length) {
        return false;
    }
    // 终止条件2：已经访问过该索引，避免循环递归
    if (visited[currentIndex]) {
        return false;
    }
    // 终止条件3：到达最后一个索引，找到有效路径
    if (currentIndex == a.length - 1) {
        return true;
    }

    // 标记当前索引为已访问，防止后续重复进入
    visited[currentIndex] = true;

    // 递归尝试两种移动方向：加当前元素值 / 减当前元素值
    boolean forwardPath = isWay(a, currentIndex + a[currentIndex], visited);
    boolean backwardPath = isWay(a, currentIndex - a[currentIndex], visited);

    // 只要任意一条路径可行，就返回true
    return forwardPath || backwardPath;
}

关键逻辑说明 #

• 已访问标记：boolean[] visited用来记录已经处理过的索引，避免同一个索引被反复访问导致无限递归，彻底解决栈溢出问题。
• 清晰的终止条件：
  • 索引越界→直接返回false；
  • 索引已访问→返回false（避免循环）；
  • 到达最后一个索引→返回true（找到有效路径）。
• 递归分支：每次尝试两种移动方向，只要其中一条路径能到达终点，就整体返回true。

用你的示例数组测试这个方法，会正确返回true，同时也不会出现栈溢出的问题。

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