20

重複の可能性：
末尾再帰を使用して記述できない問題はありますか？

私の理解では、末尾再帰は、再帰呼び出しがスパムになるという再帰呼び出しからの情報を必要としない場合に使用できる最適化です。

それでは、末尾再帰を使用してすべての再帰関数を実装することは可能ですか？親ができる前に最も内側の子が戻る必要があるDFSのようなものはどうですか？

4

7 に答える 7

14

それはあなたが何を求めているかに正確に依存します。

すべての関数を同じシグニチャを持つ関数（可変状態なし）として保持する場合は、いいえ。最も明白な例はクイックソートで、両方の呼び出しを末尾呼び出しにすることはできません。

さまざまな方法で関数を変更できる場合は、はい。ローカルでの変更で十分な場合もあります。多くの場合、返される式を作成する「アキュムレータ」を追加できますが、結果に非可換演算が含まれる場合は注意が必要です（たとえば、リンクリストを単純に作成する場合は、順序が逆になります）、またはスタックを追加できます。

または、プログラム全体をグローバルに変更することもできます。この場合、各関数は、将来のアクションを含む関数を追加の引数として取ります。これは、ピートが話している継続渡しです。

手作業で作業している場合、ローカルでの変更は非常に簡単です。ただし、自動書き換えを行う場合（たとえば、コンパイラーで）、グローバルなアプローチを採用する方が簡単です（必要な「スマート」が少なくなります）。

于 2012-08-01T22:07:22.713 に答える
5

はいといいえ。

はい、他の制御フローメカニズム（継続渡しなど）と組み合わせて使用​​すると、任意の制御フローを末尾再帰として表現できます。

いいえ、他の制御フローメカニズムで末尾再帰を補足しない限り、すべての再帰を末尾再帰として表現することはできません。

于 2012-07-30T03:58:54.443 に答える
3

すべてのプログラムは、継続渡しを使用して末尾呼び出しとして書き直すことができます。現在の実行の継続を表す1つのパラメーターを末尾呼び出しに追加するだけです。

ターニングコンプリート言語は、継続渡しが提供するのと同じ変換を実行します-プログラムのGödel番号を作成し、非末尾呼び出しが戻るパラメーターを入力し、それをパラメーターとして末尾呼び出しに渡します-明らかにこれが継続、コルーチン、または他のファーストクラスの構成であなたのために行われると、それははるかに簡単になります。

CPSはコンパイラーの最適化として使用され、私は以前に継続渡しを使用してインタープリターを作成しました。スキームプログラミング言語は、末尾呼び出しの最適化とファーストクラスの継続の標準の要件を使用して、このような方法で実装できるように設計されています。

于 2012-08-01T12:42:48.763 に答える
3

はい、できます。変換には通常、必要な情報を明示的に維持することが含まれます。そうでない場合は、実行時に実行スタックの呼び出しフレーム間で暗黙的に分散されます。

それと同じくらい簡単です。実行時にランタイムシステムが暗黙的に実行するものは何でも、自分で明示的に実行できます。ここには大きな謎はありません。PCはシリコンと銅と鋼でできています。

処理する状態/位置/ノードの明示的なキューを持つループとしてDFSを実装するのは簡単です。実際、そのように定義されています。DFSは、キュー内のポップされた最初のエントリを、そこからのすべてのアークに置き換えます。BFSは、これらのアークをキューの最後に追加します。

継続渡しスタイル変換は、プログラム内のすべての関数呼び出しを、実行後に末尾呼び出しとして残します。これは人生の単純な事実です。使用される継続は拡大および縮小しますが、呼び出しはすべて末尾呼び出しになります。

ヒープ上に明示的に維持されたデータとして、継続で広がるプロセスの状態をさらに具体化することができます。これが最終的に達成するのは、説明と具体化であり、スタック上の暗黙的なものをヒープ内に存在する明示的なものに移動し、制御フローを単純化してわかりやすくします。

于 2012-08-05T23:07:26.693 に答える
2

すべての再帰関数を末尾再帰に書き換えることができるかどうかはわかりませんが、多くの場合は可能です。これを行う標準的な方法の1つは、アキュムレータを使用することです。たとえば、階乗関数は（Common Lispで）次のように書くことができます。

(defun factorial (n)
   (if (<= n 1)
       1
       (* n (factorial (1- n)))))

これは再帰的ですが、末尾再帰ではありません。アキュムレータ引数を追加することで、末尾再帰にすることができます。

(defun factorial-accum (accum n)
   (if (<= n 1)
       accum
       (factorial-accum (* n accum) (1- n))))

階乗は、アキュムレータを1に設定することで計算できます。たとえば、3の階乗は次のとおりです。

(factorial-accum 1 3)

ただし、このような方法を使用してすべての再帰関数を末尾再帰関数として書き直すことができるかどうかは、私にはわかりません。しかし、確かに多くの機能があり得ます。

于 2012-08-01T21:47:20.060 に答える
2

再帰的アルゴリズムは、分割統治法に従って実装されたアルゴリズムであり、各中間サブ問題を解決すると、0、1、またはそれ以上の新しい小さなサブ問題が生成されます。これらのサブ問題がLIFOの順序で解決されると、古典的な再帰アルゴリズムが得られます。

これで、アルゴリズムが各ステップで0または1のサブ問題のみを生成することがわかっている場合、このアルゴリズムは末尾再帰を介して簡単に実装できます。実際、このようなアルゴリズムは、反復アルゴリズムとして簡単に書き直し、単純なサイクルで実装できます。（追加する必要はありませんが、末尾再帰は、反復を実装するためのもう1つのあまり明確ではない方法です。）

このような再帰的アルゴリズムの教科書の例は、階乗計算への再帰的アプローチです。計算するには、最初に計算n!する必要があります(n-1)!。つまり、各再帰的ステップで、1つの小さなサブ問題のみが見つかります。これは、階乗計算アルゴリズムを真に反復的なアルゴリズム（または末尾再帰的なアルゴリズム）に簡単に変換できるようにするプロパティです。

ただし、一般的なケースで、アルゴリズムの各ステップで生成されるサブ問題の数が1を超えることがわかっている場合、アルゴリズムは実質的に再帰的です。反復アルゴリズムとして書き直すことはできず、末尾再帰を介して実装することはできません。このようなアルゴリズムを反復的または末尾再帰的に実装しようとすると、「保留中の」サブ問題を格納するために、一定でないサイズの追加のLIFOストレージが必要になります。このような実装の試みは、手動で再帰を実装することにより、アルゴリズムの避けられない再帰的な性質を単純に曖昧にします。

たとえば、親->子リンクがある（子->親リンクがない）バイナリツリーのトラバースなどの単純な問題は、実質的に再帰的な問題です。末尾再帰アルゴリズムでは実行できません。反復アルゴリズムでは実行できません。

于 2012-08-01T22:22:15.183 に答える
-1

いいえ、再帰呼び出しが1回の呼び出しに対してのみ「自然に」実行できます。2つ以上の再帰呼び出しの場合は、もちろんスタックフレームを自分で模倣できます。しかし、それは非常に醜く、メモリを最適化するという意味で、事実上末尾再帰にはなりません。

末尾再帰のポイントは、親スタックに戻りたくないということです。したがって、スタックを増やすのではなく、親スタックを完全に置き換えることができる子スタックにその情報を渡すだけです。

于 2012-07-30T10:31:00.640 に答える