9

再帰呼び出しが簡単に実装されない、または望まれない設定で、既存のコードを書き直しています。（そして、Fortran 77では、知っておく必要があります。）必要な呼び出しを追跡するために最初からスタックを作成することを考えましたが、これは厄介なようで、配列にメモリを割り当てたくない場合は、再帰は深くありません。（Fortran 77が動的配列のサイズ設定もサポートしているとは確信していません。）

明らかに再帰的な関数を取得し、スタック上のスペースを無駄にすることなく非再帰的に書き換える方法に関する一般的な解決策に関する他の提案はありますか？

どうもありがとう、Old McSt

4

3 に答える 3

16

コードが末尾再帰を使用している場合 (つまり、関数が他の処理を行わずにすべての再帰呼び出しの結果を直接返す場合)、スタックなしで関数を命令的に書き直すことができます。

function dosomething(a,b,c,d) 
{
  // manipulate a,b,c,d
  if (condition) 
    return dosomething(a,b,c,d) 
  else
    return something;
}

の中へ：

function dosomething(a,b,c,d) 
{
  while (true) 
  {
    // manipulate a,b,c,d
    if (condition) continue;
    else return something;
  }
}

末尾再帰がなければ、スタック (または同様の中間ストレージ) を使用することが唯一の解決策です。

于 2010-12-12T14:17:42.390 に答える
3

ループとして記述できる古典的な再帰関数は、フィボナッチ関数です。

 function fib(n)
 {
     // valid for n >= 0
     if (n < 2)
         return n;
     else
         return fib(n-1) + fib(n-2);
 }

ただし、メモ化しない場合、これにはO（N）スタックスペースを使用したO（exp ^ N）操作が必要です。

書き直すことができます：

 function fib(n)
 {
     if (n < 2)
        return n;
     var a = 0, b = 1;
     while (n > 1)
     {
         var tmp = a;
         a = b;
         b = b + tmp;
         n = n - 1;
     }   
     return b;
 }

ただし、これには関数がどのように機能するかについての知識が含まれ、自動プロセスに一般化できるかどうかはわかりません。

于 2010-12-12T16:51:54.890 に答える
2

ほとんどの再帰関数は、スペースの浪費に関してループとして簡単に書き直すことができます-これは関数によって異なります.多くの(すべてではありませんが)再帰アルゴリズムは実際にはその種のストレージに依存しているためです(ただし、これらの場合はループバージョンの方が通常より効率的です)それも）。

于 2010-12-12T14:15:59.677 に答える