予期せぬ方法で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へのメソッド呼び出し中にを呼び出すまではすべて期待通りに機能していましたが、forループの繰り返し中にdoesContainがtrueに設定されています。デバッガはdoesContainの値が（正しく）真であることを示しており、if文をスキップしてelseブロックを終了することを示しています。しかし、その直後に、それはelseブロックにジャンプし、doesContainの代わりにcontainへの再帰呼び出しを呼び出します。次に、 "針"が配置されていない文字列の残りの部分を検索しているため、再帰的に動作し続け、失敗してfalseを返します。

私はStackOverflow自体が「宿題の手助け」の場所ではないことを知っていますが、私は学校以外の目的でプログラムしています。なぜこのように振舞っているのか非常に困惑しています。誰がなぜこれをやっているのか知っていますか？私はここに何かを逃していますか

Answer 1

私はあなたのコードを見て、自分自身をeclipseで走らせました。調べてみたい理論は、スタッキングがどのように再帰で動作するかです。あなたのプログラムは真実を発見してからスタックを離れるが、その時点までに何度か再発した。それは真実を返しましたが、それ以前に格納されていたすべての偽変数も返すようになりました。

さらにご質問がありましたら、お知らせください。

EDIT あなたが進んで再帰に入る本当に興味があるなら、私は非常にこのビデオをお勧めします：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

私はあなたがソートの再帰関数を自分で混乱していると思います。再帰関数に渡される変数の1つはdoesContainですが、関数にはが返されます。戻り値はです。行内

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

部分文字列に針が含まれている場合は、を呼び出すと戻ります。その値を取って、コールスタックに戻す必要があります。

うまくいけばそれは意味をなさないでしょう。そうでなければ、私はあなた自身でそれを理解することができるようにコードを与えます：

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; 
    } 
}