再帰的パルミトム関数はどのように機能しますか？

Question

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

問題を解決したにもかかわらず、私は再帰呼び出しが文字列の内部にどのように入るのか理解できません。コードを見るだけで、このメソッドは指定された文字列の両端の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")); 
} 
} 

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 

最後の呼び出しの戻り値はすべての方法トップに伝播します。

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

ここでは、より良い視覚化するため、この正確な問題を示している絵です：回文の

Answer 2

思う：

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つは削除された後）は回文文字列です。したがって、コードのように書くことができる

：peed deepの文字列を使用して

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

、異なるレベルがある：あるいは

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.