递归线性搜索代码中temp变量逻辑与返回顺序的疑问

老师的递归实现代码 #

static ArrayList<Integer> LinearSearch(int[] arr,int index,int target) {
    ArrayList<Integer> iList = new ArrayList<>();
    if(index == arr.length){
        return iList;
    }
    if(arr[index] == target){
        iList.add(index);
    }
    ArrayList<Integer> temp = LinearSearch(arr,index+1,target);
    iList.addAll(temp);
    return iList;
}

核心疑问与执行流程拆解 #

针对数组[1,2,3,4,3]（目标值为3），实际返回[2,4]而非预期的[4,2]，核心原因在于递归的先递后归执行顺序，以及temp的生成逻辑：

1. 递推阶段（逐层深入到终止条件）

递归从初始调用LinearSearch(arr, 0, 3)开始，逐层调用index+1，直到触发终止条件index == arr.length：

• index=0：元素1≠3，创建空列表，调用index=1
• index=1：元素2≠3，创建空列表，调用index=2
• index=2：元素3=3，创建列表并添加索引2，调用index=3
• index=3：元素4≠3，创建空列表，调用index=4
• index=4：元素3=3，创建列表并添加索引4，调用index=5
• index=5：触发终止条件，返回空列表

2. 回溯阶段（逐层返回合并结果）

从终止条件开始，结果逐层向上返回并合并：

• index=5返回空列表给index=4的temp：index=4的列表原本是[4]，合并后仍为[4]，返回给index=3的temp
• index=3的空列表合并temp（[4]）后变成[4]，返回给index=2的temp
• index=2的列表原本是[2]，合并temp（[4]）后变成[2,4]，返回给index=1的temp
• index=1的空列表合并temp（[2,4]）后变成[2,4]，返回给index=0的temp
• index=0的空列表合并temp后最终返回[2,4]

简单来说，老师的代码是先记录当前索引的匹配结果，再追加后续递归找到的所有结果，所以索引按从左到右的顺序存入列表。

自己的回溯实现代码 #

static ArrayList<Integer> LinearSearch(int[] arr,int index,int target) {
    ArrayList<Integer> iList = new ArrayList<>();
    if(index == arr.length){
        return iList;
    }
    iList = LinearSearch(arr,index+1,target);
    if(arr[index] == target){
        iList.addFirst(index);
    }
    return iList;
}

逻辑对比 #

你的代码是先获取后续递归的结果，再将当前匹配的索引插入到列表头部，本质是回溯时从后往前收集索引。如果要得到[4,2]的结果，只需要把addFirst(index)换成add(index)，这样当前匹配的索引会追加到后续结果的末尾，最终得到从右到左的索引顺序。

内容的提问来源于stack exchange，提问作者Eren Yılmaz