再帰の謎- Pythonで実装する方法を理解する

再帰とは何か

あなたが再帰の根底にある概念を理解するが、私自身のようにそれを実行するのに苦労するか、あなたがそれが何であるかについてさえわからないならば、あなたのためにこのポスト.
再帰は、問題を解くことのできる小さなバージョンに分解することによって複雑な問題を解決すると定義されます.プログラミングでは、これは関数呼び出し自身を持つことによって行われます.
再帰の根本原理はこれら2つのケースです.

ベースケース:このケースは問題の最小のインスタンスを定義します.特定の再帰的な解決において、複数のベースケースがあるかもしれませんが、このポストの説明の目的のために、私の例は1つだけを取り入れます.コーディングするとき、基底ケースは関数自体の呼び出しの無限ループを防止します.

再帰的なケース:このケースはベースケースに近づくために問題を操作します.プログラミングでは、この関数が自分自身を呼び出す場合です.

簡単に言えば、それがベースケースに到達するまで、再帰的なケースは問題を破壊するでしょう.
再帰のあなたの理解が危険であるならば、心配しないでください.

呼び出しスタック

Pythonで再帰がどのように実装されているかを本当に理解するためには、コールスタックをよく理解する必要があります.
呼び出しスタックは、スタックデータ構造を使用してローカル変数と前の関数呼び出しを追跡します.スタックは最後のIN、最初のOutデータ構造です.これは、スタックに配置される最後の項目が最初に削除されることを意味します.視覚化するために、プレートのスタックを考えてください.

プレートが最後にスタックに置かれているものは、最初に削除されるものです.
プログラミングに関して、スタックは2つの単純な操作をします:プッシュとポップ.pushはスタックにアイテムを追加し、スタックから項目を削除し、その値を返します.
Pythonでは、呼び出しスタックはフレームから成ります.一番下のフレームはグローバルまたはモジュールフレームです.これは全てのグローバル変数から成ります.関数が新しい変数と呼ばれるたびに、ローカル変数と関数引数を含むスタックにプッシュされます.関数呼び出しが戻ると、フレームがスタックからポップされ、その値が前のフレームで呼び出された場所に渡されます.

有名な再帰例

数の階乗は以下のように定義される.
4 !4 * 3 * 2 * 1 = 24
数Nの階乗を数学的な方程式と定義するなら、

factorial(n) = n * factorial(n-1)

方程式の右側は、我々の解決の再帰的なケースになります.注意して、再帰的な場合は、元の問題(階乗(n))をとって、階乗(n - 1)が何でもnを掛けることのより単純な問題になります.
パラメータnを取る関数の階乗を定義することができます.ただし、この関数を定義した場合、上記の式を使用すると、無限にエラーにつながることになります.
これはベースケースを定義しなかったからです.最も基本的な要因は1の階乗である.そこで、1 *階乗( 0 )を呼び出すのではなく、1を返すには、1の階乗に到達したらプログラムを伝えることができます.その後、Python呼び出しスタックは数値を乗算処理します.
再帰と基底の両方を定義した後、以下のPythonプログラムに到達します.

def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n-1)

深さ再帰関数実装

factorial関数を呼び出す前に、Python呼び出しスタックは次のようになります.

次に、4の引数で階乗関数を渡します.

factorial(4)

階乗関数のためのフレームは、呼び出しスタックにプッシュされます.引数nを4に設定します.

Pythonインタプリタは関数を処理し、Nは< = 1ではないので、N *階乗( n - 1 )を評価します.しかし、関数が値を返す前に、階乗を評価しなければなりません.これは別の階乗枠をスタックにプッシュし、引数nを3に設定します.

また、nが＜＝1でないので、n *階乗(n−1)を評価する.同様に、関数は値を返す前に階乗( n - 1 )を評価しなければなりません.
このパターンは、引数nが1に等しい階乗枠がスタックにプッシュされるまで継続されます.

このとき、関数は基底ケースに到達します.呼び出しスタックを説明するときに早めに述べたように、関数が戻ったとき、スタックからフレームを取り出し、その値を前のフレームで呼び出された場所に転送します.

Factorial(n - 1)の値が評価されたので、階乗関数はプロダクトを評価して、前のフレームにそれを返すことができます.

このパターンは、元の関数呼び出しに到達するまで続きます.

推測したように、引数4の階乗関数は24の値を返します.

概要

Pythonで再帰的な解決法を書くとき、基底ケースと再帰的なケースで問題を考えてください.どうすれば基本的な問題に対して問題を減らすのを助ける再帰的な事例を定義できますか
再帰的な解決を理解しようとするとき、私は私の頭で呼び出しスタックを視覚化するのが最もよいとわかります.関数が項目と呼ばれるたびにスタックに追加され、returnキーワードに遭遇すると、スタックから項目をポップし、前の関数呼び出しにその値を返します.
あなたがこれまでにそれをして、私のポストを楽しんだならば、Hashnodeと上で私について来てください.私はより多くのコンテンツを投稿する計画と提案や要求にオープンです!