再帰を使用せずに再帰機能を書き直します

Question

再帰的な呼び出しが簡単に実装されておらず、望まれない設定で既存のコードを書き直しています。 （そして、Fortran 77で、あなたが知っておく必要がある場合）私は、必要な通話を追跡するためにゼロからスタックを作ることを考えましたが、これはKludgyのようです。再帰は深くありません。 （Fortran 77が動的な配列のサイジングをサポートしているとは確信していません。）

明らかに再帰的な機能を採用し、スタック上のスペースを無駄にすることなく、それを非回復的に書き直す方法に関する一般的なソリューションの他の提案はありますか？

たくさんのありがとう、古いMCST

Answer 1

コードがテールの再帰を使用している場合（つまり、関数は他の処理なしですべての再帰コールの結果を直接返します）、スタックなしで関数を命令することが可能です。

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;
  }
}

尾の再帰がなければ、スタック（または同様の中間ストレージ）を使用することが唯一のソリューションです。

Answer 2

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

 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;
 }

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

Answer 3

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