23

main関数への再帰ループから抜け出す方法を考えています。簡単な回文運動をしようとしています。関数はTrueを返す必要があります"redivider"が、return Trueはに渡されてis_pal()おり、関数は壊れていません。True / Falseを追跡するために2番目の変数を追加するis_pal以外に、この再帰ループから抜け出すための適切な方法は何ですか？

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")
4

6 に答える 6

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

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

そうすれば、それらが一致しない場合、False返されます。最後まで到達すると、Trueが返されます。また、冗長な条件付きを排除し、偶数の長さの回文のエッジケースをチェックしました。

于 2012-05-11T02:18:20.863 に答える
17

再帰関数から「抜け出す」ことはありません。そうしようとすると、あなたはそれらについて間違った方法で考えていると言います。現在、再帰呼び出しは出力を無視しています。これは、再帰が無意味であることを意味します。戻りis_pal(middle(str))値は、関数の戻り値には影響しません。

再帰的アルゴリズムは、問題をより小さな問題に分解し、より小さな問題の解を再帰的に取得し、より小さな解を使用してより大きな問題の正しい解を構築することにより、入力問題を解決します。内部呼び出しから「抜け出す」のではなく、ソリューションを1レベル戻します。内線通話かトップレベル通話かはわかりません（または知る必要があります）。どちらの場合でも、関数は同じことを行う必要があります。True引数が回文である場合は戻り、Falseそうでない場合は戻ります。

実装しようとしているアルゴリズムは基本的に次のとおりです。

  1. 文字列の長さが1の場合、それは回文です（return True）
  2. それ以外の場合、最初の文字が最後の文字と同じである場合、中央の文字が回文であれば、入力は回文になります。

つまり、最初と最後の文字が同じであることを確認すると、「私の入力は回文です」に対する答えは、「中間の文字は回文です」に対する答えとまったく同じになります。契約を履行するには、その回答を返す必要があります。したがって、再帰呼び出しはreturn is_pal(middle(str))単なるではなくする必要がありますis_pal(middle(str))。これがトップレベルの呼び出しだった場合、それが答えです。これがトップレベルの呼び出しではなかった場合、外部の呼び出しは、外部の問題に対する答えを見つけるためにこの答えを必要とします（この場合、単にそれを返すことによって）。

ところで、あなたのアルゴリズムには他にもいくつか問題があります。

  1. 戻ることはないFalseので、答えは決してありません（この場合、最初と最後の文字が一致しない場合、関数の最後から落ちFalseて誤って戻ることがあり、ほとんどの場合、代用として機能します、しかしそれはまだ実際には正しくありません）。NoneNoneFalse

  2. 文字列の長さが1ではなくゼロの場合（空の文字列が渡された場合、または同じ長さの最初と最後の文字のすべてのペアが削除された後に同じ長さの回文が渡された場合に発生します）、正解を返します。実際、空の文字列の最初と最後の文字を取得しようとすると、例外が発生します。

于 2012-05-11T02:31:08.640 に答える
17

Pythonで再帰関数から抜け出す1つの方法は、例外をスローし、それをトップレベルでキャッチすることです。これは再帰について考える正しい方法ではないと言う人もいますが、それで仕事は終わります。さらに、タスクが配列/配列の配列/ ndarrayなどの「問題のある」要素を特定することである場合、グローバルソリューションが特定された後、アルゴリズムの続行を停止するため、ブレーク手法が便利です。

def solve_problem(lst):
    def solve_rec(l):
        '''has impl. that may throw an exception '''
    try:
        solve_rec(lst)
        return True
    except:
        return False
于 2018-03-26T15:18:21.070 に答える
2

関数を使用して結果を印刷した後、プログラムを終了できexit()ます。

それは良い習慣ではないかもしれませんが、それはあなたが探しているものかもしれません。

于 2019-07-07T07:43:30.703 に答える
0

あなたはリターンを逃しています。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")
于 2012-05-11T02:17:19.613 に答える
0

一致しない場合はFalseを返し、returnステートメントを追加する必要があります。また、おそらくlen（str）== 0およびlen（str）==1に対してチェックする必要があります。

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
于 2012-05-11T02:18:32.737 に答える