2

数時間前にPythonでの再帰に関するビデオを見て、ビデオで作成されたプログラムを再作成したので、私のバージョンのPythonで動作しました。コードは機能しますが、完全には理解できない部分と、それが何をしているのかが少しわかりません。

def lower(s):
    s = s.lower()
    return s

def isPal(s):
    if len(s) <= 1:
        return True
    else:
        return s[0] == s[-1] and isPal(s[1:-1])

def isPalindrome(s):
    if isPal(lower(s)) == True:
        print("{0} is a palindrome".format(s))

私が問題を抱えている部分は、

return s[0] == s[-1] and isPal(s[1:-1])

私が疑問に思っているのは、なぜそれらが返されるのか、またなぜ s[0:-1] ではなく s[1:-1] なのかということです。それらを共有します。前もって感謝します。

4

5 に答える 5

5

なぜ s[0:-1] ではなく s[1:-1] なのか

s[1:-1]s最初と最後の要素が切り取られて返されます。最後の要素だけが切り取られてs[0:-1]返されます。s

回文のプロパティ (回文の場合) を保持するには、両端を切り取る必要があります。これは、中央から等距離にある要素が同一であるということです。一方の端だけを切り落とすと、中央が移動し、(一般的なケースでは) その不変条件が破壊されます。

これは自己再帰の核心です: 何かを実行してから、同じプロパティを持つより単純なケースをデリゲートします。

s[0] == s[-1] と isPal(s[1:-1]) を返す理由

これが返されるのは、最初と最後の要素に (上記のように) 回文プロパティがあり、次の「レイヤー」にもそのプロパティがあることを最初に確認するためです。外側のペアが等しくない場合、それは回文ではなく、False返されます。true の場合、再帰的な手順が実行され、それが True の場合、式全体が を返しますTrue。

于 2013-09-19T15:15:27.667 に答える
3

「カヤック」という言葉があると想像してください

プログラムは次の場合に表示されます。

'k' == 'k'はいの場合、プログラムは関数を次のように呼び出します。'aya'

次に、プログラムは'a' == 'a'、はいの場合、プログラムが関数を呼び出すかどうかを調べます'y'

それならたった一文字だからプログラムは返すTrue

于 2013-09-19T15:16:54.513 に答える
3

これが魔法が起こる場所です：

return (s[0] == s[-1]) and isPal(s[1:-1])

（括弧を追加したので、演算子の優先順位は完全に明確です）。Python の AND ステートメントは最初の引数を評価し、それがTrueである場合にのみ 2 番目の引数を評価することを知っておくことが重要です。最初が だった場合、を呼び出さずにすぐにFalse戻ります。これは短絡評価として知られています。Blenderは、彼の投稿でこれの良い例を示しています。FalseisPal()

s[0]は文字列の最初の文字、 は文字列s[-1]の最後の文字です。まず、最初と最後の文字が同じかどうかを確認します。それらが異なる場合、文字列が回文になる方法はありません。それらが同じ場合は、それらを無視して文字列の内側に移動できます。

s[1:-1]最初と最後の文字を切り取り、それをisPal()関数に渡します。これはたまたま現在使用している関数です。これを再帰と呼びます。関数に再度「再帰」すると、新しいスタックが作成され、新しいローカル変数が作成され、関数への入力引数は前の呼び出しのものとは異なります。

最初と最後の文字をチェックし続け、単語の中心まで再帰します。この時点で、1 文字または 0 文字が残っており、そこまで到達した場合は、回文が見つかったことがわかります。

この最終的な内部から戻るとisPal()、戻り値への呼び出し (True回文が見つかった場合) が呼び出し元の関数に渡され、呼び出し元の関数にisPal()返されます。最初の呼び出し元に結果を返します。このプロセスを「スタックの展開」と呼びます。

次に例を示します。

s = 'racecar'
s[0] == s[-1] # True - both letters are 'r'
s = s[1:-1]   # s becomes 'aceca'
s[0] == s[-1] # True - both letters are 'a'
s = s[1:-1]   # s becomes 'cec'
s[0] == s[-1] # True - both letters are 'c'
s = s[1:-1]   # s becomes 'e'
len(s) <= 1   # This statement is now True, so the stack will start to unwind

視覚的には、呼び出しは次のようになります。

'racecar' ---------
                  |
                  V    'aceca'
 True <--- isPal(   ) ----
             ^           |
        True |           V     'cec'
             ---- isPal(   ) ----
                    ^           |
               True |           V     'e'
                    ---- isPal(   ) ----
                           ^           |
                      True |           V
                           ---- isPal(   )  # We get all the way down here,
                                            # and then we start to return

回文がない場合は、次のようになります。

'race2car' --------
                  |
                  V    'ace2ca'
False <--- isPal(   ) ----
             ^           |
       False |           V     'ce2c'
             ---- isPal(   ) ----
                    ^           |
              False |           V     'e2'
                    ---- isPal(   ) ----
                           ^           |
                     False |           V
                           ---- isPal(   )  # Here the outer two letters
                                            # do not match, so we start to
                                            # return False
于 2013-09-19T15:24:33.900 に答える
0

そのステップでは短絡論理積を使用するため、実際には次のように動作します。

if s[0] != s[-1]:
    return False
else:
    return isPal(s[1:-1])

についてs[1:-1]は、最初と最後の文字を と比較するため、最初と最後の文字をs[0] != s[-1]削除s[1:-1]して、結果の文字列を に戻しますisPal。

于 2013-09-19T15:13:06.030 に答える