递归isPalindrome函数如何工作？

Question

我正在研究一些介绍性的递归问题,我有一个澄清的问题,我想得到答案.我遇到的最棘手的问题是这个递归是如何在下面解决的问题中运行的？

尽管已经解决了这个问题,但我只是不理解递归调用如何进入字符串的内部.从查看代码看,这个方法似乎只检查给定字符串两端的两个字符,而不检查其余字符.我的教科书给出了非常不满意的答案,基本上,只要你的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"));
}
}

Answer 1

在str.substring(1,str.length() - 1)上递归调用isPalindrome()函数.所以对于isPalindrome()调用,callstack看起来像这样:

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

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

随着递归,图片总是有帮助.尽力将callstack绘制成图表.它将允许您可视化,因此更好地理解更复杂的递归.这是一个简单的"线性"递归,但你最终会像递归一样面对"树".

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

Answer 2

想想回文:

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.