Java递归函数处理重复元素导致的栈溢出错误分析与优化

本文深入探讨了在Java中，递归函数因处理数组重复元素逻辑缺陷而引发StackoverflowError的案例。通过分析原有代码中deleteRepeated函数的错误实现，揭示了无限递归的根本原因。文章提出了一种高效且健壮的迭代方法来移除数组中的重复元素，并提供了示例代码，旨在帮助开发者理解递归陷阱并掌握正确的数组去重策略。

递归与栈溢出：问题剖析

在Java等编程语言中，当一个方法被调用时，jvm会在栈内存中为该方法创建一个栈帧，用于存储局部变量、参数和返回地址。递归函数在执行时会不断地调用自身，每次调用都会产生一个新的栈帧。如果递归没有明确的终止条件，或者终止条件无法被满足，栈帧会持续累积，最终耗尽栈内存，导致java.lang.StackOverflowError。

原始代码中，factorial函数是一个典型的递归阶乘计算，其本身在正常输入下是正确的。然而，问题主要出现在deleteRepeated函数及其与repeated函数的交互中。

原始代码中的缺陷分析

原始的deleteRepeated函数旨在从数组中移除重复元素，但其实现存在以下几个关键问题：

1. 错误的去重逻辑：deleteRepeated函数内部的循环逻辑 (while (i < newArr.Length) 和 for (int j = k + 1; j < n; j++)) 实际上是对repeated函数逻辑的拙劣模仿，并没有正确地识别并构建一个只包含唯一元素的新数组。newArr[k] = arr[k]; 这一行代码仅在特定条件下将元素从arr复制到newArr，但并未有效过滤重复项。
2. 无限递归的根源： 在deleteRepeated函数的末尾，存在一个递归调用：

   rep = repeated(newArr); if (rep > 0) {     int[] newArr2 = new int[newArr.length - rep];     deleteRepeated(newArr, newArr2); }

   这里，repeated(newArr)的目的是检查newArr中是否仍存在重复元素。然而，由于deleteRepeated未能正确地去重，newArr很可能仍然包含重复项，或者其长度计算 (newArr.length – rep) 存在问题。这导致rep > 0的条件持续为真，从而触发无限递归调用。每次递归调用都会创建一个新的栈帧，最终耗尽栈空间，引发StackOverflowError。

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

3. repeated函数的复杂性：repeated函数试图通过计算组合数 (n * (n-1)) / 2 来确定迭代次数，这种方法对于简单的重复元素计数过于复杂且容易出错。它试图寻找所有可能的对，然后检查它们是否相等，这并非最直观或高效的去重或重复计数方法。

优化方案：迭代式去重

为了解决StackOverflowError并实现正确的数组去重功能，我们应该放弃原有的复杂且错误的递归去重逻辑，转而采用一种更清晰、更高效的迭代方法。

核心思想

迭代式去重通常涉及遍历原始数组，并维护一个结果数组（或列表），每次将原始数组中的元素与结果数组中已有的元素进行比较。如果该元素在结果数组中不存在，则将其添加到结果数组中。

Poe

Quora旗下的对话机器人聚合工具

289

查看详情

示例代码

以下是一个改进的deleteRepeated方法，它采用迭代方式，将原始数组中的唯一元素复制到一个新的数组中。

import java.util.Scanner;  public class ArrayDuplicateRemoval {      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();         }         sc.close();          // 创建一个足够大的新数组来存储去重后的元素，最大长度与原数组相同         int[] tempArr = new int[arr.length];         // 调用去重方法，返回实际的唯一元素数量         int uniqueCount = deleteRepeated(arr, tempArr);          // 根据实际的唯一元素数量创建最终数组         int[] finalArr = new int[uniqueCount];         System.arraycopy(tempArr, 0, finalArr, 0, uniqueCount);          System.out.println("去重后的数组元素:");         for (int a : finalArr) {             System.out.println(a);         }     }      /**      * 从给定数组中移除重复元素，并将唯一元素存储到新数组中。      *      * @param arr 原始数组。      * @param newArr 用于存储唯一元素的新数组。此数组应预先分配足够大的空间。      * @return 实际存储在 newArr 中的唯一元素数量。      */     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 中已添加的元素里             for (int j = 0; j < n; j++) {                 if (newArr[j] == arr[i]) {                     unique = false; // 发现重复，标记为不唯一                     break;          // 找到重复即可退出内层循环                 }             }             // 如果元素是唯一的，则将其添加到 newArr             if (unique) {                 newArr[n++] = arr[i];             }             // 如果 newArr 已满（达到其最大容量），则停止处理             if (n >= newArr.length) {                 break;             }         }         return n; // 返回实际存储的唯一元素数量     }      // 原始代码中的 factorial 函数，与去重逻辑无关，但可保留     public static long factorial(int n) {         if (n == 0)             return 1;         return (long)n * factorial(n - 1);     } }

代码详解

• deleteRepeated(int[] arr, int[] newArr) 方法：
  • n 变量：充当newArr的索引，同时记录了newArr中当前唯一元素的数量。
  • 外层循环 (for (int i = 0; i < arr.length; i++))：遍历原始数组arr中的每一个元素。
  • unique 标志：初始化为true，用于判断当前元素arr[i]是否为唯一。
  • 内层循环 (for (int j = 0; j < n; j++))：遍历newArr中已经添加的唯一元素。如果arr[i]与newArr中的任何元素相同，则将其标记为不唯一 (unique = false) 并跳出内层循环。
  • 条件添加：如果unique仍为true，说明arr[i]是新的唯一元素，将其添加到newArr中，并递增n。
  • 容量检查：if (n >= newArr.length) break; 这一行确保不会向newArr写入超出其容量的元素。
  • 返回值：方法返回n，即newArr中实际存储的唯一元素的数量。

进一步优化与注意事项

1. 使用 java.util.Set： 在Java中，处理集合去重最简洁和高效的方式是使用 Set 接口的实现，例如 HashSet。Set 集合天生不允许包含重复元素。

   import java.util.Arrays; import java.util.LinkedHashSet; import java.util.Set;  public class SetDuplicateRemoval {     public static int[] removeDuplicatesUsingSet(int[] arr) {         Set<Integer> uniqueElements = new LinkedHashSet<>(); // LinkedHashSet保持插入顺序         for (int element : arr) {             uniqueElements.add(element);         }         // 将Set转换回int数组         return uniqueElements.stream().mapToInt(Integer::intValue).toArray();     }      public static void main(String[] args) {         int[] originalArr = {1, 2, 3, 2, 4, 1, 5};         int[] resultArr = removeDuplicatesUsingSet(originalArr);         System.out.println("使用Set去重后的数组: " + Arrays.toString(resultArr));     } }

   这种方法不仅代码量少，而且HashSet的查找和插入操作平均时间复杂度为O(1)，效率非常高。

2. 动态数组 ArrayList： 如果不能确定去重后数组的精确大小，使用ArrayList作为中间存储结构会更灵活，避免手动管理数组大小。

   import java.util.ArrayList; import java.util.List;  public class ArrayListDuplicateRemoval {     public static int[] removeDuplicatesUsingList(int[] arr) {         List<Integer> uniqueList = new ArrayList<>();         for (int element : arr) {             if (!uniqueList.contains(element)) { // contains操作可能较慢                 uniqueList.add(element);             }         }         // 将List转换回int数组         return uniqueList.stream().mapToInt(Integer::intValue).toArray();     }      // 结合Set和List的优势     public static int[] removeDuplicatesUsingSetAndList(int[] arr) {         Set<Integer> uniqueSet = new LinkedHashSet<>();         for (int element : arr) {             uniqueSet.add(element);         }         return uniqueSet.stream().mapToInt(Integer::intValue).toArray();     } }

   请注意，ArrayList.contains() 方法的时间复杂度为O(n)，因此如果元素数量很多，效率可能不如HashSet。

3. 递归使用的场景： 递归并非一无是处，它在处理树形结构、图遍历、分治算法（如快速排序、归并排序）等问题时，能提供简洁优雅的解决方案。然而，对于像数组去重这种可以清晰地通过迭代解决的问题，通常应优先考虑迭代，以避免栈溢出的风险和更高的内存开销。

总结

java.lang.StackOverflowError通常是由于无限或深度过大的递归调用导致的。在编写递归函数时，务必确保有明确且能够被满足的终止条件。对于数组去重这类问题，迭代方法（尤其是结合Set集合）通常是更健壮、高效且易于理解的解决方案。通过选择合适的算法和数据结构，可以有效避免常见的运行时错误，并提高代码的性能和可维护性。