2

リストの長さを計算しようとしています。cmdで実行すると、次のようになります。

RuntimeError：比較して最大再帰深度を超えました

私のコードには何も問題はないと思います。

def len_recursive(list):
    if list == []:
        return 0
    else:
        return 1 + len_recursive(list[1:])
4

6 に答える 6

3

深すぎないと予測できる場合を除き、再帰を使用しないでください。Python では、再帰の深さに非常に小さな制限があります。

再帰を主張する場合、効率的な方法は次のとおりです。

def len_recursive(lst):
    if not lst:
        return 0
    return 1 + len_recursive(lst[1::2]) + len_recursive(lst[2::2])
于 2013-01-14T20:59:24.533 に答える
2

他の人が説明したように、関数には 2 つの問題があります。

  1. 末尾再帰ではないため、 のリストしか処理できませんsys.getrecursionlimit。
  2. 末尾再帰であったとしても、Python は末尾再帰の最適化を行いません。

1つ目は簡単に解決できます。たとえば、Óscar López の回答を参照してください。

2 つ目は解決が困難ですが、不可能ではありません。1 つのアプローチは、サブルーチンの代わりにコルーチン (ジェネレーター上に構築) を使用することです。もう 1 つの方法は、関数を実際に再帰的に呼び出すのではなく、再帰的な結果を含む関数を返し、結果を適用するドライバーを使用することです。後者を実装する方法の例については、Paul Butler によるPython の末尾再帰を参照してください。

Paul Butler のtail_rec関数から始めます。

def tail_rec(fun):
    def tail(fun):
        a = fun
        while callable(a):
            a = a()
        return a
    return (lambda x: tail(fun(x)))

彼には 2 つの相互再帰関数があるため、これは彼の場合のデコレーターとしては機能しません。しかし、あなたの場合、それは問題ではありません。したがって、オスカー・ロペスのバージョンを使用すると、次のようになります。

@tail_rec
def tail_len(lst):
    def loop(lst, acc):
        if not lst:
            return acc
        return lambda: loop(lst[1:], acc + 1)
    return lambda: loop(lst, 0)

そしていま：

>>> print tail_len(range(10000))
10000

多田。

実際にこれを使用したい場合はtail_rec、より優れたデコレータを作成することをお勧めします。

def tail_rec(fun):
    def tail(fun):
        a = fun
        while callable(a):
            a = a()
        return a
    return functools.update_wrapper(lambda x: tail(fun(x)), fun)
于 2013-01-14T21:13:54.230 に答える
2

Python の再帰の深さは限られていますが、この投稿に示されているように増やすことができます。Python がテール コールの最適化をサポートしている場合、このソリューションは任意の長さのリストに対して機能します。

def len_recursive(lst):
    def loop(lst, acc):
        if not lst:
            return acc
        return loop(lst[1:], acc + 1)
    return loop(lst, 0)

しかし、そのままでは、より短いリストを使用するか、許容される最大再帰深度を増やす必要があります。

len()もちろん、この実装を (組み込み関数を使用する代わりに) 実生活で使用する人はいないでしょう。 @pokeの答え。

于 2013-01-14T21:01:42.803 に答える
1

紙の束を使用してこれを実行していると想像してください。持っているシートの数を数えたいとします。誰かがあなたに 10 枚のシートを渡した場合、最初のシートを取り、それをテーブルに置き、次のシートをつかみ、最初のシートの隣に置きます。これを 10 回行うと、机はかなりいっぱいになりますが、各シートを準備しました。次に、すべてのページのカウントを開始し、0 + 1 + 1 + ... => 10 と数えながらリサイクルします。これはページをカウントする最良の方法ではありませんが、再帰的なアプローチと python の実装を反映しています。

これは、少数のページで機能します。誰かがあなたに 10000 枚のシートを渡してくれると想像してみてください。すぐに、机の上に各ページを配置するスペースがなくなります。これは本質的に、エラー メッセージが伝えていることです。

最大再帰深度は、テーブルが保持できる「シートの数」です。Python を呼び出すたびに、「1 + 再帰呼び出しの結果」を保持する必要があるため、すべてのページがレイアウトされたときに戻ってカウントアップできます。残念ながら、最後のカウントアップが発生する前に、スペースが不足しています。

これを再帰的に学習したい場合は、適切な状況で len() を使用したいので、小さなリストを使用するだけで、25 で十分です。

一部のシステムは、テール コールをサポートしている場合、大きなリストに対してこれを処理できます。

于 2013-01-14T21:06:51.593 に答える
1

例外メッセージは、メソッドが再帰的に呼び出される頻度が高すぎることを意味するため、リストが長すぎてそのように要素を再帰的にカウントできない可能性があります。ただし、反復ソリューションを使用して簡単に実行できます。

def len_iterative(lst):
    length = 0
    while lst:
        length += 1
        lst = lst[1:]
    return length

lst[1:]リストのコピーを作成し続けるため、これはまだひどい解決策である可能性が非常に高いことに注意してください。したがって、len(lst) + 1リスト インスタンス (長さ0～len(lst)) になります。ビルトインをlen直接使用するのがおそらく最良のアイデアですが、それは割り当てだったと思います。

于 2013-01-14T21:01:21.557 に答える
0

Python は末尾再帰呼び出しを最適化していないため、そのような再帰アルゴリズムを使用することはお勧めできません。sys.setrecursionlimit()でスタックを微調整できますが、それでも良い考えではありません。

于 2013-01-14T20:57:56.083 に答える