7

私はいくつかの入門的な再帰の問題に取り組んでおり、答えてもらいたい明確な質問があります。私が持っている最も厄介な質問は、この再帰が以下の解決された問題でどのように機能しているかということです。

問題を解決したにもかかわらず、再帰呼び出しがどのように文字列の内部に入るのか理解していません。コードを見るだけで、このメソッドは、指定された文字列の両端の2つの文字のみをチェックし、残りの文字はチェックしないように見えます。私の教科書は、基本的に、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"));
}
}
4

2 に答える 2

12

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

最後の呼び出しの戻り値は、一番上まで伝播します。

再帰では、画像が常に役立ちます。コールスタックを図として描くために最善を尽くしてください。これにより、より複雑な再帰を視覚化できるため、よりよく理解できるようになります。これは単純な「線形」再帰ですが、最終的には再帰のような「ツリー」に直面します。

これは、この正確な問題をよりよく視覚化するための図です。

回文再帰

于 2012-02-02T05:22:19.487 に答える
9

回文について考えてみてください。

risetovotesir

これは実際には、パリンドロームv（1文字の文字列は常にパリンドロームであり、空の文字列も同様です）から始めて、同じ文字を前後に追加することで作成できます。

      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'.

その再帰関数によって使用されるプロセスは反対方向であり、文字列をビットごとに分解します。それが実際に回文であるかどうかを検出します。

  • 最初と最後の文字は同じです。と
  • 弦の内側（これら2つが削除された後）は回文です。

したがって、コードは次のように記述できます。

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.
于 2012-02-02T05:23:45.497 に答える