0

我必须使用递归来解决这个问题,我设法使用循环很快地使它工作,但我有点卡在这个问题上。我目前的代码是

public static String ReverseR(String n){
    String finalstring="";
    int i = 0;
    int len = n.length();
    while (i < len) {
        finalstring += (n.charAt(len -  1));
        ReverseR(n.substring(0, len - 1));
        i++;
    }
    return finalstring;
}

当我输入任何字符串时,结果字符串的长度是正确的,但只使用最后一个字母。例如:ReverseR("Hello") = ooooo 有什么想法吗?

4

4 回答 4

5

递归有点像归纳证明。

  1. 摆脱while循环
  2. 如果您要反转一个 0 字符的字符串,这很简单:只需返回 ""
  3. 如果要反转 n 个字符的字符串,请反转 [0..n-2] 并在最后一个字母前面。你已经在做什么了。
于 2013-10-22T19:12:43.180 回答
1

更改n.charAt(len - 1))n.charAt(len - i))

你总是和 len -1 在同一个地方;)

[编辑]

while (i < len){
    finalstring += (n.charAt(len - 1 - i));
    ReverseR(n.substring(0, len - 1 - i));
    i++;
}

这将修复您的代码,但是您必须选择whileReverseR(...)

重复的问题,检查这个Reversing a String with Recursion in Java

于 2013-10-22T19:11:40.343 回答
0

这是一个完整的工作解决方案

public static String reverse(final String s) {
    if (s == null) {
        throw new NullPointerException();
    }

    final int length = s.length();
    if (length <= 1) {
        return s;
    } else {
        // s = start + lastChar
        final String start = s.substring(0, length - 1); 
        final char lastChar = s.charAt(length - 1);
        return lastChar + reverse(start);
    }
}
于 2013-10-22T19:17:39.620 回答
0

您的递归算法不应该需要任何循环,即whilefor循环。任何循环结构基本上都可以通过递归来实现,而无需接触循环。基本递归字符串反转的示例可能如下所示:

public static String reverseR(String n){
  if (n.length() <= 1) return n;
  return reverseR(n.substring(1))+n.charAt(0);
}

使用此算法,您基本上是在说:返回“除第一个之外的每个字母的反转”+“第一个字母”

帮助编写递归算法的一件好事是做出很多假设。首先假设您的 reverse 函数有效,然后将其放置在您想要反转部分字符串的任何位置。只要记住添加一个基本案例,你就会很成功。像HaskellProlog会让你习惯递归算法的语言,因为这是它们迭代的主要来源。

于 2013-10-22T19:39:41.893 回答