3

Python は初めてで、再帰を理解しようとしています。MITイントロコースの問題セットの問題1のように、再帰関数を使用して、文字列「キー」が文字列「ターゲット」で見つかった回数を出力するプログラムを作成しようとしています。関数がどのように実行されるかを把握しようとして問題が発生しています。ドキュメントといくつかのチュートリアルを読みましたが、このコードを修正するのに役立つ再帰をよりよく理解する方法についてのヒントはありますか?

from string import *

def countR(target,key):
    numb = 0
    if target.find(key) == -1:
        print numb
    else:
        numb +=1
        return countR(target[find(target,key):],key)

countR('ajdkhkfjsfkajslfajlfjsaiflaskfal','a')
4

4 に答える 4

8

再帰によって、問題を独立して解決できる小さなサブ問題に分割し、それらのソリューションを組み合わせて最終的なソリューションを取得する必要があります。

あなたの場合、タスクを2つの部分に分割できます。最初に出現した場所（場合）を確認keyし、残りを再帰的にカウントします。

そこにキーはありますか:
- いいえ: 0 を返します
。 - はい: 削除して、キーの数が 1 +残りkeyの数であると言います。key

コード内:

def countR(target,key):
    if target.find(key) == -1:
        return 0
    else:
        return 1+ countR(target[target.find(key)+len(key):],key)

編集:
次のコードは、目的の結果を出力します。

print(countR('ajdkhkfjsfkajslfajlfjsaiflaskfal','a'))
于 2012-08-05T23:03:42.590 に答える
1

これは再帰の仕組みではありません。numb役に立たない - 再帰を入力するたびにnumb0 として再作成されるため、0 または 1 しか指定できません - 求める実際の結果は決してありません。

再帰は、小さな問題の答えを見つけ、それを使って大きな問題を解決することで機能します。この場合、最初の出現を含まない文字列内のキーの出現回数を見つけ、それに 1 を追加する必要があります。

また、見つけたばかりの文字列が再び表示されないように、実際にスライスを進める必要があります。

from string import *

def countR(target,key):
    if target.find(key) == -1:
        return 0
    else:
        return 1+countR(target[target.find(key)+len(key):],key)

print(countR('ajdkhkfjsfkajslfajlfjsaiflaskfal','a'))
于 2012-08-05T23:07:11.413 に答える
1

私が見たほとんどの再帰関数は、より高いフレームが構築される興味深い値を返すことを強調しています。あなたの関数はそれを行いません。おそらくそれがあなたを混乱させている理由です。これは、整数の階乗を与える再帰関数です。

def factorial(n):
    """return the factorial of any positive integer n"""
    if n > 1:
        return n * factorial(n - 1)
    else:
        return 1 # Cheating a little bit by ignoring illegal values of n

上記の関数は、私が「通常の」種類の再帰と呼んでいるものを示しています。つまり、内側のフレームによって返された値が外側のフレームによって操作されます。

あなたの機能は、次の点で少し変わっています。

  1. 常に値を返すとは限りません。
  2. 外側のフレームは、内側のフレームの戻り値に対して何もしません。

より従来の再帰パターンに従うようにリファクタリングできるかどうか見てみましょう。（スポイラー構文として書かれているので、最初に自分で取得できるかどうかを確認できます）：

def countR(target,key): idx = target.find(key)` if idx > -1: return 1 + countR(target[idx + 1:], key) else: return 0

ここでは、ターゲットが見つかるたびにcountR追加し、残りの文字列を繰り返します。1一致が見つからない場合でも値を返しますが、次の 2 つの重要なことを行います。

  1. 外枠に追加しても値は変わりません。
  2. それ以上再発しません。

(わかりました。重要なことは、実行しないことです。全体像がわかります。)

メタ/編集:このメタ記事にもかかわらず、スポイラー テキストのコードを実際に適切にフォーマットすることは明らかに不可能です。そのため、その機能が修正されるまで、または永久にフォーマットされていないままにしておきます。

于 2012-08-05T23:19:15.613 に答える
0

キーがターゲットに見つからない場合は、numb を出力します。そうでない場合は、見つかった出現箇所の後に始​​まる新しい文字列を作成し (先頭を切り取ります)、そこから検索を続けます。

于 2012-08-05T23:03:35.590 に答える