需要一些帮助来为我的回文应用程序编写递归实现

Question

首先，我并不是要求人们“做我的作业”，就像我在这里看到的其他人所要求的那样。我已经成功编写了一个程序的工作迭代版本，用于确定字符串是否是回文。在确定字符串是否为回文时，空格、标点符号和特殊字符将被忽略。这个版本确实有效，但是当我尝试在“isPalindrome()”方法中应用递归语句时，我收到堆栈溢出错误。我知道这些错误是什么，只是在这样的程序中应用递归方法对我来说很难理解（两周前我才了解到它们）。无论如何，这是迄今为止我成功编译（和运行）的代码：

---

/** Palindrome.java: A sigle application class that determines if a word or a string
  * is a palindrome or not. This application is designed to ignore spaces between
  * chars, punctuation marks and special characters while determining if the word or
  * string is a palindrome or not.
  * 
  **/

import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.regex.*;

public class Palindrome{

  static String palindrome, str, str2, str3;

  /** The main method of the Palindrome application. Takes input from the
    * user, removes spaces from their input, turns their string input into
    * lowercase and then all non letter characters are taken out of the user's
    * input. Finally the recursive method determines if the string entered in
    * by the user is a palindrome.
    * 
    * @param args Takes in a string array of arguements
    **/
  public static void main(String[] args){
    Scanner input = new Scanner(System.in);
    while(input.hasNext()){ 
      str = removeSpaces(input.nextLine());
      str2 = str.toLowerCase();
      str3 = normalise(str2);
    }
    System.out.println(isPalindrome(str3));

  }

  /** The default constructor
    **/
  public Palindrome(){
  }

  /** isPalindrome(): A boolean method that is passed through a String input
    * and uses a for loop, two inner while loops and an if-else to determine
    * whether the users input is a palindrome.
    *
    * @param s The string input to be tested
    * @return true The users input is a palindrome
    * @return false The users input isn't a palindrome
    **/
  public static boolean isPalindrome(String s){

    int first, last;

    for(first = 0, last = s.length()-1 ; first < last ; first++ , last-- ){
      while( (int)s.charAt(first) < 'a' || (int)s.charAt(first) > 'z' ){
        first++;
      }
      while( (int)s.charAt(last ) < 'a' || (int)s.charAt(last ) > 'z' ){
        last--;
      }
    }
    if( first > last || s.charAt(first) != s.charAt(last) ){
      //return isPalindrome(s.substring(0, s.length()-1)) == false;
      return false;
    }
    else{
      //return isPalindrome(s.substring(0, s.length()-1)) == true;
      return true;
    }
  }

  /**
   * This method takes out punctuation marks in the string parsed
   * through, using Java's regular expressions (regex) and Java's
   * inbuilt method replaceAll(). The regex expression is passed
   * through the replaceAll() method to remove all non alpha-numeric
   * characters from the string passed through the method's parameter.
   * 
   * @param t The string that will have punctuation stripped from it.
   *
   * @return t The string has had all non alpha-numeric characters
   * removed and the new string is then returned.
   */
  public static String normalise(String t){
    t = t.replaceAll("[^a-zA-Z0-9]", "");
    return t;
  }

  /** removeSpaces(): A method that deletes spaces from the users input
    * and then decrements the string length count so any indexes aren't missed
    * when it is incremented.
    * 
    * @param s The string which is going to have it's spaces removed.
    * @return temp The new string is then returned after the spaces have been taken out.
    **/
  public static String removeSpaces(String s){
    StringBuilder temp = new StringBuilder(s); //creates a new StringBuilder with the inputted String
    for(int i = 0; i < temp.length(); i++){ //do this for the entire length of the StringBuilder

      if(temp.charAt(i) == ' '){ //if the char at i is a space

        temp.deleteCharAt(i); //remove the char
        i--; //subtract 1 from the counter so we don't miss an index when we increment it
      }
    }
    return temp.toString(); //return the new String
  }
}

---

我现在已经删除了递归方法中的递归语句。如果有人能告诉我到底做错了什么，并帮助我实施一个解决方案，那就太好了。我宁愿坚持使用迭代版本，因为我了解它的机制，但被要求做一个递归版本（我从去年年中休息后就开始进行 Java 编码，但在递归方面相对新手），这证明了这是一个相当大的挑战。如果您更改代码并且最终使用递归版本，请解释您的更改的方式、时间、原因等。我不是在找人帮我做这件事，我想学习，而且似乎我通过示例学到了最好的东西（去年我通过分析示例和阅读实现的解释获得了 B 及格）。非常感谢:)。

编辑：我想我现在递归已经正常了，只是逻辑是目前让我困惑的事情。这是 isPalindrome() 方法的重新编码版本：

  public static boolean isPalindrome(String s){

    int first, last;
    boolean isPalindr = true;

    if (s.length() <= 1){
      return true; // Base case
    }

    for(first = 0, last = s.length()-1 ; first < last ; first++ , last-- ){
//      while( (int)s.charAt(first) < 'a' || (int)s.charAt(first) > 'z' ){
//        first++;
//      }
//      while( (int)s.charAt(last ) < 'a' || (int)s.charAt(last ) > 'z' ){
//        last--;
//      }
//  }
      if( first == last || s.charAt(first) == s.charAt(last) ){
        //return isPalindrome(s.substring(first, last));
        return isPalindrome(s.substring(first, last)) == true;
        //isPalindr = false;
      }
      else{
        return isPalindrome(s.substring(first, last)) == false;
        //isPalindr = true;
      }
    }
    return isPalindr;
  }

如果有人可以帮助我解决逻辑，我认为这将被修复:)。

Answer 1

删除所有与问题无关的代码后，我们会得到这样的结果：

public static boolean isPalindrome(String s){
   for loop {
      isPalindrome(); 
   }
}

isPalindrome 调用 isPalindrome 调用 isPalindrome 等等......无限。

它与正确的递归函数之间的区别在于，递归函数将具有某种条件语句，从而打破函数调用自身的循环。执行流程将如下所示：

isPalindrome(1) begins execution and calls isPalidrome(2)
 isPalindrome(2) begins execution and calls isPalidrome(3)
  isPalindrome(3) begins execution and calls isPalidrome(4)
   isPalindrome(4) begins execution and calls isPalidrome(5)
    isPalindrome(5) begins execution and returns to isPalindrome(4)
   isPalindrome(4) resumes execution and returns to isPalindrome(3)
  isPalindrome(3) resumes execution and returns to isPalindrome(2)
 isPalindrome(2) resumes execution and returns to isPalindrome(1)
isPalindrome(1) resumes execution and returns.

如果这种解释没有帮助，请这样想。假设有人递给你盘子，一次一个，看看你是否能同时拿 25 个盘子。它会像这样：

Plate 1 is given to you.  Are there 25 plates?  No.  Add another plate.
 Plate 2 is stacked on top of Plate 1.  Are there 25 plates?  No.  Add another plate.
  Plate 3 is stacked on top of Plate 2.  Are there 25 plates?  No.  Add another plate.
   ...
    Plate 24 is stacked on top of Plate 23.  Are there 25 plates?  No.  Add another plate.
     Plate 25 is stacked on top of Plate 24.  Are there 25 plates?  Yes.  Mission Accomplished.  Now, let's put the plates back.
     Plate 25 is removed.
    Plate 24 is removed.
   ...
  Plate 3 is removed.
 Plate 2 is removed.
Plate 1 is removed.

这是可能的编码方式：

bool stackPlates(int i){
   plateStack.addPlate();

   if (plateStack.wasDropped == true) { return false; }     // Were the plates dropped?  Return FALSE to indicate failure.
    else if (i < 25) { return stackPlates(i+1); }           // Are there 25 plates yet?  If not, add another.
     else { return true; }                                  // There are 25 plates stacked.  Return TRUE to indicate success.

   plateStack.removePlate(i);
}

这是从另一个函数调用的 stackPlates(int i)：

bool success = stackPlates(1);

if (success==TRUE) { cout << "CONGRATULATIONS!  YOU STACKED 25 PLATES!"; }
 else { cout << "YOU BROKE THE PLATES!  BETTER LUCK NEXT TIME!"; }

为了正常工作，你的函数需要做的是这样做：

bool isPalindrome(string s, int i) {

   char first = s[i];                   // REPLACE THIS WITH THE CODE TO SKIP SPACES & SPECIAL CHARACTERS
   char last = s[(s.length -1) -i];     // REPLACE THIS WITH THE CODE TO SKIP SPACES & SPECIAL CHARACTERS

   if ( first != last )  { return false; }                // return false if mismatch letter
    else if ( i >= (s.length/2) ) { return true; }        // return true if string fully checked
     else { return isPalindrome(s, i+1); }                // string not fully checked; move to next letter

}

Answer 2

您遇到堆栈溢出，因为函数底部的 else 分支在 (first <= last && "字符相等") 时执行，因此您不断重复出现字符串由一个组成的情况特点。

顺便说一句，我认为您的代码没有干净地使用递归：您应该在开始在字符串上重复之前仅对字符串进行一次预处理，并且执行回文递归的代码应该要简单得多。

Answer 3

对于任何给定的 isPalindrome 条目，它都会递归地调用自身，因为你对 else 没有任何条件。因此，如果它满足条件“first > last || s.charAt(first) != s.charAt(last)”，它将递归调用 isPalindrome，那么下一次调用也是如此，即使它命中了 else 。

我不知道什么是回文，也不知道问题的真正解决方案是什么，但这就是您收到堆栈溢出错误的原因。我怀疑您需要向 else 添加另一个条件，以便它停止递归调用自身。

Answer 4

在编写递归函数时，最好的方法通常是决定一个基本情况（：像“”是回文，尽管“a”也是回文......），然后设计一种方法来获取任何状态并移动它到基本情况。

因此，在回文的情况下，它的基本思想与以前相同，如果第一个字符和最后一个字符相同，则返回 true 并检查字符串的其余部分（从而更接近基本情况），如果它们是那么你就不会返回 false 。

您的堆栈溢出来自于在每种情况下调用 isPalindrome ，而不是当您需要继续解决问题时，不要忘记，如果两个字符意味着某些内容不是回文，则其余字符将变得无关紧要（因此不必递归）

Answer 5

您重新编码的版本有点奇怪，因为它在不需要时仍然使用循环。特别是，您的代码永远不会超出循环中的第一次迭代，因为在嵌入的 if-else 语句中，无论如何您都会返回结果，因此您的函数将始终退出在第一次迭代期间（除非根本没有迭代）。

递归应该通过识别基本情况来实现

1. ，即可以解决的最简单的情况
2. 将较大的问题重新表示为部分解决方案，然后是相同但较小的问题。

您正确处理的基本情况；任何长度等于或小于 1 的字符串自动成为回文。

下一步是考虑一个更大的问题，也许是一些字符串abcwewe....ba。我们怎样才能把这个问题分解成一个更简单的问题呢？我们知道，我们通常会通过从末尾开始，一对一地检查字母来检查某个东西是否是回文，但随后我们也意识到，每次检查字母时，我们只是再次重复相同的问题并解决同样的方式。

在我上面给出的字符串中，我们检查并验证第一个字母 a 与最后一个字母 a 相同，所以这是一种部分解决方案。现在我们最终得到的是较小的单词bcwewe....b，这又是同样的问题：这个新字符串也是回文吗？

因此，您现在要做的就是调用递归调用，但这次使用从第二个字符开始到倒数第二个字符的子字符串。您只需两行即可编写答案，如下所示：

public static boolean isPalindrome(String s) {
    if (s.length() <= 1) return true; // base case
    return s.charAt(0) == s.charAt(s.length()-1) && isPalin(s.substring(1,s.length()-1)); // recursive case
}

需要注意的一点是我使用的是短路 &&，因此如果第一个条件失败（检查第一个和最后一个字符），那么Java将不会调用递归。