python - return 関数は再帰でどのように機能しますか?

Question

return ステートメントが再帰関数 (python) でどのように機能するかわかりません。再帰関数で「もの」を返すときに、何が起こっているのかについて、いくつかの基本的な例を教えてください。

Answer 1

インデントを使用して再帰呼び出しを表す簡単な例を次に示します (スタックの深さを測定することにより)。

>>> import inspect
>>> def factorial(n):
...     print('{:{}}factorial({})'.format('', len(inspect.stack()), n))
...     retval = 1 if n == 1 else n * factorial(n-1)
...     print('{:{}}return {}'.format('', len(inspect.stack()), retval))
...     return retval
... 
>>> factorial(5)
  factorial(5)
   factorial(4)
    factorial(3)
     factorial(2)
      factorial(1)
      return 1
     return 2
    return 6
   return 24
  return 120
120

Answer 2

再帰は、最も単純な形式が達成されるまで、関数がより単純な形式で自分自身を呼び出す洗練されたプログラミング スタイルです。

この最も単純な形式は「基本ケース」と呼ばれます (次の例では、基本ケースはif n == 1: return 1階乗の場合、到達する必要がある最も単純なケースであるためです)。これは、入力が可能な限り単純であるかどうかを確認するためのテストです。州。

再帰関数の他の部分は、関数をさらに単純化する「再帰ケース」です (次の例でn * factorial(n-1)は、 を使用して関数を単純化しているため、再帰ケースですn-1)。

シンプルで再帰的な階乗関数:

def factorial(n): # only works for positive numbers
    if n == 1: return 1 # base case
    return n * factorial(n-1) # recursive case; only executed if the above is not
                              # executed because 'return' stops a function

階乗は、 までのすべての数値の乗算ですn。

これを分解してみましょう: factorial(4):

1. n1ですか？いいえ、そうですreturn n * factorial(n-1)
2. 4 * factorial(4-1)=4 * factorial(3)
3. n1ですか？いいえ、そうですreturn n * factorial(n-1)
4. 3 * factorial(3-1)=3 * factorial(2)
5. n1ですか？いいえ、そうですreturn n * factorial(n-1)
6. 2 * factorial(2-1)=2 * factorial(1)
7. n1ですか？はい、そうですreturn 1

それでは、呼び出しを追跡しましょう。

ステップ 1、3、5 は単なるチェックであるため、実際には何も返されません。

• ステップ2：factorial(4) = 4 * factorial(3)
• ステップ 4:factorial(3) = 3 * factorial(2)
• ステップ 6:factorial(2) = 2 * factorial(1)
• ステップ 7: factorial(1) = 1.

したがって、returnステートメントをトレースすると、1 * 2 * 3 * 4 = 24 となり、これは 4 の階乗です。

Answer 3

関数が再帰呼び出しを行うと、呼び出された関数に制御が渡されます。関数が戻ると、制御はその関数からそれを呼び出した関数に渡されます。関数にステップ インし、各ステートメントをステップ オーバーし、関数からステップアウトします。

関数呼び出しの通常の簿記は、スタックと呼ばれる構造です。ばねの上に置かれたプレートの積み重ねを想像することになっています。関数の各呼び出し (呼び出し) は、スタックの「トップ」に「プッシュ」されるもう 1 つのプレートです。関数からの各リターンは、その呼び出しをスタックから「ポップ」します。