Python :: recusedの再帰の理解

Question

私は再帰を理解しようとしています。

このコードでは、2つの数値の範囲の合計を計算しています。

def sum(lower, upper): 
    if lower > upper: 
     return 0 
    else: 
     return lower + sum(lower +1, upper) 

print(sum(11, 30)) 

各再帰呼び出しの値が格納されている場所を理解しようとしています。 したがって、lowerが12、upperが30の場合、この42がどこに格納されていますか？

おかげで、各再帰の ジェイソン

Answer 1

値はコールスタックに格納されています。

あなたはこのようなあなたの関数の逆アセンブリを表示することができます。

def my_sum(lower, upper): 
    if lower > upper: 
     return 0 
    else: 
     return lower + my_sum(lower +1, upper) 

import dis 
dis.dis(my_sum) 

あなたが得る：

2   0 LOAD_FAST    0 (lower) 
       2 LOAD_FAST    1 (upper) 
       4 COMPARE_OP    4 (>) 
       6 POP_JUMP_IF_FALSE  12 

    3   8 LOAD_CONST    1 (0) 
      10 RETURN_VALUE 

    5  >> 12 LOAD_FAST    0 (lower) 
      14 LOAD_GLOBAL    0 (my_sum) 
      16 LOAD_FAST    0 (lower) 
      18 LOAD_CONST    2 (1) 
      20 BINARY_ADD 
      22 LOAD_FAST    1 (upper) 
      24 CALL_FUNCTION   2 
      26 BINARY_ADD 
      28 RETURN_VALUE 
      30 LOAD_CONST    0 (None) 
      32 RETURN_VALUE 

LOAD_FASTルーチンは値をロードします関数スタックから。

これは一時的な値と同じです。

Answer 2

Pythonなどのほとんどの言語では、関数呼び出しにスタックという構造を使用しています。 stack data structureに精通していない場合は、そのことをお読みになることをお勧めします。それはあなたにスタックの仕事のしっかりとした理解を与えるでしょう。

私はthis tutorial for a detailed explanationをチェックアウトすることをお勧めします。

Answer 3

異なる命名規則に書かれたあなたのコード...

def compute(low, high): 
    if low > high: 
     return 0 
    else: 
     return low + compute(low+1, high) 

（低）、整数、および（高い）の整数が言ったよりも高くなっている別の整数を指定すると、このコードは、それらの間の合計を検索します2つの整数（再帰を介して）。

上記は再帰、つまり初期条件が満たされないたびにif low > high:になると30を返し、関数は再び呼び出され、1を加えて最終的に条件を満たすようにします。 （ローが10に等しい場合）再帰がで設定されます

をさらに例compute(6, 9)と - 低= 10、0が返された場合、以前に低い9であったので、この時点での発現return low + compute(low+1, high)は今、return 9 + 0あろう前の呼び出しから9を返したので、return 8 + 9、17を返します...私はあなたがポイントを得ると思う、このプロセスは、最初のreturn文まで発生します。それを、卑猥なものを巻き戻すことと考えて、それを最初の形に戻してください。

最終的に満たされる条件とインクリメンタルなreturn文がなければ、この関数は無限に同じ結果を返して、ifの条件が満たされないか、無限に1を低くすることに注意してください。

私はこれが再帰を少し明るくすることを望みます。

Answer 4

コールセンターのように考える。あなたが求めることができる範囲の数字の合計を彼らに伝えることを宣伝する人。

誰かに電話をかけて、12から30までの数字の合計を求めます。その人は「あまりにも複雑です」と思って、13から30の合計を求めるために同じコールセンターを呼び出します。その2人目の人はまだそれを直接行うことはできませんし、を再度と呼んで14から30の合計を求めます。最終的に、誰かが31から30の合計を求めて電話を受け取り、「Um、それは空の範囲なので、もちろん0」と返信します。それから、すべてが後退します。呼び出しスタックに関係するすべての人々は、答えを待っていましたが、今度は自分の結果を計算し、呼び出した人に報告します。したがって、回答は「30」（30 + 0）、「59」（29 + 30）、「87」（28 + 59）などとなります。最終的に人が呼び出され、12から30の質問があり、13から30の合計が387であるという回答が返されます。回答は12に追加され、「399」に返信されます。

このアナロジーには、自分の回答を待っている間にリクエストデータを頭に入れておく人がいます。これがコンピュータプログラミングで行われたときに、このデータはすべてどこに保存されますか？まあ、call stackに。これはスタックと呼ばれ、一度に1つずつ作成して一度に1つずつ取り除くようなスタックのように、コールは互いに重ねられ、逆の順序で終了します。そのコールセンターのように、コンピュータのコールスタックのサイズは限られています。コールセンターの人数よりも多い範囲について質問すると、最終的にコールセンターのすべての人があなたの要求に関与し、最後に呼び出された人には誰も話を聞かれません。この時点で、システムはやや破壊されます。コンピュータでは、これを「スタックオーバーフロー」と呼びます。このサイトのように。