再帰関数の最適化

Question

私は現在、多くの再帰呼び出しを扱うサイドプロジェクトに取り組んでいます。私はコンピュータ科学者ではないので、自分のコードをどのように最適化するかは正確にはわかりません。再帰関数はあまり効率的ではないと私は知っていますが、あなたはしばしばそれを末尾呼び出しで置き換えることができると聞いてきましたが、私はこれをどうやって行うのか正確にはわかりません。この関数は、appendList、sequence、およびusedの3つの配列を取ります。他の引数base、length、index、last wordは整数です。

function Recursion(appendList, base, length, sequence, used, lastWord, index) 
#Global variables: 
global G_Seq_List 
global G_Seq_Index 

used = ones(UInt8, 1, base^length) 
used[1] = 0 

if index == base^length 
    check = zeros(UInt8, base^length, 1) 

    for i = 1 : base^length 
     index = 1 
     for j = 1 : length 
      k = mod(i+j-1,base^length) 
      index = index + base^(length - j)*sequence[k+1] 
     end 

     check[index] = check[index] + 1 

     if check[index] != 1 
      return 
     end 
    end 

    G_Seq_List[G_Seq_Index,:] = sequence[:] 
    G_Seq_Index = G_Seq_Index + 1 

    return 
end 

#Builds Sequence 
for i = 1 : base^length 
    if appendList[i , mod(lastWord - 1, base^(length - 1)) + 1] == 1 
     if used[i] == 1 
      tempUsed = used 
      tempUsed[i] = 0 
      tempCounter = index + 1 
      tempSequence = sequence 
      tempSequence[tempCounter] = mod(i - 1, base) 
      Recursion(appendList, base, length, tempSequence, tempUsed, i, tempCounter) 
     end 
    end 
end 
end 

この再帰をテールコールに変えるのは簡単な修正ですか？そうでない場合は、この機能を最適化するためにどのようなことができますか？

Answer 1

通常、すべての再帰をループに変換することができます。新しいフレームを割り当てたり、余分な情報を保存したりする必要はなく、アルゴリズムのパフォーマンスは同等です。 「末尾呼び出し -

「テール呼び出しの最適化は、」再帰呼び出しは、関数の最後の呼び出し（したがって、その名前であれば、自動的にループに再帰を変換することである、コンパイラ（またはランタイム）が行うものです"）、通常は新しいコールフレームを割り当てるのではなく、同じコールフレームを再利用します。フレームを再利用するのは大丈夫です。再帰呼び出しの結果を返すだけであれば、それを囲む関数呼び出しから何も必要ないので、最初にフレームを生かしておく理由はないからです。

だから、何あなたがチェックする必要がありますすることです：

1. コンパイラが末尾呼び出しの最適化をサポートしているかどうか。
2. コンパイラがそうするために必要な作業 - 通常は直接パターンが機能しますが、コンパイラがより複雑なコードをサポートすることがあります。

どちらもあなたの特定のコンパイラに依存していますので、私はそれについてのドキュメントを参照しています - 私はそれがあなたの質問から何かを伝えることができませんでした。