CODEWITHSUNDEEP
javarecursion
inquizitive
inquizitive

Reputation: 632

Creating recursion in Java

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.

Upvotes: 3

Views: 172

Answers (5)

M. Shaw
M. Shaw

Reputation: 1742

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 + ".");
}

Upvotes: 2

dejvuth
dejvuth

Reputation: 7136

I guess you want to append a new character to pre for each recursive call by taking the first character from str, so you should stop when only one character is left in str.

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

    recurse(pre + str.substring(0, 1), str.substring(1));
    if (pre.length() > 0)
        recurse(pre + "." + str.substring(0, 1), str.substring(1));
}

Calling it with recurse("", "test"); gives you:

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

Upvotes: 1

Serge Ballesta
Serge Ballesta

Reputation: 148940

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

Upvotes: 2

Codebender
Codebender

Reputation: 14471

You need to recurse in a loop to get all possibilities.

public static void recurse(String pre, String str) {
    pre += ".";
    System.out.println(pre + str);
    for (int i = 1; i <= str.length(); i++)
        recurse(pre + str.substring(0, i), str.substring(i));
}

Output:

.tes
.t.es
.t.e.s
.t.e.s.
.t.es.
.te.s
.te.s.
.tes.

Note: You may need to modify this a little to not include the . at the beginning.

Upvotes: 1

Andrew
Andrew

Reputation: 49606

You might use the following piece of code:

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

Output:

test
t.est
t.e.st
t.e.s.t
t.e.st
t.est
test

Upvotes: 1

Related Questions