Java递归函数StackOverflowError：去重算法的优化与实践-java教程-PHP中文网

Java递归函数StackOverflowError：去重算法的优化与实践

本文深入探讨了Java中因递归函数设计不当导致的StackOverflowError，特别是在数组去重场景下。通过分析原始代码中deleteRepeated函数的逻辑缺陷，揭示了无限递归的根源。文章提供了一种高效、迭代式的去重算法作为解决方案，并详细解析其实现原理和优势，旨在帮助开发者避免此类常见错误，提升代码健壮性。

理解StackOverflowError及其在递归中的成因

java.lang.stackoverflowerror 是java虚拟机（jvm）抛出的一个运行时错误，表示线程的栈空间已耗尽。在递归函数中，如果递归调用没有正确的终止条件，或者每次调用未能有效缩小问题规模以接近终止条件，那么函数会无休止地调用自身，导致调用栈不断增长，最终超出jvm为该线程分配的栈内存限制，从而引发 stackoverflowerror。

在提供的代码中，虽然 factorial 函数是一个经典的递归示例，其本身设计是正确的（有明确的基线条件 n == 0），但在特定的上下文或参数过大时，仍可能导致栈溢出。然而，问题的核心并非 factorial 本身，而是 deleteRepeated 函数的递归调用机制。

原始代码分析：问题症结所在

让我们逐一分析原始代码中的关键函数，以定位 StackOverflowError 的根本原因。

factorial 函数:
```
public static long factorial(int n) {
    if (n == 0)
        return 1;
    return (n * factorial(n - 1));
}
```
登录后复制
这是一个标准的递归阶乘实现，逻辑清晰且终止条件明确。当 n 不大时，它能正常工作。

立即学习“Java免费学习笔记（深入）”；

repeated 函数:

public static int repeated(int arr[]) {
    int n = arr.length;
    // int mix = (int) (factorial(n) / (2 * factorial(n - 2))); // 这一行计算的是组合数 C(n, 2)
    int i = 0;
    int k = 0;
    int rep = 0;
    int a = -100; // 用于避免重复计数同一个元素与不同位置的重复
    while (i < mix) { // mix的值可能导致循环次数与实际不符
        for (int j = k + 1; j < n; j++) {
            if (arr[k] == arr[j] && a != j) { // 逻辑复杂，可能无法准确计数
                a = j;
                rep += 1;
            }
            i++;
        }
        k++;
    }
    return rep;
}

登录后复制

这个函数的目标是计算数组中的重复元素数量。然而，其内部逻辑复杂且效率不高。mix 变量被计算为 C(n, 2)（从 n 个元素中选择 2 个的组合数），这与实际遍历数组并计数重复元素的逻辑不完全匹配。更重要的是，其内部的循环和条件判断难以准确地实现“计数重复元素”这一目标。

deleteRepeated 函数：无限递归的根源

人声去除
用强大的AI算法将声音从音乐中分离出来

23

查看详情
```
public static int[] deleteRepeated(int arr[], int newArr[]) {
    int n = arr.length;
    int rep = repeated(arr); // 调用repeated函数，可能返回不准确的重复数
    int i = 0;
    int k = 0;
    int a = -100;
    while (i < newArr.length) { // 循环条件依赖newArr的长度，但newArr可能并未被正确填充
        for (int j = k + 1; j < n; j++) {
            if (arr[k] == arr[j] && a != arr[k]) { // 这里的逻辑与去重不符，更像是在查找重复
                a = arr[j];
                newArr[k] = arr[k]; // 错误：这里应该将不重复的元素添加到newArr，而不是arr[k]
            }
            i++;
        }
        k++;
    }
    rep = repeated(newArr); // 再次调用repeated，检查newArr中是否有重复
    if (rep > 0) { // 关键：如果newArr中仍有重复，则进行递归调用
        int[] newArr2 = new int[newArr.length - rep];
        deleteRepeated(newArr, newArr2); // 递归调用，但newArr的状态可能未改变
    }
    return newArr; // 返回newArr
}
```
登录后复制
deleteRepeated 函数是导致 StackOverflowError 的直接原因。其核心问题在于：
- 逻辑缺陷： deleteRepeated 的内部循环逻辑并没有真正地将 arr 中的不重复元素筛选出来并放入 newArr。相反，它似乎尝试复制了 repeated 函数的部分逻辑，但未能正确实现去重。newArr 数组在循环结束后可能并未被正确填充，甚至可能大部分是默认值（0）。
- 无限递归： 在函数末尾，rep = repeated(newArr); 再次计算 newArr 中的重复元素。由于 newArr 未能被有效去重（甚至可能未被正确填充），repeated(newArr) 几乎总是会返回 rep > 0。这意味着 if (rep > 0) 的条件将一直为真，导致 deleteRepeated(newArr, newArr2); 被无限递归调用。每次递归调用都会在栈上创建一个新的栈帧，最终耗尽栈空间，引发 StackOverflowError。
- 状态未改变： 递归的终止条件依赖于 newArr 中不再有重复元素 (rep == 0)。然而，由于函数内部逻辑未能有效改变 newArr 的状态以使其去重，这个终止条件永远无法满足，从而陷入死循环。

优化方案：迭代式去重算法

为了解决上述问题，我们应该采用一种更直接、更高效且避免递归的迭代式去重算法。对于数组去重，常见的策略是遍历原数组，并将不重复的元素逐一添加到新数组中。这种方法不仅逻辑清晰，而且可以有效避免 StackOverflowError。

示例代码：高效去重实现

以下是优化后的 deleteRepeated 函数，采用迭代方式实现数组去重：

import java.util.Scanner;
import java.util.Arrays; // 导入Arrays工具类，用于后续可能的数组操作

public class ex9_Optimized {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入数组长度 n: ");
        int n = sc.nextInt();
        int[] arr = new int[n];
        System.out.println("请输入 " + n + " 个整数:");
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 创建一个足够大的新数组，最坏情况是所有元素都唯一
        int[] tempArr = new int[n];
        // 调用优化后的去重函数，返回实际去重后的元素数量
        int actualSize = deleteRepeated(arr, tempArr);

        // 根据实际大小创建一个最终数组
        int[] finalArr = Arrays.copyOf(tempArr, actualSize);

        System.out.println("去重后的数组为:");
        for (int a : finalArr) {
            System.out.println(a);
        }
        sc.close();
    }

    /**
     * 高效地从源数组中移除重复元素，并将不重复的元素放入目标数组。
     * 此方法采用迭代方式，避免了StackOverflowError。
     *
     * @param arr 源数组，包含可能重复的元素。
     * @param newArr 目标数组，用于存储去重后的元素。此数组应有足够的容量。
     * @return 目标数组中实际存储的不重复元素的数量。
     */
    public static int deleteRepeated(int arr[], int newArr[]) {
        int n = 0; // n 用于记录 newArr 中实际元素的数量，也是下一个不重复元素插入的位置
        for (int i = 0; i < arr.length; i++) {
            boolean unique = true;
            // 检查 arr[i] 是否已存在于 newArr 的前 n 个元素中
            for (int j = 0; j < n; j++) {
                if (newArr[j] == arr[i]) {
                    unique = false;
                    break; // 发现重复，跳出内层循环，无需继续检查
                }
            }
            if (unique) {
                // 如果是独一无二的，则添加到 newArr 中
                // 同时检查 newArr 是否还有空间，防止数组越界
                if (n < newArr.length) {
                    newArr[n++] = arr[i];
                } else {
                    // newArr 空间不足，通常意味着初始分配的newArr长度不够
                    // 或者原数组的唯一元素数量超出了newArr的容量
                    System.err.println("警告: 目标数组空间不足，部分元素可能未被复制。");
                    break;
                }
            }
        }
        return n; // 返回新数组中实际的元素数量
    }

    // 原始的 factorial 和 repeated 函数与去重逻辑关系不大，在此处不再提供
    // 如果需要，可以根据实际需求重新设计或优化
}

登录后复制

代码解析与应用

deleteRepeated 函数详解：
- int n = 0;: 引入一个变量 n，它有两个作用：
  - 记录 newArr 中当前已经存储了多少个不重复的元素。
  - 指示下一个不重复元素应该插入到 newArr 的哪个索引位置。
- 外层循环 for (int i = 0; i < arr.length; i++): 遍历原始数组 arr 中的每一个元素。
- 内层循环 for (int j = 0; j < n; j++): 对于 arr[i]（当前正在检查的元素），它会与 newArr 中已经收集到的 n 个不重复元素进行比较。
- boolean unique = true;: 这是一个标志，默认认为当前元素是唯一的。如果内层循环发现 arr[i] 与 newArr 中的任何一个元素相同，unique 就会被设置为 false，并立即跳出内层循环，因为已经确定它不是唯一的。
- if (unique): 如果 unique 仍然为 true（即 arr[i] 在 newArr 中没有找到重复项），那么 arr[i] 是一个新发现的唯一元素。
- newArr[n++] = arr[i];: 将这个唯一元素添加到 newArr 的 n 索引位置，然后 n 自增，为下一个唯一元素准备好位置。
- 容量检查 if (n < newArr.length): 确保在向 newArr 添加元素时不会发生数组越界。虽然通常 newArr 会被初始化为与 arr 相同的长度，但这是一个好的防御性编程实践。
- 返回值 return n;: 函数返回 n，表示 newArr 中实际存储了多少个有效的不重复元素。
main 方法中的应用：
- main 方法首先创建了一个与原始数组 arr 相同大小的 tempArr。这是因为在最坏情况下（所有元素都唯一），去重后的数组可能与原数组一样长。
- 调用 deleteRepeated(arr, tempArr) 后，它会返回实际的去重元素数量 actualSize。
- Arrays.copyOf(tempArr, actualSize) 用于根据 actualSize 创建一个精确大小的 finalArr，避免了 tempArr 中可能存在的尾部默认值（0）。

编程实践建议

递归与迭代的选择： 递归虽然在某些场景下能使代码更简洁，但其固有的栈溢出风险不容忽视。对于涉及大量数据处理或深度不确定的操作，迭代通常是更安全、性能更好的选择。在去重、遍历等场景中，迭代是首选。
明确函数职责： 每个函数都应该有清晰、单一的目的。例如，一个函数负责去重，就只做去重的工作，不应该混入复杂的计数逻辑或不相关的操作。
测试与调试： 编写单元测试来验证函数的正确性，并利用调试工具（如IDE的调试器）逐步执行代码，观察变量状态，是定位和解决问题的有效方法。

算法复杂度： 在设计算法时，应考虑其时间复杂度和空间复杂度。上述迭代去重算法的时间复杂度为 O(N*M)，其中 N 是原数组长度，M 是去重后数组长度（最坏情况 M=N）。对于大型数据集，可以考虑使用 HashSet 等数据结构将时间复杂度优化到 O(N)。

// 使用HashSet进行去重，时间复杂度为O(N)
public static int[] deleteRepeatedWithSet(int arr[]) {
    Set<Integer> uniqueElements = new LinkedHashSet<>(); // LinkedHashSet保持插入顺序
    for (int element : arr) {
        uniqueElements.add(element);
    }
    // 将Set转换回数组
    int[] result = new int[uniqueElements.size()];
    int i = 0;
    for (int element : uniqueElements) {
        result[i++] = element;
    }
    return result;
}

登录后复制