Just a little recursion issue in Java

I'm currently just working my way through some recursion problems, and I am currently stuck on one.

The problem is to recursively insert spaces into a string, into every single possible location, such that the output looks something like:

Input: ABCD
Out:
       ABCD
       A BCD
       A B CD
       A B C D
       A BC D
       AB CD
       AB C D
       ABC D

I have currently worked on the problem, and got to a point much like:

Input: ABCD
Out:
       ABCD
       A BCD
       A B CD
       A B C D

My code for the problem so far:

import java.util.Scanner;

public class Words 
{
    static int counter = 0;
    static String fString = "";
    static String fString2 = "";
    static String previous = "";
    static String input = "";
    static String other = "";

    public static String segment(String inputPrefix, String restOfString)
{
    if(restOfString.length() != 0)
    {   
        if(inputPrefix.equals(""))
        {
            fString += restOfString + "\n";
            segment(restOfString.substring(0,1), restOfString.substring(1));
        }
        else
  开发者_运维技巧      {
            previous += inputPrefix + " ";
            fString += previous + restOfString + "\n";
            fString2 = previous + restOfString;
            segment(restOfString.substring(0,1)
                            , restOfString.substring(1));
        }
    }
    /*else
    {
        counter++;
        other = fString2.replaceAll(" ", "");
        System.out.println(other);
        if((counter + 1) < other.length())
        {
            System.out.println("Other: " + other);
            input = other.substring(0, counter + 1);
            other = other.substring(counter + 1);
            System.out.println(counter);
            System.out.println("input: " + input);
            System.out.print("other: " + other);

            segment(input, other);
        }
        else
            return fString;
    }*/

    return fString;

}

public static void main (String[] args) 
{
    Scanner scan = new Scanner(System.in);
    System.out.print("Enter a string: ");
    String input = scan.next();
    System.out.println();
    System.out.println(segment("", input));

}
}

That second else clause is where I am having my most trouble, because every time I run it un-commented it goes into an infinite loop. I even put int trace statements (the println statements) and it still isn't helping.

I've read through it many times and it just doesn't make sense to me why it doesn't work.

The first thing that makes me dubious about your code is that you are supposed to returning a series of strings, but your return value is a string.

Perhaps, you should nail down your base case and recursive step.

It looks like you've got a start on the base case. You can insert zero spaces in the empty string, so

allPossibleSpacings("") -> [ "" ]

but you don't want to insert a space at the end, so you need a second base case

allPossibleSpacings("x") -> [ "x" ]

and then your recursive step could be

allPossibleSpacings("x" + s) -> flatten(
    ∀ t : allPossibleSpacings(s), ["x" + t, "x " + t])

I won't help you write that in Java since it's homework, but hope that helps.

void recurse(String myString, int start){
        System.out.println(myString);
        for(int i = start; i < myString.length; i++) {
            if (myString.charAt(i) != ' ' ){
                recurse(myString.Substring(0,i) + ' ' + myString.Substring(i), i+2);
            }
        }
    }

call first with recurse("ABCD", 1);

It looks like you've been able to do the first 'grouping' correctly, but unable to get the next groupings.

The groupings are: 'A BCD', 'AB CD', and 'ABC D'. You need to apply your algorithm to each of these groupings. You've applied it to the first. How do you get the rest of them?

Has enough time passed? I wrote up a python solution just to see what it'd look like compared to Java.

def segment(input, separator=' ', start_from=0):
    print input
    # add spaces after each letter starting from start_from index, terminating at last letter-1
    for i in range(start_from, len(input)-1):
        # if the next letter is already a space, or this letter is a space, move on
        if separator in (input[i+1], input[i]): continue
        # whatever index we're on, do the next one recursively
        segment(input[:i] + input[i] + separator + input[i+1:], separator=separator, start_from=i+1)

segment('ABCD')