Java - using recursion to create all substrings from a string

Question

The following code in Java uses recursion to create all possible substrings from a string. I am wondering is there a better way of coding this? I want to use recursion.

public class main {

    public static void main(String[] args) {
        generate("hello");
    }

    public static void generate(String word) {
        if (word.length() == 1) {
            System.out.println(word);
            return;
        }else{
            System.out.println(word);
            generate(word.substring(0, word.length()-1)); 
            generate(word.substring(1, word.length())); 
        }

    }

}

FAQ Q - Why do I want to do this using recursion? A - Because the CEO of StackOverflow says recursion is important http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

Answer 1

This problem has overlapping subproblems and because of that the top-down recursion as you do is not much effective. You are evaluating multiple substrings multiple times.

Actually it is horribly ineffective (I would guess O(2^n)). Just try to run it on a bit longer string.

generate("OverlappingSubproblems");

If you are interested in a better way of solving this you can try something like this:

public static void generate2(String word) {
    for (int from = 0; from < word.length(); from++) {
        for (int to = from + 1; to <= word.length(); to++) {
            System.out.println(word.substring(from, to));
        }
    }
}

If you want to use recursion you can try to rewrite the for-loops with recursion as exercise ;)

Answer 2

The following turned out to be the best solution:

public class recursive {

    static String in = "1234";

    public static void main(String[] args) {
        substrings(0,1);
    }

    static void substrings(int start, int end){
        if(start == in.length() && end == in.length()){
            return;
        }else{
            if(end == in.length()+1){
                substrings(start+1,start+1);
            }else{
                System.out.println(in.substring(start, end));
                substrings(start, end+1);
            }
        }
    }

}

It first checks the base case: if both start and end are equal to in.length(). Because if they are, that means there are no more substrings to be found, and the program ends.

Let's start with start=0 and end=1. They obviously don't equal in.length(), and end definitely doesn't equal in.length()+1. Thus, substring(0,1) will be printed out, which is 1. The next iteration of substrings will be substrings(0,2), and in.substring(0,2) will be printed, which is 12. This will continue until end == in.length()+1, which happens when the program finishes substrings(0,4) and tries to move on to substrings(0,5). 5 == in.length()+1, so when that happens, the program will do substrings(start+1,start+1), which is substrings(1,1). The process will continue with substrings(1,2), and (1,3), until (1,5) when the program will run substrings(2,2).

All of this will continue until substrings(4,4), which, at that point, the program stops.

The result looks like this:

1 12 123 1234

2 23 234

3 34

4

Answer 3

There is a lot to be learned from Honza's answer.I suggest you try and rewrite that as a recursive algorithm.

As with any recursive approach, divide it into self-referencing subproblems:

1. substrings(X) = substrings_starting_at_first_character(X) + substrings(X minus first char).
2. substrings_starting_at_first_character(X) = X + substrings_starting_at_first_character(X minus last char).

Next figure out your non-self-referencing base cases:

1. substrings("") = empty set.
2. substrings_starting_at_first_character("") = empty set.

And go from there.