7

我正在研究一些介绍性的递归问题，并且我有一个想要回答的澄清问题。我遇到的最烦人的问题是，这个递归在下面解决的问题中是如何运作的？

尽管已经解决了这个问题，但我只是不明白递归调用是如何进入字符串内部的。仅从代码来看，该方法似乎只会检查给定字符串两端的两个字符，而不会检查其余字符。我的教科书给出了一个非常不令人满意的答案，基本上，只要你的 return 语句改进了问题，就不用担心递归是如何工作的。但是我很难知道如何处理后续的递归问题，而不了解如何以与跟踪循环相同的方式跟踪递归方法。

任何智慧之言将不胜感激。

谢谢！

public class isPalindrome {

public static boolean isPalindrome(String str)
{
    //test for end of recursion
    if(str.length() < 2) {return true;}

    //check first and last character for equality
    if(str.charAt(0) != str.charAt(str.length() - 1)){return false;}

    //recursion call 
    return isPalindrome(str.substring(1, str.length() - 1));
}
public static void main(String[] args)
{
    System.out.print(isPalindrome("deed"));
}
}
4

2 回答 2

12

isPalindrome() 函数在 str.substring(1, str.length() -1) 上被递归调用。因此，对于 isPalindrome() 调用，调用堆栈将如下所示：

1. isPalindrome("abcddcba"): 

   ("a" == "a") = true, so recurse

2. isPalindrome("bcddcb"):

   ("b" == "b") = true, so recurse

3. isPalindrome("cddc"):     

   ("c" == "c") = true, so recurse

4. isPalindrome("dd"): 

   ("d" == "d") = true, so recurse  

6. isPalindrome(""):           

   length < 2, so return true

最后一次调用的返回值将一直传播到顶部。

通过递归，图片总是有帮助的。尽力将调用堆栈绘制成图表。它将允许您可视化并因此更好地理解更复杂的递归。这是一个简单的“线性”递归，但您最终会遇到类似递归的“树”。

这是一张图片，说明了这个确切的问题，以便您更好地可视化：

回文递归

于 2012-02-02T05:22:19.487 回答
9

想想回文：

risetovotesir

这实际上可以通过从回文开始v（一个字符的字符串总是回文，空字符串也是如此）并在前后添加相同的字母来构建：

      v           Start with palindrome 'v'.
     ovo          Add 'o' to both ends.
    tovot         Then 't'.
   etovote        Then 'e'.
  setovotes       Then 's'.
 isetovotesi      Then 'i'.
risetovotesir     And finally 'r'.

该递归函数使用的过程是相反的方向，将字符串逐位分解。它检测它是否确实是一个回文是如果两者：

  • 第一个和最后一个字符相等；和
  • 字符串的内部（一旦这两个被删除）是一个回文。

因此代码可以写成：

public static boolean isPalindrome (String str) {
    // Zero- or one-character string is a palindrome.

    if (str.length() < 2)
        return true;

    // If first and last characters are different, it's NOT palindromic.

    if (str.charAt (0) != str.charAt (str.length() - 1))
        return false;

    // Otherwise it's palindromic only if the inner string is palindromic.

    return isPalindrome (str.substring (1, str.length () - 1));
}

使用 的字符串peed deep，不同的级别是：

1. length 9 >= 2, both ends are 'p', next level checks 'eed dee'.
2. length 7 >= 2, both ends are 'e', next level checks 'ed de'.
3. length 5 >= 2, both ends are 'e', next level checks 'd d'.
4. length 3 >= 2, both ends are 'd', next level checks ' ' (space).
5. length 1 <  2, return true.

或者，一个非回文（虽然非常接近）star rots给你：

1. length 9 >= 2, both ends are 's', next level checks 'tar rot'.
2. length 7 >= 2, both ends are 't', next level checks 'ar ro'.
3. length 5 >= 2, ends are 'a' and 'o', so return false.
于 2012-02-02T05:23:45.497 回答