Creating recursion in Java

Question

Initially this seemed like a no brainer, but the more I am trying to do this, the more I am getting stuck.

I am looking to create a recursive method that will take a string and output combination with dots as below:

input: test

output:

test
t.est
te.st
tes.t
t.es.t
te.s.t
t.e.s.t
t.e.st

you get the idea... I need all permutations of dots between the characters. But two dots should not appear together and dot should not be the first or the last character.

The code I have written is:

public final class Main{
   public static void main(String[] args) throws Exception{
      recurse ("test");
   }

   public static void recurse(String str){
        recurse("",str);
   }

   public static void recurse (String pre, String str){
      if(str.length() > 1){
         recurse(pre+str.substring(0,1)+".",str.substring(1));
      }
      System.out.println(pre+str);  
   }
}

But, I can't get my head around it. What change should I do?

Just for the sake of clarification I got the idea from https://medium.com/@JakeCooper/so-nice-i-did-it-twice-hacking-the-oneplus-reservation-system-again-2e8226c45f9a, but I do not have any intention of hacking the invite system.

Answer 1

Try

public static void recurse(String prev, String next) {
    if (next.length() == 0) 
        System.out.println(prev);
    else {
        recurse(prev + next.charAt(0), next.substring(1));
        recurse(prev + "." + next.charAt(0), next.substring(1));
    }    
}

If you allow . to precede the entire String as well, use:

String s = "test";
recurse("",s);

If you don't allow . to precede:

recurse(s.charAt(0), s.substring(1));

If you allow . to be appended (i.e. test. , t.e.s.t.), change the if block to

if (next.length() == 0) {
    System.out.println(prev);
    System.out.println(prev + ".");
}

Answer 2

I would pass the position in the string to the recurse function :

public static void recurse(String str) {
    recurse(str, 1); // start only at 1 since we do not want dot at first position
}

public static void recurse(String str, int n) {
    if (n >= str.length()) { // >= since no dot at last position
        System.out.println(str); // ok we have a full string : print it
    } else {
        recurse(str, n + 1);    // either not dot and recurse
        str = str.substring(0, n) + "." + str.substring(n); // or add one at n
        recurse(str, n + 2);   // and recurse too
    }
}

The output of recurse("test") is as expected :

test
tes.t
te.st
te.s.t
t.est
t.es.t
t.e.st
t.e.s.t