3

私の同僚が開発した次の再帰関数を考えてみましょう。

def a():
    try:
        a()
    except:
        a()

これを実行すると、(Python 2.7) インタープリターがハングします。再帰の深さ (たとえば N) がヒットするとすぐに がスローRuntimeErrorされ、(N-1) 番目のexceptブロックにRuntimeErrorジャンプし、別の を取得し、(N-2) 番目にジャンプするexceptなどと予想していたので、これには驚きました。

そこで、デバッグ用に関数を少し肉付けしました。

y = 10000

def a(x=0):
  global y
  if y:
    y -= 1
    try:
      print "T: %d" % x
      a(x+1)
    except RuntimeError:
      print "E: %d" % x
      a(x+1)

ある時点で関数を強制的に終了させるためにあるだけです。yそれ以外の場合、関数の動作が変わるとは思いません。私のインタープリター (再帰制限が 1000 の場合) では、呼び出しa()によって次のようなシーケンスが生成されます。

T: 998
E: 998
E: 997
T: 998
E: 998
E: 990
T: 991
T: 992
T: 993
T: 994
T: 995
T: 996
T: 997
T: 998
E: 998
E: 997
T: 998
E: 998
E: 996

より長いシーケンスを見ると、そこから実際のパターンを識別することはできません (ただし、それをプロットしようとはしませんでした)。再帰の深さに達するたびに M がインクリメントされる N 呼び出しと NM 呼び出しの間でスタックが往復しているのではないかと考えました。しかし、どれだけ大きいかは問題ではないようですy。スタックは、約 8 回を超える呼び出しを巻き戻すことはありません。

では、Python の内部では実際に何が行われているのでしょうか? この行動にパターンはありますか？

4

1 に答える 1

5

これは興味深い問題です。期待される動作が現実的ではない理由は、RuntimeError が発生したときに、問題のある「再帰的すぎる」スタック フレームが閉じられているようです。これは、例外が次に低いスタック フレームでキャッチされると、そのフレームは制限に達するまで再び上方に再帰できることを意味します。

つまり、再帰の深さ (N など) に達するとすぐに、次のようになると予想していました。

  1. RuntimeError をスローする
  2. (N-1)番目以外のブロックにジャンプ
  3. 別の RuntimeError を取得する
  4. を除いて (N-2) 番目にジャンプ
  5. 等

実際に何が起こるかは次のとおりです。

  1. RuntimeError をスローする
  2. (N-1)番目以外のブロックにジャンプ
  3. N までずっと再帰する
  4. 別の RuntimeError を取得する
  5. を除いて (N-2) 番目にジャンプ
  6. N までずっと再帰する
  7. 等

さらに、それぞれの「N までずっと再帰する」は、例外-再帰-例外の同じインクリメンタル プロセスを使用してアンワインドする必要があります。したがって、予想よりもはるかに多くの再帰があります。

x出力で確認するのが難しい理由は、元のコードが同じ値を持つ複数の呼び出しを区別しないためです。1001 回目の呼び出しが行われると、1000 回目の呼び出しで例外が発生し、999 回目の呼び出しに制御が戻ります。この呼び出しは、 を使用して別の呼び出しを行いx=1000、特定の値を持つ呼び出しの並列「系列」を作成しxます。

この動作は、元のコードを次のように変更することで確認できます。

y = 2000

def a(x=0, t=''):
    print(t + "In a({0})".format(x))
    global y
    if y:
        y -= 1
        try:
            a(x+1, t)
        except RuntimeError:
            print(t + "*** E: %d" % x)
            a(x+1, t+'\t')

これによりインデントが追加されるため、どの呼び出しが他のどの呼び出しの中に入ったかを確認できます。結果の出力のサンプルは次のとおりです。

In a(986)
In a(987)
*** E: 987
*** E: 986
    In a(987)
    *** E: 987
*** E: 985
    In a(986)
    In a(987)
    *** E: 987
    *** E: 986
        In a(987)
        *** E: 987
*** E: 984
    In a(985)
    In a(986)
    In a(987)
    *** E: 987
    *** E: 986
        In a(987)
        *** E: 987
    *** E: 985
        In a(986)
        In a(987)
        *** E: 987
        *** E: 986
            In a(987)
            *** E: 987
*** E: 983
    In a(984)
    In a(985)
    In a(986)
    In a(987)
    *** E: 987
    *** E: 986
        In a(987)
        *** E: 987
    *** E: 985
        In a(986)
        In a(987)
        *** E: 987
        *** E: 986
            In a(987)
            *** E: 987
    *** E: 984
        In a(985)
        In a(986)
        In a(987)
        *** E: 987
        *** E: 986
            In a(987)
            *** E: 987
        *** E: 985
            In a(986)
            In a(987)
            *** E: 987
            *** E: 986
                In a(987)
                *** E: 987

(何らかの理由で、私のインタープリターは 1000 回目の呼び出しではなく 988 回目の呼び出しで最初にエラーを生成しますが、これはあまり変わりません。) すべてのエラーは、階層内の 1 つのステップだけを元に戻し、フォレスト全体を許可することがわかります。 「ネストされた再帰」が発生します。

これにより、コール数が指数関数的に増加します。実際、再帰制限を小さな値に設定してこれをテストし (20 と 25 を試しました)、再帰が最終的に終了することを確認しました。私のシステムでは、2**(R-12)合計呼び出し後に終了します。ここで、R は再帰制限です。(12 は、最初の例外が N=988 で発生したときの私の例で見られるように、再帰制限と最初の例外が実際に発生した数との差です。おそらく、これらの 12 フレームは何らかの方法で内部的に「使用」されています。私の通訳）

インタプリタがハングしているように見えるのは当然のことです。制限が 1000 であると、完了するのに宇宙の年齢よりもはるかに時間がかかるためです。

于 2013-09-04T04:07:20.967 に答える