java - 递归 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

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

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

对于递归，图片总是有帮助的。尽最大努力将调用堆栈画成图表。它将允许您可视化，从而更好地理解更复杂的递归。这是一个简单的“线性”递归，但您最终会遇到类似“树”的递归。

这里有一张图片可以说明这个确切的问题，以便您更好地形象化: