12

問題を解決するために再帰またはメモ化を使用する選択肢がある場合、どちらを使用する必要がありますか? 言い換えれば、それらが正しい出力を提供し、使用しているコードで合理的に表現できるという点で両方とも実行可能なソリューションである場合、いつ一方を他方よりも使用するのでしょうか?

4

14 に答える 14

22

それらは相互に排他的ではありません。両方使用できます。

個人的には、最初に基本再帰関数を作成し、その後、最適化手順としてメモ化を追加します。

于 2009-01-26T15:17:03.000 に答える
13

使用する経験則は、副問題が持つオーバーラップの量に基づいています。フィボナッチ数を計算している場合 (古典的な再帰の例)、再帰を使用すると、多くの不要な再計算が行われます。

たとえば、F(4) を計算するには、F(3) と F(2) を知る必要があるため、F(2) と F(1) を計算して F(3) を計算します。再帰を使用した場合、F(2) と他のほとんどの F(n) を 2 回計算するだけです。メモ化を使用すると、値を調べることができます。

二分探索を行っている場合、サブ問題間に重複がないため、再帰は問題ありません。各ステップで入力配列を半分に分割すると、重複のない 2 つの部分問題を表す 2 つの一意の配列が得られます。このような場合、メモ化は役に立ちません。

于 2009-01-26T15:30:28.277 に答える
8

再帰にはスタックフレームの作成に関連するパフォーマンスのペナルティがあり、メモ化のペナルティは結果のキャッシュです。パフォーマンスが懸念事項である場合、確実に知る唯一の方法はアプリケーションでテストすることです。

私の個人的な意見では、最初に使用して理解するのが最も簡単な方法を使用します。これは私の意見では再帰です。メモ化の必要性を示すまで。

于 2009-01-26T15:14:14.393 に答える
7

メモ化は、たまたま再帰を最適化するために一般的に使用されるキャッシング方法です。再帰を置き換えることはできません。

于 2009-01-27T22:53:12.500 に答える
6

問題を知らずに言えるかわからない。多くの場合、再帰を伴うメモ化を使用する必要があります。それでも、実際に代替ソリューションとして使用できる場合、メモ化は再帰よりも大幅に高速になる可能性があります。どちらにもパフォーマンスの問題がありますが、問題の性質や入力のサイズによって異なります。

于 2009-01-26T15:14:42.007 に答える
3

通常、スタックメモリよりも多くのヒープメモリにアクセスできるため、メモ化を選択します。

つまり、アルゴリズムが大量のデータで実行されている場合、ほとんどの言語では、ヒープ保存データのスペースが不足する前に、繰り返しスタックスペースが不足します。

于 2009-01-26T15:15:21.850 に答える
3

メモ化(他の人が指摘しているように、再帰アルゴリズムの最適化戦略) と動的プログラミング(再帰ソリューションをシミュレートしますが、実際には再帰を使用しません) を混同していると思います。それがあなたの質問だった場合、それはあなたの優先事項に依存すると思います: 高い実行効率 (動的プログラミング) または高い可読性 (メモ化、問題の再帰的な解決策がまだコードに存在するため)。

于 2009-02-09T23:57:33.830 に答える
2

再帰的な問題では再帰するしかないというTomalakの主張に同意しませんか？

最良の例は、上記のフィボナッチ数列です。私のコンピューターでは、再帰バージョンのF（45）（Fはフィボナッチの場合）は2269806339の追加に15秒かかり、反復バージョンは43の追加にかかり、数マイクロ秒で実行されます。

もう1つの有名な例は、ハノイの塔です。トピックに関するクラスの後、再帰がそれを解決する唯一の方法のように見えるかもしれません。しかし、ここでも反復的な解決策がありますが、再帰的な解決策ほど明白ではありません。それでも、主に高価なスタック操作が必要ないため、反復はより高速です。

Towers of Hamoiの非再帰バージョンに興味がある場合は、Delphiのソースコードを次に示します。

procedure TForm1.TowersOfHanoi(Ndisks: Word);
var
  I: LongWord;
begin
  for I := 1 to (1 shl Ndisks) do
    Memo1.Lines.Add(Format('%4d: move from pole %d to pole %d',
      [I, (I and (I - 1)) mod 3, (I or (I - 1) + 1) mod 3]));
  Memo1.Lines.Add('done')
end;
于 2009-02-13T16:17:47.560 に答える
2

それはあなたが何をしようとしているのかによります。動的計画法（メモ化）は、ほとんどの場合、より高速です。多くの場合、LOTによって。（つまり、立方体から平方、または指数関数からポリ）が、私の経験では、再帰は読みやすく、デバッグしやすいです。

繰り返しになりますが、多くの人は疫病のように再帰を避けているので、読みやすいとは思いません...

また、（サードハンド？）再帰的なソリューションを考え出した後、動的ソリューションを見つけるのが最も簡単であることがわかったので、両方を実行することになります。ただし、すでに両方のソリューションを使用している場合は、Dynamicが最善の策かもしれません。

私が役に立ったかどうかはわかりませんが、あなたはそこに行きます。アルゴリズム選択の多くのものと同様に、YMMV。

于 2009-01-26T15:16:44.560 に答える
2

問題が再帰的なものである場合、再帰する以外にどのような選択肢がありますか？

メモ化を使用して短絡するように再帰関数を記述して、2番目の呼び出しの最大速度を得ることができます。

于 2009-01-26T15:19:32.917 に答える
1

末尾再帰手法を使用して問題を解決できる場合、再帰は大量のスタック スペースを使用する必要はありません。前述のように、問題によって異なります。

于 2009-01-26T15:20:46.720 に答える
1

通常、決定に役立つ 2 つの基準に直面します。

  • 実行時間
  • 可読性

再帰コードは通常は遅くなりますが、はるかに読みやすくなります (常にではありませんが、ほとんどの場合。前述のように、言語がサポートしている場合は末尾再帰が役立ちます。サポートしていない場合は、できることはあまりありません)。

再帰的な問題の反復バージョンは通常、実行時間に関しては高速ですが、コードは理解しにくく、そのため脆弱です。

両方のバージョンの実行時間と可読性が同じである場合、どちらかを選択する理由はありません。この場合、他のことを確認する必要があります: このコードは変更されますか? メンテナンスはどうですか？再帰アルゴリズムに慣れていますか、それとも悪夢を見ていますか?

于 2009-01-26T15:50:25.413 に答える
1 
var memoizer = function (fund, memo) {
    var shell = function (arg) {
        if (typeof memo[arg] !== 'number') {
            memo[arg] = fund(shell, arg);
        }
        return memo[arg];
    };
    return shell;
};

var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, [0, 1]);

両方を使う！

于 2009-02-09T20:19:42.967 に答える
0

両方を組み合わせる。メモ化を使用して、再帰的なソリューションを最適化します。それがメモ化の目的です。メモリ空間を使用して再帰を高速化します。

于 2011-02-20T01:02:19.223 に答える