Just a little recursion issue in Java

Question

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.

Answer 1

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.