如何退出递归函数调用 查找1到n正整数数组中的缺失数字

你的代码核心问题 #

• 递归调用无返回值承接：每次调用checkMissingItem(array,j,mitem)时，没有将该调用的结果向上返回，导致深层递归的计算结果无法传递到最上层，最终只会返回最外层函数的mitem值，这就是你无法正确退出递归的核心原因
• 逻辑冗余混乱：循环+递归的组合逻辑设计不合理，查找1~n范围内的缺失数字完全不需要这么复杂的实现

修复后的递归版本 #

最小改动保留递归实现的可运行代码如下：

public class MissingNumber {
    public static void main(String[] args)
    {
        int[] array={3,7,1,2,8,4,5};
        // 从数字1开始逐个检查
        System.out.println(checkMissingItem(array, 1));
    }

    public static int checkMissingItem(int [] array, int checkNum)
    {
        // 边界校验：检查范围超过n（数组长度+1，因为缺1个元素）直接返回异常值
        if(checkNum > array.length + 1) {
            return -1;
        }
        // 遍历数组查找当前要校验的数字
        for (int num : array) {
            if (num == checkNum) {
                // 找到则校验下一个数字，必须return递归结果才能把值传回上层
                return checkMissingItem(array, checkNum + 1);
            }
        }
        // 遍历完未找到，当前checkNum就是缺失值，直接返回即可自动结束递归
        return checkNum;
    }
}

更推荐的非递归实现 #

递归实现当n过大时会出现栈溢出问题，更推荐以下两种时间复杂度O(n)、空间复杂度O(1)的解法：

1. 求和法（直观易理解） #

原理：1到n的和为固定值n*(n+1)/2，减去数组所有元素的和，差值就是缺失的数字

public static int findMissingBySum(int[] array) {
    int n = array.length + 1;
    int total = n * (n + 1) / 2;
    int arraySum = 0;
    for (int num : array) {
        arraySum += num;
    }
    return total - arraySum;
}

2. 异或法（避免大数求和溢出） #

原理：相同数字异或结果为0，0异或任意数字等于数字本身。将1~n所有数异或后再和数组所有元素异或，最终结果就是缺失的数字

public static int findMissingByXor(int[] array) {
    int n = array.length + 1;
    int xorRes = 0;
    for (int i = 1; i <= n; i++) {
        xorRes ^= i;
    }
    for (int num : array) {
        xorRes ^= num;
    }
    return xorRes;
}

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