2

反復への再帰またはその逆のアルゴリズムは、最も効率的な出力と末尾再帰で存在しますか?

好ましい言語は C# です。

例: 入力時に、このアルゴリズムは次の単純な関数を取得します。

public static ulong Factorial(ulong n)
{
    return n == 0 ? 1 : n * Factorial(n - 1);
}

処理後、次のように戻ります。

public static ulong Factorial(ulong n)
{
    ulong result = 1;
    for (ulong i = 1; i <= n; i++)
        result = result * i;
    return result;
}
4

3 に答える 3

2

はい、再帰アルゴリズムから反復バージョンを作成することは常に可能です。C# でそれを行うためのプログラム/コード リライターが存在するかどうかはわかりません。この種の手法はよく研究されており、 「再帰から反復へ: 最適化とは何ですか?」などの一般的な参考文献を見つけることができます。(pdfファイル) .
最悪の場合、ヒープ上のスタックを単純に「エミュレート」して、将来の使用のために関数の状態を保存します。最も単純なケースは、おそらくループへの末尾再帰です。そのテーマに関する記事はたくさんあります。
一方、一般的な反復アルゴリズムから再帰バージョンを作成することはあまり研究されていませんが、確かに存在します。

于 2012-09-16T19:11:53.007 に答える
0

この種の変換を行うアルゴリズムの簡単で一般的な実装については知りませんが、非常に一般的な動的計画法を使用して再帰的アルゴリズムを最適化することは簡単です。

たとえば、各呼び出しの結果を辞書（ ->からのマップ）にキャッシュすると、反復と同じアルゴリズムの複雑さが得られます（ただし、時間の複雑さのみです。このメソッドではより多くのメモリが使用されます） 。自分のスタックを単に「模倣」するだけでは、アルゴリズムの複雑さに関して何も得られないことに注意してください。FactorialnFactorial(n)

キャッシングは、実装と適用の両方が非常に簡単で、幅広いアルゴリズムで機能します。

ウィキペディアのページには、サンプルアルゴリズムに関する特定のエントリがあります。

于 2012-09-16T19:23:05.117 に答える
0

私が知っている唯一のことは、再帰は で非再帰に等しく変換できるということstackです。実際にはそのように行われるため、自分で行うことができます。

ところで、単純な繰り返しに変換できない場合があると考えるかもしれません。

于 2012-09-16T19:12:56.563 に答える