递归实现字符串去重遇Stack Overflow Error，求问题排查

核心问题原因 #

你代码里的递归调用语句DeDupe(s, idx++, s1);用了后自增运算符++，这个运算符的逻辑是先将当前idx的原值传递给方法，再对idx执行加1操作。这就导致每次递归调用传入的idx永远是初始的0（或者上一层的旧值），永远触发不了idx == s.length()的终止条件，无限递归下去最终引发Stack Overflow Error。

修复方案 #

把递归调用里的idx++改成idx + 1（推荐，不修改当前方法的idx变量，避免逻辑混乱），或者++idx（前自增，先加1再传递值）：

DeDupe(s, idx + 1, s1);

额外优化建议 #

1. 静态数组状态残留问题：全局静态数组ar在多次调用DeDupe时会保留上一次的标记状态，导致后续调用结果错误。可以在每次调用前重置数组：

   // 在main方法调用前重置数组
   Arrays.fill(ar, false);
   DeDupe(s, 0, "");
   

2. 字符串拼接效率问题：s1 += s.charAt(idx)每次都会生成新的String对象，递归次数多的时候效率很低，建议改用StringBuilder维护结果：

   public static void DeDupe(String s, int idx, StringBuilder sb) {
       if (idx == s.length()) {
           System.out.println(sb.toString());
           return;
       }
       char c = s.charAt(idx);
       if (!ar[c - 'a']) {
           sb.append(c);
           ar[c - 'a'] = true;
       }
       DeDupe(s, idx + 1, sb);
   }
   // main方法里调用
   DeDupe(s, 0, new StringBuilder());
   

修复后的完整代码 #

import java.util.Arrays;
import java.util.Scanner;

public class RemoveDuplicates {
    public static boolean ar[] = new boolean[26];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        Arrays.fill(ar, false); // 重置标记数组
        DeDupe(s, 0, new StringBuilder());
        sc.close();
    }

    public static void DeDupe(String s, int idx, StringBuilder sb) {
        if (idx == s.length()) {
            System.out.println(sb.toString());
            return;
        }
        char c = s.charAt(idx);
        if (!ar[c - 'a']) {
            sb.append(c);
            ar[c - 'a'] = true;
        }
        DeDupe(s, idx + 1, sb);
    }
}

内容的提问来源于stack exchange，提问作者Yukta Jaiswal