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.

do you want to do this as part of oneplus2 invite hack? :P — Karthik
– Karthik, Commented Aug 6, 2015 at 12:00
Hehe, @ReservoirSampling, I did get the idea from the post in medium, but I have no intention of purchasing OnePlus 2, or hacking its invite system (wouldn't touch that phone with a 10 foot pole). I just wanted to do the same string manipulation in java as a way of passing time, like I said, seemed a no-brainer and then I got stuck! :( — inquizitive
– inquizitive, Commented Aug 6, 2015 at 12:02

M. Shaw · Accepted Answer · 2015-08-06 12:45:07Z

2

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

answered Aug 6, 2015 at 12:45

M. Shaw

1,74211 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

inquizitive Over a year ago

Thanks a lot for your answer. This is what I was expecting my code to be. But I was missing the 2nd recurse call.

Serge Ballesta · Accepted Answer · 2015-08-06 12:32:26Z

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

answered Aug 6, 2015 at 12:32

Serge Ballesta

150k13 gold badges137 silver badges267 bronze badges

1 Comment

inquizitive Over a year ago

Thanks a lot for your answer, this works quite well. Actually, what I wanted to know was what was wrong in my approach. This could have been done in many ways, but I chose one and I couldn't complete the thing with that, hence I was interested in knowing what was missing from my code!

Andrew · Accepted Answer · 2015-08-06 12:07:12Z

1

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

answered Aug 6, 2015 at 12:07

Andrew

49.8k15 gold badges99 silver badges145 bronze badges

6 Comments

Codebender Over a year ago

As you can see in the output and code, you are printing each string twice. Which may not be what the OP wants.

inquizitive Over a year ago

Updated the question with required output. Basically I want all permutations of dots between the characters

Andrew Over a year ago

@inquizitive, i don't understand your algorithm

Andrew Over a year ago

@inquizitive, te.s.t -> t.e.s.t -> t.e.st Explain me this sequence

inquizitive Over a year ago

There is no sequence in the question, I have just tried to show all combinations possible with test. The sequence is not important.

|

Codebender · Accepted Answer · 2015-08-06 12:25:15Z

1

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.

answered Aug 6, 2015 at 12:25

Codebender

14.5k7 gold badges51 silver badges87 bronze badges

3 Comments

Will Norvelle Over a year ago

Won't this be stuck infinitely calling recurse()? The beginning of each loop calls recurse() which starts another loop which calls recurse() and so on until the computer complains about having too many functions in the stack. The recursive nature of this problem means you don't want a loop, or at least not one that calls the function inside of it with no way to escape.

inquizitive Over a year ago

Thanks, this works, and you have probably the closest answer to what I was looking for since I wanted to know what needed to be added to the code I HAD ALREADY written. Oh.. and I added if(!pre.isEmpty()) pre += "."; for the initial dot!

Codebender Over a year ago

@Will, the condition in the loop will stop the infinite recursion.

dejvuth · Accepted Answer · 2015-08-06 12:33:46Z

1

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

answered Aug 6, 2015 at 12:33

dejvuth

7,1743 gold badges37 silver badges37 bronze badges

Collectives™ on Stack Overflow

Creating recursion in Java

5 Answers 5

1 Comment

1 Comment

6 Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

1 Comment

6 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related