Java递归处理重复元素栈溢出分析

本篇文章主要是结合我之前面试的各种经历和实战开发中遇到的问题解决经验整理的，希望这篇《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。

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

优化方案：迭代式去重

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

核心思想

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

示例代码

以下是一个改进的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 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 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 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集合）通常是更健壮、高效且易于理解的解决方案。通过选择合适的算法和数据结构，可以有效避免常见的运行时错误，并提高代码的性能和可维护性。

本篇关于《Java递归处理重复元素栈溢出分析》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！