優化遞歸函數

我目前正在處理大量遞歸調用的側項目。我不是計算機科學家，所以我不確定如何優化我的代碼。我知道遞歸函數效率不高，我聽說你經常可以用tail調用替換它，但我不確定如何去做這件事。這個函數需要三個數組：appendList，sequence和used。其他參數，基數，長度，索引和最後一個詞是整數。優化遞歸函數

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

將此遞歸轉換爲尾部調用是否快速修復？如果不是，我可以做些什麼來優化這個功能？

來源

2017-04-26 RedShift

你能解釋一下你用這個函數來完成什麼嗎？此外，進行優化的第一步是瞭解*爲什麼要優化。它慢嗎？典型的輸入大小是多少？ – justhalf

一般來說，任何遞歸都可以轉換爲循環，並且循環通常會有更好的性能，因爲它具有相似的算法性能，而不需要分配新的幀和存儲額外的信息。

「尾巴調用優化」是後話了編譯器（或運行時）做的，這是自動遞歸轉換到一個循環，如果遞歸調用該函數中的最後一次通話（因此得名 - 「尾調用「），通常通過重複使用相同的呼叫幀而不是分配新呼叫幀。重用該框架是可以的，因爲如果你對遞歸調用的結果做了返回，那麼你不需要從封閉函數調用中得到任何其他東西，所以沒有理由保持框架在第一位。

所以，你需要檢查的是：

無論你的編譯器支持尾調用優化。
爲了讓編譯器能夠這麼做，你必須做的事情 - 通常簡單的return f(...)模式可以工作，但有時編譯器可以支持更復雜的代碼。

兩者都取決於您的具體編譯器，所以我會查找關於它的文檔 - 我不能說出你的問題是什麼。

來源

2017-04-27 13:24:21 Oak

優化遞歸函數

回答

相關問題