Unexpected recursive behavior in Java

Question

public class Main21 {

    static int count=0;
    
    public static void printer(String s, int n, int sz){
        
        if(n>sz-1)
            return;
       String s1=s+"P";
       String s2=s+"A";
       String s3=s+"L";
       
       if(s1.length() == sz && s2.length() == sz && s3.length() == sz){
           
               if( !s1.contains("AA") && !s1.contains("LLL") && !s2.contains("AA") && !s2.contains("LLL") && !s3.contains("AA") && !s3.contains("LLL") )
               {
                   System.out.print(s1+" "+s2+" "+s3+" ");
                   count++;
               }
       }         
       printer(s1,n+1,sz);
       printer(s2,n+1,sz);
       printer(s3,n+1,sz);
    
    }
    public static void main(String[] args) {
        int sz=2 ;
        printer("P",1,sz);
        printer("A",1,sz);
        printer("L",1,sz);
        
        System.out.println("\n"+count*3);
    }

}

I am getting result: PP PA PL LP LA LL 6

AL and AP is getting missed. But when I am passing size as 3 its working fine. Could you please point out the fault?

When passed 3:

PPP PPA PPL PLP PLA PLL APP APA APL ALP ALA ALL LPP LPA LPL  15

If s ends in A then s2.contains("AA") will be true, which prevents the print. — khelwood
– khelwood, Commented Apr 3, 2021 at 7:37
Any solution to prevent it? I want to indentify if there exists consecutive "AA" and consecutive "LLL" present or not. — David Johnson
– David Johnson, Commented Apr 3, 2021 at 8:19

Davide D'Alto · Accepted Answer · 2021-04-03 16:43:47Z

I think the problem is that when you check the strings you skip printing all of them even if only one of the three is invalid.

Here's possible solution that also removes some duplicated code:

public class Main21 {

    static int count = 0;

    public static void printer(String s, int n, int sz) {
        if ( n > sz - 1 ) {
            return;
        }
        String s1 = s + "P";
        String s2 = s + "A";
        String s3 = s + "L";

        StringBuilder builder = new StringBuilder();
        appendIfValid( builder, sz, s1, s2, s3 );
        if ( builder.length() > 1 ) {
            System.out.print( builder.toString() );
            count++;
        }

        printer( s1, n + 1, sz );
        printer( s2, n + 1, sz );
        printer( s3, n + 1, sz );
    }

    private static void appendIfValid(StringBuilder builder, int sz, String... strings) {
        for ( String s : strings ) {
            if ( valid( sz, s ) ) {
                builder.append( s );
                builder.append( " " );
            }
        }
    }

    private static boolean valid(int sz, String s) {
        return s.length() == sz
                && !s.contains( "AA" )
                && !s.contains( "LLL" );
    }

    public static void main(String[] args) {
        int sz = 3;
        printer( "P", 1, sz );
        printer( "A", 1, sz );
        printer( "L", 1, sz );

        System.out.println( "\n" + count * 3 );
    }

}

This code could be improved by skipping the recursion when the string is invalid. You could also create the StringBuilder only once and print everything once at the end.

Collectives™ on Stack Overflow

Unexpected recursive behavior in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related