末尾再帰とは何ですか？

末尾再帰は、呼び出し関数が再帰呼び出しを行った後、それ以上計算を行わない特殊な再帰のケースです。たとえば、関数

 int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); } 

は末尾再帰です（最後の命令は再帰呼び出しであるため）が、この関数は末尾再帰ではありません：

 int g(int x) { if (x == 1) { return 1; } int y = g(x-1); return x*y; } 

再帰呼び出しが戻った後に何らかの計算を行うため。

末尾再帰は、一般的な再帰よりも効率的に実装できるため、重要です。通常の再帰呼び出しを行うときは、リターンアドレスを呼び出しスタックにプッシュしてから、呼び出された関数にジャンプする必要があります。これは、再帰呼び出しの深さでサイズが線形である呼び出しスタックが必要であることを意味します。末尾再帰がある場合、再帰呼び出しから戻るとすぐに戻るので、再帰関数のチェーン全体をスキップして元の呼び出し元に直接戻ることができます。つまり、 「すべての再帰呼び出しに呼び出しスタックはまったく必要ありません。最後の呼び出しを単純なジャンプとして実装できるため、スペースを節約できます。

コメント

• あなたが書いた"つまり、'すべての再帰呼び出しに呼び出しスタックはまったく必要ありません"。コールスタックは常に存在しますが、リターンアドレスをコールスタックに書き込む必要はありませんよね？
• 計算モデルによってある程度異なります:)しかし、実際のコンピュータでは、コールスタックはまだ存在しますが、'使用していません。
• 最終的な'の場合はどうなりますか。呼び出しますが、forループになります。したがって、上記のすべての計算を実行しますが、一部はdef recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctorのようなforループで実行します-この再帰は' t終了します。

簡単に言うと、テール再帰はコンパイラが置き換えることができる再帰です。 「goto」コマンドを使用した再帰呼び出し。コンパイルされたバージョンでスタックの深さを増やす必要はありません。

テール再帰関数を設計するには、追加のパラメーターを使用してヘルパー関数を作成する必要がある場合があります。

たとえば、これはテール再帰関数ではありません ：

int factorial(int x) { if (x > 0) { return x * factorial(x - 1); } return 1; } 

しかし、これはテールです-再帰関数：

int factorial(int x) { return tailfactorial(x, 1); } int tailfactorial(int x, int multiplier) { if (x > 0) { return tailfactorial(x - 1, x * multiplier); } return multiplier; } 

コンパイラは、次のようなもの（疑似コード）を使用して、再帰関数を非再帰関数に書き換えることができるため：

int tailfactorial(int x, int multiplier) { start: if (x > 0) { multiplier = x * multiplier; x--; goto start; } return multiplier; } 

コンパイラのルールは非常に単純です。「return thisfunction(newparameters);」が見つかったら、「

“。ただし、これは、再帰呼び出しによって返された値が直接返される場合にのみ実行できます。

関数内のすべての再帰呼び出しをこのように置き換えることができる場合、それは末尾です。 -再帰関数。

私の回答は、本コンピュータプログラムの構造と解釈。私はこの本をコンピュータ科学者に強くお勧めします。

アプローチA：線形再帰プロセス

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

のプロセスの形状アプローチA は次のようになります：

(factorial 5) (* 5 (factorial 4)) (* 5 (* 4 (factorial 3))) (* 5 (* 4 (* 3 (factorial 2)))) (* 5 (* 4 (* 3 (* 2 (factorial 1))))) (* 5 (* 4 (* 3 (* 2 (* 1))))) (* 5 (* 4 (* 3 (* 2)))) (* 5 (* 4 (* 6))) (* 5 (* 24)) 120 

アプローチB：線形反復プロセス

(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count))) 

アプローチB のプロセスの形状は次のようになります：

(factorial 5) (fact-iter 1 1 5) (fact-iter 1 2 5) (fact-iter 2 3 5) (fact-iter 6 4 5) (fact-iter 24 5 5) (fact-iter 120 6 5) 120 

線形反復プロセス（アプローチB）は、プロセスが再帰的な手順であっても、一定のスペースで実行されます。このアプローチでは、セット変数が任意の時点でのプロセスの状態を定義することにも注意してください。 {product, counter, max-count}。これは、末尾再帰によってコンパイラの最適化を可能にする手法でもあります。

アプローチAには、基本的に遅延操作のチェーンである、インタプリタが維持するより多くの隠された情報があります。

コメント

• 'は(1) (* 1)の代わりに？

テール再帰は再帰の形式であり、再帰呼び出しは関数の最後の命令です（テール部分はそこから始まります）。さらに、再帰呼び出しは、前の値を格納するメモリセルへの参照（以外の参照）で構成してはなりません。関数のパラメーター）。このように、以前の値は気にせず、すべての再帰呼び出しには1つのスタックフレームで十分です。末尾再帰は、再帰アルゴリズムを最適化する1つの方法です。他の利点/最適化は、末尾再帰アルゴリズムを、再帰の代わりに反復を使用する同等のアルゴリズムに変換する簡単な方法があることです。そうです、クイックソートのアルゴリズムは確かに末尾再帰です。

QUICKSORT(A, p, r) if(p < r) then q = PARTITION(A, p, r) QUICKSORT(A, p, q–1) QUICKSORT(A, q+1, r) 

反復バージョンは次のとおりです：

QUICKSORT(A) p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) r = q - 1 p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) p = q + 1