如何修复递归去重字符串时的栈溢出错误

本文详解 Ja va 中因错误使用后置递增操作符（idx++）导致无限递归和栈溢出的问题，并提供正确、健壮的递归实现方案。

咱们直接进入正题。今天聊一个在递归代码中特别容易踩的坑——后置递增操作符（idx++）被误用在递归参数里，结果引发了栈溢出。别笑，这问题在初学递归时简直是个“经典副本”。先看一段典型的出问题代码：

DeDupe(s, idx++, s1); // ❌ 错误：idx++ 先传入原值，再自增 → 每次都传 0！

问题出在哪？idx++ 的语义是“先使用当前值，再自增”。也就是说，当你把这行代码写进递归调用时，传给下一层递归的参数仍然是 idx 的原始值（比如 0），然后当前栈帧的局部变量 idx 确实自增了——但这个变化对下一层递归毫无影响。于是每一层递归看到的 idx 都是 0，永远达不到 idx == s.length() 的终止条件，无限递归瞬间把栈撑爆。

正确的处理方式其实很简单——用 前缀递增 或者直接 显式加 1：

DeDupe(s, idx + 1, s1); // ✅ 推荐：语义清晰，无副作用
// 或
DeDupe(s, ++idx, s1);   // ✅ 也可行，但易混淆，不推荐用于递归参数

不过话说回来，这个程序里还藏着两个更深层的设计问题，如果不一起处理，光改递增符号也救不回来：

1. 静态布尔数组 ar[] 没有重置：ar 是个静态字段，如果多次调用去重方法（比如测试多组输入），上一次的标记会残留，导致后续结果错乱。解决办法很简单——要么把它改成方法内的局部变量，要么每次调用前手动清空。
2. 字符串拼接的效率与逻辑瑕疵：s1 += ... 在递归中频繁创建新字符串，性能开销不小。更重要的是，当前的逻辑只在字符首次出现时追加，却 遗漏了 else 分支的递归调用——也就是说，当字符重复时，程序直接走了 if 里那条路，却没有递归进入下一个位置，导致部分字符被悄悄跳过。

下面给出一个修复后的完整版本，关键改动都用注释标明了：

import ja va.util.Scanner;

public class RemoveDuplicates {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        // 使用局部布尔数组，确保每次调用独立
        boolean[] seen = new boolean[26];
        DeDupe(s, 0, "", seen);
    }

    public static void DeDupe(String s, int idx, String result, boolean[] seen) {
        // 基础终止条件
        if (idx == s.length()) {
            System.out.println(result);
            return;
        }

        char c = s.charAt(idx);
        int pos = c - 'a';

        // 检查是否为小写字母（增强鲁棒性）
        if (pos >= 0 && pos < 26) {
            if (!seen[pos]) {
                seen[pos] = true;
                DeDupe(s, idx + 1, result + c, seen); // ✅ 正确递进：idx+1
            } else {
                // 字符已存在，跳过，继续处理下一个
                DeDupe(s, idx + 1, result, seen); // ✅ 同样需 idx+1
            }
        } else {
            // 非小写字母：直接保留（可根据需求调整策略）
            DeDupe(s, idx + 1, result + c, seen);
        }
    }
}

最后，给几条实用建议，就当是多年踩坑换来的经验：

• 永远不要在递归参数里写 i++ 或 ++i：最安全的做法是直接用 i + 1，语义清晰，没有副作用，一眼就能看懂。
• 静态状态变量要慎用：但凡涉及递归或多次调用，优先用参数传递或局部变量，别省那点内存。
• 递归的每个分支都必须向终止条件靠近：写完之后，逐个检查所有路径，确认递归变量确实在更新。
• 别忘了输入边界：这里假设输入全是小写字母，真实项目里建议把大小写、数字甚至 Unicode 都考虑进来。
• 性能敏感的场景：result + c 在深度递归中会产生大量临时字符串，可以考虑用 StringBuilder 来优化——但要注意 StringBuilder 可变，在递归回溯时需要手动撤销追加操作，稍微麻烦一点。

修正完这些，程序就能稳定运行，正确输出按首次出现顺序去重后的字符串，同时彻底告别栈溢出。