54

末尾再帰は、再帰呼び出しが定数スタック (O(n) ではなく) を消費できるため、関数型言語における重要なパフォーマンス最適化戦略です。

単純に末尾再帰スタイルで記述できない問題はありますか?それとも、単純再帰関数を末尾再帰関数に変換することは常に可能ですか?

もしそうなら、いつの日か関数型コンパイラとインタプリタが自動的に変換を実行できるほどインテリジェントになるでしょうか?

4

5 に答える 5

51

はい、実際には、いくつかのコードを使用して、すべての関数呼び出し (およびすべての戻り値) を末尾呼び出しに変換できます。最終的に得られるものは、継続渡しスタイル (CPS) と呼ばれます。

たとえば、次の関数には 2 つの再帰呼び出しが含まれています。

(define (count-tree t)
  (if (pair? t)
    (+ (count-tree (car t)) (count-tree (cdr t)))
    1))

この関数を継続渡しスタイルに変換すると、次のようになります。

(define (count-tree-cps t ctn)
  (if (pair? t)
    (count-tree-cps (car t)
                    (lambda (L) (count-tree-cps (cdr t)
                                                (lambda (R) (ctn (+ L R))))))
    (ctn 1)))

追加の引数 は、を返す代わりに末尾呼び出しctnを行うプロシージャです。(sdcvvc の答えは、O(1) 空間ですべてを行うことはできないと言っていますが、それは正しいです。ここでは、各継続は、メモリを消費するクロージャーです。)count-tree-cps

carorの呼び出しcdrを+末尾呼び出しに変換しませんでした。それも可能ですが、これらのリーフ呼び出しは実際にはインライン化されると思います。

さて、楽しい部分です。Chicken Schemeは、コンパイルするすべてのコードに対して実際にこの変換を行います。Chicken によってコンパイルされたプロシージャは決して戻りません。Chicken が実装される前の 1994 年に書かれた、なぜ Chicken スキームがこれを行うのかを説明する古典的な論文があります: CONS should not cons its arguments, Part II: Cheney on the MTA

驚くべきことに、継続渡しスタイルは JavaScript ではかなり一般的です。ブラウザーの「遅いスクリプト」ポップアップを回避して、長時間実行される計算を行うために使用できます。また、非同期 API にとって魅力的です。jQuery.get(XMLHttpRequest の単純なラッパー) は明らかに継続渡しスタイルです。最後の引数は関数です。

于 2009-12-11T16:07:11.100 に答える
27

確かにそうですが、相互再帰関数のコレクションを末尾再帰関数に変換できることを観察するのは役に立ちません。この観察結果は、1960 年代に、すべてのプログラムが case ステートメントを入れ子にしたループとして記述できるため、制御フロー構造を削除できるという古い意見と同じです。

知っておくと便利なのは、明らかに末尾再帰ではない多くの関数が、累積パラメータを追加することで末尾再帰形式に変換できることです。(この変換の極端なバージョンは継続渡しスタイル (CPS) への変換ですが、ほとんどのプログラマーは CPS 変換の出力が読みにくいと感じています。)

以下は、「再帰的」であるが (実際には単に反復しているだけです)、末尾再帰的ではない関数の例です。

factorial n = if n == 0 then 1 else n * factorial (n-1)

この場合、乗算は再帰呼び出しの後に発生します。積を累積パラメーターに入れることで、末尾再帰的なバージョンを作成できます。

factorial n = f n 1
   where f n product = if n == 0 then product else f (n-1) (n * product)

内部関数fは末尾再帰であり、タイトなループにコンパイルされます。

次の区別が役立つと思います。

  • 反復プログラムまたは再帰的プログラムでは、サイズの問題を解決するにはn、最初にサイズの部分問題を1 つn-1解決します。階乗関数の計算はこのカテゴリに分類され、反復または再帰的に実行できます。n-1(この考え方は、たとえば、との両方が必要なフィボナッチ関数に一般化されますn-2。n)

  • 再帰的プログラムでは、最初に size の2 つの 部分問題をn解くことによってサイズの問題を解きます。または、より一般的には、 最初にサイズのサブ問題とサイズ のサブ問題を解決することによって、サイズの問題を解決します。クイックソートとマージソートは、この種の問題の 2 つの例であり、再帰的に簡単にプログラムできますが、繰り返しプログラムしたり末尾再帰のみを使用したりするのはそれほど簡単ではありません。(基本的に、明示的なスタックを使用して再帰をシミュレートする必要があります。)n/2nkn-k1 < k < n

  • 動的計画法では、最初にすべてのサイズ のすべての 部分問題をn解くことによって、サイズの問題を解決します。ここで、. ロンドンの地下鉄である地点から別の地点への最短ルートを見つけることは、この種の問題の例です。(ロンドンの地下鉄は多重接続グラフであり、最初に最短経路が 1 駅であるすべてのポイントを見つけ、次に最短経路が 2 駅であるというように、問題を解決します。)kk<n

最初の種類のプログラムだけが、末尾再帰形式への単純な変換を行います。

于 2009-12-12T01:07:14.887 に答える
11

再帰アルゴリズムは反復アルゴリズム (おそらくスタックまたはリストが必要) として書き直すことができ、反復アルゴリズムは常に末尾再帰アルゴリズムとして書き直すことができるため、再帰ソリューションは何らかの方法で末尾再帰ソリューションに変換できることは事実だと思います。 .

(コメントで、Pascal Cuoq は、どのアルゴリズムも継続渡しスタイルに変換できると指摘しています。)

何かが末尾再帰的であるからといって、そのメモリ使用量が一定であるとは限らないことに注意してください。これは、コール リターン スタックが大きくならないことを意味します。

于 2009-12-11T15:18:05.543 に答える
10

O(1) 空間ですべてを行うことはできません (空間階層定理)。末尾再帰の使用を主張する場合は、コール スタックを引数の 1 つとして格納できます。明らかに、これは何も変更しません。内部のどこかにコール スタックがあり、それを明示的に表示するだけです。

もしそうなら、いつの日か関数型コンパイラとインタプリタが自動的に変換を実行できるほどインテリジェントになるでしょうか?

このような変換は、スペースの複雑さを軽減しません。

Pascal Cuoq がコメントしたように、別の方法はCPSを使用することです。その場合、すべての呼び出しは末尾再帰です。

于 2009-12-11T15:24:58.637 に答える
1

テールコールのみを使用してtakのようなものを実装できるとは思いません。(継続不可)

于 2009-12-11T15:41:28.203 に答える