递归查找数组中数字最后出现索引及Java代码正确性验证

给定长度为N的数组和整数x，你需要查找并返回整数x在数组中最后一次出现的索引，若数组中不存在x则返回-1。
最后一次出现索引的定义为：若x在数组中多次出现，返回x在数组中最后一次出现位置的下标。
要求：必须从下标0开始遍历数组，不可从N-1倒序遍历，且需采用递归方式实现，数组索引从0开始计数。

输入输出规范 #

输入格式 #

第1行：整数N，即数组的大小
第2行：N个整数作为数组的元素，空格分隔
第3行：整数x

输出格式 #

最后一次出现的索引值或-1

约束条件 #

• 1 ≤ N ≤ 10^3

示例 #

输入

4
9 8 10 8
8

输出

3

public class Solution {
     static int idx = -1;
     static int helper(int input[], int x ,int i){
        if(i == input.length){
        return idx;
        }
        else if(input[i] == x){
          if(i > idx ){
            idx = i;
         }
       }
    return helper(input,x,i +1);
}

public static int lastIndex(int input[], int x) {
    /* Your class should be named Solution
     * Don't write main().
     * Don't read input, it is passed as function argument.
     * Return output and don't print it.
     * Taking input and printing output is handled automatically.
    */
    return helper(input,x,0);
}
}

符合要求的部分 #

你的代码确实满足题目核心要求：

1. 递归实现逻辑正确，从下标0开始正序遍历数组，没有倒序遍历的操作
2. 单次调用lastIndex方法时，可以得到正确的返回结果，比如示例输入调用后会正确返回3

存在的问题 #

你使用了静态全局变量idx存储匹配到的最大索引，这会导致多次调用lastIndex方法时结果错误：静态变量的值会保留上一次调用的结果，不会自动重置为-1，比如第一次调用查找值8得到结果3，第二次调用查找一个数组中不存在的值时，本应返回-1，但会因为静态变量保留的旧值返回错误的3。

优化方案 #

可以把当前匹配到的最大索引作为递归方法的入参传递，完全规避静态变量的问题，优化后代码如下：

public class Solution {
    static int helper(int input[], int x ,int i, int currentMaxIdx){
        if(i == input.length){
            return currentMaxIdx;
        }
        if(input[i] == x){
            currentMaxIdx = i;
        }
        return helper(input,x,i +1, currentMaxIdx);
    }

    public static int lastIndex(int input[], int x) {
        return helper(input,x,0, -1);
    }
}

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