递归与栈溢出：问题剖析
在Java等编程语言中，当一个方法被调用时，JVM会在栈内存中为该方法创建一个栈帧，用于存储局部变量、参数和返回地址。递归函数在执行时会不断地调用自身，每次调用都会产生一个新的栈帧。如果递归没有明确的终止条件，或者终止条件无法被满足，栈帧会持续累积，最终耗尽栈内存，导致java.lang.StackOverflowError。
原始代码中，factorial函数是一个典型的递归阶乘计算，其本身在正常输入下是正确的。然而，问题主要出现在deleteRepeated函数及其与repeated函数的交互中。
原始代码中的缺陷分析
原始的deleteRepeated函数旨在从数组中移除重复元素，但其实现存在以下几个关键问题：
- 错误的去重逻辑：deleteRepeated函数内部的循环逻辑 (while (i < newArr.length) 和 for (int j = k + 1; j < n; j++)) 实际上是对repeated函数逻辑的拙劣模仿，并没有正确地识别并构建一个只包含唯一元素的新数组。newArr[k] = arr[k]; 这一行代码仅在特定条件下将元素从arr复制到newArr，但并未有效过滤重复项。
-
无限递归的根源：
在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免费学习笔记（深入）”；
- 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中实际存储的唯一元素的数量。
进一步优化与注意事项
-
使用 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)，效率非常高。
-
动态数组 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。
递归使用的场景： 递归并非一无是处，它在处理树形结构、图遍历、分治算法（如快速排序、归并排序）等问题时，能提供简洁优雅的解决方案。然而，对于像数组去重这种可以清晰地通过迭代解决的问题，通常应优先考虑迭代，以避免栈溢出的风险和更高的内存开销。
总结
java.lang.StackOverflowError通常是由于无限或深度过大的递归调用导致的。在编写递归函数时，务必确保有明确且能够被满足的终止条件。对于数组去重这类问题，迭代方法（尤其是结合Set集合）通常是更健壮、高效且易于理解的解决方案。通过选择合适的算法和数据结构，可以有效避免常见的运行时错误，并提高代码的性能和可维护性。
