如何解决生成无连续1的二进制字符串代码的StackOverflowError

问题描述 #

运行一段生成长度为n且无连续1的二进制字符串的Java代码时，抛出java.lang.StackOverflowError，错误栈指向字符串拼接位置，无法正常输出目标字符串。

原代码 #

//Question: print all binary string of size n without consecutive one's

import java.util.*;
public class BinaryString {
    
    public static void binaryString(int n , int lastPlace , String str)
    {
        if(n==0)
        {
            System.out.println(str);
        }
        binaryString(n-1,0,str + "0");
        if(lastPlace==0)
        {
            binaryString(n-1,1,str+ "1");
        }
    }

    public static void main(String args[])
    {
        System.out.println("Enter value of n: ");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        binaryString(n,0," ");
        sc.close();
    }
}

错误信息（翻译后） #

Exception in thread "main" java.lang.StackOverflowError
        at java.base/jdk.internal.misc.Unsafe.allocateUninitializedArray(Unsafe.java:1380)
        at java.base/java.lang.StringConcatHelper.newArray(StringConcatHelper.java:441)
        at java.base/java.lang.StringConcatHelper.simpleConcat(StringConcatHelper.java:365)
        at BinaryString.binaryString(BinaryString.java:10)

错误原因 #

递归缺少终止逻辑：当n==0时，打印完字符串后没有执行return，导致后续的递归调用仍然会执行，形成无限递归，最终耗尽栈空间抛出StackOverflowError。另外初始调用传入的字符串是" "（带空格），会导致输出的二进制字符串开头多一个空格，不符合预期。

修复后的代码 #

//Question: print all binary string of size n without consecutive one's

import java.util.*;
public class BinaryString {
    
    public static void binaryString(int n , int lastPlace , String str)
    {
        if(n==0)
        {
            System.out.println(str);
            // 递归终止，返回上层调用
            return;
        }
        binaryString(n-1,0,str + "0");
        if(lastPlace==0)
        {
            binaryString(n-1,1,str+ "1");
        }
    }

    public static void main(String args[])
    {
        System.out.println("Enter value of n: ");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 初始字符串改为空字符串，避免开头多余空格
        binaryString(n,0,"");
        sc.close();
    }
}

修复说明 #

1. 在n==0的分支中添加return;，确保递归在完成打印后终止，不再执行后续的递归调用。
2. 将初始调用的第三个参数从" "改为""，消除输出字符串开头的多余空格。

验证示例 #

输入n=3，会输出以下符合要求的二进制字符串：

000
001
010
100
101

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