再帰呼び出しを使用せずに再帰関数を書き換える

Question

再帰呼び出しが容易に実装されないか望まれない設定で、既存のコードを書き直しています。 （と知っている必要がある場合、Fortran 77で）私は必要な呼び出しを追跡するためにスタックを最初から作ることを考えましたが、これはクルージングのようです。再帰は深くない。 （私は、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

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

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

しかし、この機能は、それが自動プロセスに一般化することができるかどうかわからない、どのように機能するかについての知識を必要とします。