遞歸與Java以意想不到的方式行爲

Question

我是一名學生，我一直在努力研究以下挑戰：在沒有使用substring方法的情況下在較大的字符串（乾草堆）中找到子字符串（指針），並且使用遞歸。遞歸是不是我的強項，但我已經做了以下工作：

public class Contains 
{ 
    public static void main(String[] args) 
    { 
     System.out.println(contains("Java programming", "ogr", false)); 
    } 

    public static boolean contains(String haystack, String needle, boolean doesContain) 
    { 
     if(haystack.length() < needle.length()) 
     { 
      return false; 
     } 
     else 
     { 
      for(int i = 0; i < needle.length(); i++) 
      { 
       if(haystack.charAt(i) != needle.charAt(i)) 
        if((i + 1) == needle.length()) 
         { 
          doesContain = false; 
          break; 
         } 
        else 
         break; 
       else 
        if((i + 1) == needle.length()) 
        { 
         doesContain = true; 
         break; 
        } 
        else 
         continue; 
      } 
      char[] haystackChar = haystack.toCharArray(); 
      char[] newCharArray = new char[(haystackChar.length - 1)]; 

      for(int j = 1; j < haystackChar.length; j++) 
      { 
       newCharArray[j - 1] = haystackChar[j]; 
      } 

      String newStr = new String(newCharArray); 

      if(doesContain == false) 
       contains(newStr, needle, doesContain); 
     } 
     return doesContain; 
    } 
} 

我知道這可能不是最好的或最優雅的解決方案，但我大多隻是試圖得到它的工作。我一直在Eclipse調試器中運行它，並且一切都按預期運行，直到在方法調用contain期間調用if(doesContain == false)，其中doesContain在for循環迭代過程中設置爲true。調試器顯示doesContain的值（正確）爲true，並且它顯示跳過if語句並退出else塊。然而，在此之後，它立即跳回到else塊，並且只調用遞歸調用contain，而不是返回doesContain。然後，它繼續遞歸工作，隨後失敗並返回false，因爲它現在正在搜索字符串的其餘部分，「針」不在其中。

我知道StackOverflow本身不是'家庭作業幫助'的位置，但是我爲學校之外的其他目的而編程，我很困惑它爲什麼會這樣做。有誰知道它爲什麼這樣做？我在這裏錯過了什麼嗎？

Answer 1

我看了你的代碼，並在eclipse中運行它自己。您將要研究的理論是堆疊如何在遞歸中工作。你的程序發現真實，然後離開堆棧，但到那時它已經多次重新發生。它返回true，但後來又返回了之前存儲的所有虛假變量。

如果您還有其他問題，請告訴我。

編輯 如果你真的有興趣進入先進遞歸我強烈推薦這個視頻：Java Recursion

嘿，我也沒必要去那麼遠，使其工作。你可以刪除doContain作爲參數，並將其設置爲一個靜態實例變量，併爲我工作。

public class Contains 
{ 

    private static boolean doesContain = false; 

    public static void main(String[] args) 
    { 
     System.out.println(contains("Java programming", "ogr")); 
    } 

    public static boolean contains(String haystack, String needle) 
    { 
     if(haystack.length() < needle.length()) 
     { 
      return false; 
     } 
     else 
     { 
      for(int i = 0; i < needle.length(); i++) 
      { 
       if(haystack.charAt(i) != needle.charAt(i)) 
        if((i + 1) == needle.length()) 
         { 
          doesContain = false; 
          break; 
         } 
        else 
         break; 
       else 
        if((i + 1) == needle.length()) 
        { 
         doesContain = true; 
         break; 
        } 
        else 
         continue; 
      } 
      char[] haystackChar = haystack.toCharArray(); 
      char[] newCharArray = new char[(haystackChar.length - 1)]; 

      for(int j = 1; j < haystackChar.length; j++) 
      { 
       newCharArray[j - 1] = haystackChar[j]; 
      } 

      String newStr = new String(newCharArray); 

      if(doesContain == false) 
       contains(newStr, needle); 
     } 
     return doesContain; 
    } 
} 

你有什麼非常接近的，但是通過將它作爲一個參數傳遞給每次你通過另一次遞歸進行存儲。這樣你只能返回你的最終價值。

Answer 2

要以您想要的方式在haystack中找到needle，您不需要使用遞歸。

剛剛從你的函數刪除下面的代碼行，它會工作得很好：

 char[] haystackChar = haystack.toCharArray(); 
     char[] newCharArray = new char[(haystackChar.length - 1)]; 

     for(int j = 1; j < haystackChar.length; j++) 
     { 
      newCharArray[j - 1] = haystackChar[j]; 
     } 

     String newStr = new String(newCharArray); 

     if(doesContain == false) 
      contains(newStr, needle, doesContain); 

Answer 3

我覺得你有點混淆自己與遞歸函數。傳遞給遞歸函數的變量之一是doesContain，但函數應該是返回字符串是否包含它！在行

 if(doesContain == false) 
      contains(newStr, needle, doesContain); 

如果子字符串包含針，contains的調用將返回。您需要獲取該值，並將其返回給調用堆棧。

希望這是有道理的。如果沒有，我會給你的代碼，所以你可以自己弄明白：

public static boolean contains(String haystack, String needle) 
{ 
    if(haystack.length() < needle.length()) 
    { 
     return false; 
    } 
    else 
    { 
     boolean doesContain=false; 
     for(int i = 0; i < needle.length(); i++) 
     { 
      if(haystack.charAt(i) != needle.charAt(i)) 
       if((i + 1) == needle.length()) 
        { 
         doesContain = false; 
         break; 
        } 
       else 
        break; 
      else 
       if((i + 1) == needle.length()) 
       { 
        doesContain = true; 
        break; 
       } 
       else 
        continue; 
     } 
     char[] haystackChar = haystack.toCharArray(); 
     char[] newCharArray = new char[(haystackChar.length - 1)]; 

     for(int j = 1; j < haystackChar.length; j++) 
     { 
      newCharArray[j - 1] = haystackChar[j]; 
     } 

     String newStr = new String(newCharArray); 

     if(doesContain == false) 
      return contains(newStr, needle); 
     else 
      return true; 
    } 
}