只是Java中的一点递归问题

java recursion

2022-09-01 10:04:20

我目前只是在努力解决一些递归问题，目前我被困在一个问题上。

问题是将空格递归地插入到字符串中，插入到每个可能的位置，使得输出看起来像这样：

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

我目前已经解决了这个问题，并达到了一个很像的地步：

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

到目前为止，我对这个问题的代码：

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));

}
}

第二个 else 子句是我遇到最大麻烦的地方，因为每次我运行它时，它都会进入一个无限循环。我甚至放了int trace语句（语句），但它仍然没有帮助。println

我已经通读了很多次，对我来说，为什么它不起作用是没有意义的。

答案 1

让我对你的代码产生怀疑的第一件事是，你应该返回一系列字符串，但你的返回值是一个字符串。

也许，你应该确定你的基本情况和递归步骤。

看起来你已经从基本案例开始了。您可以在空字符串中插入零空格，因此

allPossibleSpacings("") -> [ "" ]

但是您不想在末尾插入空格，因此您需要第二个基本情况

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

然后你的递归步骤可能是

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

我不会帮你用Java写它，因为它是家庭作业，但希望这有帮助。

答案 2

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);
            }
        }
    }

首先使用递归调用（“ABCD”， 1）;