テールvs。非末尾再帰
1. 序章
このチュートリアルでは、末尾再帰とは何かについて説明します。 また、末尾再帰関数が非末尾再帰よりも優れている点についても説明します。
2. 再帰
簡単に言うと、再帰関数は、それ自体のインスタンスを呼び出す任意の関数です。 配列の合計の関数を見てみましょう。
これにより、が再帰的に呼び出され、次に、が呼び出されます。これは、の基本ケースまで続きます。 これには3つの問題があります。2つは入力の再帰的処理に関連し、もう1つはメモリに関連します。
2.1. トラバーサルの問題
最初の問題は、スタックオーバーフローのリスクがあることです。 再帰が深すぎると、最終的にスタックスペースが不足し、新しいフレームを追加できなくなります。 このシナリオは、入力が大きすぎる場合に実行されます。
2つ目は、計算が基本ケースから始まり、配列全体をトラバースしてそれに到達することです。 そのパスの間、計算は行いません。 基本ケースに到達した後でのみ、配列の要素を相互に追加し始めることができます。 これを行うには、最初の呼び出しに戻ります。 したがって、次の例に示すように、入力配列を1回ではなく2回渡します。
2.2. メモリー
3番目の問題は、再帰呼び出しごとに新しいフレームが呼び出しスタックに追加され、各フレームがローカル変数と入力引数用に追加のメモリを予約することです。これは前の例では問題ありませんが、次の例では問題になります。 。 たとえば、合計したい配列がメモリにないことを想像してみましょう。 代わりに、ギガバイトの生データをからダウンロードし、それを処理して単一の数値を取得することで取得できます。
これで、処理後に生データを保持する必要がない場合でも、各スタックフレームはギガバイトのメモリを使用します。
3. テールvs。 非末尾再帰
両方の問題は、とが非末尾再帰関数であるという事実から生じます。 関数は、再帰呼び出しの値を返すことによって終了する場合、末尾再帰です。再帰呼び出しがその値を返すと、何もすることがないため、呼び出し元のフレームをスタックに保持することはメモリの浪費です。 したがって、呼び出しに新しいフレームを割り当てる代わりに、既存のフレームを再利用できます。 その結果、コンパイラは末尾再帰関数を認識し、フレーム割り当てを最適化できます。
末尾呼び出しの最適化の恩恵を受けるために、関数は再帰的である必要はありません。 呼び出し後に行うことが、呼び出された関数の値を返すことだけである限り、任意の関数を呼び出すことができます。 ただし、この記事では再帰のみに焦点を当てます。
3.1. 末尾再帰SUM
再帰呼び出しの後、戻り値に追加されるため、末尾再帰ではありません。 末尾再帰にするために、少し調整する必要があります。 具体的には、最後の行が。になるように、加算を引数に移動する必要があります。 アイデアは、最初に配列を通過するときに数値を合計し、現在の部分合計を引数としてに渡すことです。 そうすれば、ベースケースに到達したら戻る必要がなく、同じフレームを再利用できます。
の初期値としてそれを呼び出します。その実行は次のようになります。
同じ戦略が、他の非テール再帰でも機能します。
4. 末尾再帰関数からの反復アルゴリズムの導出
末尾再帰関数を作成することは、再帰呼び出しの代わりにGOTOコマンドを使用することと同じです。
他に2つの変更を加えました。 まず、部分和は、の先頭で初期化するローカル変数になりました。 2番目の変更は、配列の未処理部分の終わりを指す変数として扱うようになったことです。 そこで、各GOTOの直前に、段階的に1つずつ減らしていきます。
4.1. GOTOからWHILEへ
上記のGOTO関数は、whileループを使用した反復アルゴリズムに変換されます。 基本ケース条件の否定は、whileループの条件になります。 GOTOコマンドを除くelse-branchは、 while-loop の本体になり、部分的な結果の初期化はループの前に行われます。 最後に、ループの後にベースケースを移動し、反復関数を取得します。 入力のサイズを繰り返し処理します。 この例では、それはになります。したがって、whileループの条件は次のとおりです。
5. 結論
この記事では、末尾再帰と非末尾再帰の違いについて説明しました。 前者のタイプの関数は既存のスタックフレームを再利用できるため、メモリを節約し、スタックオーバーフローエラーを回避します。 また、ベースケースを処理した後に計算を終了するため、コールスタックをトラバースして元のフレームに戻ることはありません。
