再帰関数の中断？

Question

私はmain関数への再帰的なループを抜け出す方法を知っています。私は単純な回文運動をしようとしています。この関数は "redivider"に対してTrueを返さなければなりませんが、Trueがis_pal（）に渡され、関数は中断していません。 True/Falseを追跡するためにis_palに2番目の変数を追加するだけでは不十分ですが、この再帰的ループから抜け出す正しい方法は何ですか？ありがとう。

def first(word): 
    return word[0] 

def last(word): 
    return word[-1] 

def middle(word): 
    return word[1:-1] 

def is_pal(str):  
    if len(str) == 1: 
     return True 

    if first(str) == last(str) and len(str) > 1: 
     is_pal(middle(str)) 

print is_pal("redivider") 

Answer 1

def is_pal(str):  
    if len(str) <= 1: 
     return True 

    if first(str) == last(str): 
     return is_pal(middle(str)) 
    else: 
     return False 

その方法は、Falseが返されます。もしそれが最後まで終わっていれば、真が返されます。私はまた冗長な条件を削除し、偶数長の回文のエッジケースをチェックしました。

Answer 2

あなたは、再帰呼び出しの結果を返す必要があり、あなたは他のパスが取られていない場合もreturn Falseを追加する必要があります。

def is_pal(str):  
    if len(str) == 1: 
     return True 

    if first(str) == last(str) and len(str) > 1: 
     return is_pal(middle(str)) 

    return False 

Answer 3

あなたには返品がありません。また、変数名としてstrを使用しないでください。最後のことは、最初と最後の関数の名前を少し良くすることができます。それらが一致しない場合

def first_letter(word): 
    return word[0] 

def last_letter(word): 
    return word[-1] 

def middle(word): 
    return word[1:-1] 

def is_pal(word):  
    if len(word) == 1: 
     return True 

    if first_letter(word) == last_letter(word) and len(word) > 1: 
     return is_pal(middle(word)) 

print is_pal("redivider") 

Answer 4

一致しない場合はFalseを返し、return文を追加する必要があります。あなたは再帰関数の外ではない "ブレーク" を行う

def is_pal(str): 
    if len(str) in [0, 1]: 
     return True 
    if first(str) == last(str) and len(str) > 1: 
     return is_pal(middle(str)) 
    else : 
     return False 

Answer 5

：また、あなたはおそらく、LEN（文字列）== 0とlen（STR）== 1に対してチェックしたくなるでしょう。そうしようとすると、間違った方法を考えていると言います。現在のところ、再帰呼び出しは出力を無視しているため、再帰は無意味です。 is_pal(middle(str))が返すものは、関数の戻り値には何の影響も与えません。

再帰的アルゴリズムは、問題をより小さな問題に分解し、小さな問題を再帰的に取得し、小さなソリューションを使用してより大きな問題を解決することによって、入力問題を解決します。内部コールから「中断」しないで、ソリューションレベルを1つ戻します。あなたは内線通話か最上位通話かを知る必要があることを知らない（または知る必要がある）。どちらの場合でも、あなたの関数は同じことをしなければなりません：引数が回文であればTrueを返し、そうでなければFalseを返します。

あなたが実装しようとしているアルゴリズムは、基本的にはこれです：

1. 文字列の長さが1である場合、最初の文字が同じであれば、それは、回文（真を返す）
2. そうでないのです最後の文字である場合、中間文字が回文であれば入力は回文文字列である。

だから、これが何を意味するのか、あなたが最初と最後の文字が同じである確立したら、答えはが正確「への答えと同じが途中あるさ「回文は私の入力である」ということですキャラクターはパリンドロームです "。あなたはあなたの契約を履行するためにその答えを返す必要があります。したがって、再帰呼び出しはis_pal(middle(str))ではなく、return is_pal(middle(str))にする必要があります。これがトップレベルのコールだった場合、これが答えです。このがのトップレベルのコールでなかった場合、外側の呼び出しは外側の問題（この場合は単純にそれを返すことで）への答えを解決するためにこの答えが必要になります。

---

Btwでは、アルゴリズムにもいくつかの問題があります。あなたはFalseを返すことはありませんので、答えはFalse（このケースでは、あなたが最初と最後の文字が一致しない場合は、誤って関数の最後から落ちることでNoneを返すために起こる、とNone意志になることはありません

1. おそらくFalseのためのスタンドとしてはありますが、それでも実際にはは正しくありません。）です。
2. 文字列の長さは、空の文字列が又はに渡される場合等しい最初と最後の文字のすべての対が取り除かれた後も長さのパリンドロームが渡された場合に起こるゼロなく1（ある場合）、正しい答えが返されず、実際には空の文字列の最初と最後の文字を取得しようとすると、例外が発生します。