遞歸到迭代轉換

瞭解每個遞歸函數都可以轉換爲迭代版本。有人可以幫我找到這個僞代碼的迭代版本嗎？我試圖優化代碼和遞歸顯然不是要走的路線遞歸到迭代轉換

sub calc (a, b) 
{ 
    total = 0; 
    if(b <= 1) 
     return 1 
    if(2*a > CONST) 
     for i IN (1..CONST) 
      total += calc(i, b-1) ; 
    else 
     for j IN (2*a..CONST) 
      total += calc(j, b-1) ; 
    return total; 
} 
CONST = 100; 
print calc (CONST,2000);

感謝您的幫助！

來源

2013-04-12 Techmonk

什麼是總數？它是在別處定義還是應該在函數體內初始化？ – AlexFoxGill

在體內初始化 – Techmonk

謝謝。另外，也許你可以提供一些樣本輸入和輸出？算法看起來幾乎就像你不需要迭代或遞歸，而只是一個數學公式。 – AlexFoxGill

從遞歸到迭代的重構不是解決您在這裏的性能問題的答案。該算法從高速緩存中獲益最多，與Fibonacci序列的方法大致相同。

在F＃寫一個短的測試程序，具有一定的樣本數據（CONST = 5，a = 0..10，b = 2..10）後：

原計劃把6.931秒
緩存版本了0.049秒

解決方案是保存一個密鑰爲tuple(a,b)的字典，然後在計算之前查找這些值。這裏是緩存算法：

dictionary = new Dictionary<tuple(int, int), int>(); 

sub calc (a, b) 
{ 
    if (dictionary.Contains(tuple(a,b))) 
     return dictionary[tuple(a,b)]; 
    else 
    { 
     total = 0; 
     if(b <= 1) 
      return 1 
     if(2*a > CONST) 
      for i IN (1..CONST) 
       total += calc(i, b-1); 
     else 
      for j IN (2*a..CONST) 
       total += calc(j, b-1); 

     dictionary[tuple(a,b)] = total; 
     return total; 
    } 
}

編輯：只是爲了確認，這不是我的測試造成的性能增益的迭代特性，我用一組參數（CONST = 5再次嘗試他們兩個， a = 6，b = 20）。

緩存版本了0.034秒
原始版本仍在運行...（2+分鐘）

來源

2013-04-12 15:48:08 AlexFoxGill

好主意，但我認爲它需要一些改進，因爲我們從來沒有爲相同的a調用函數，b對緩存不會以這種方式幫助很多。 – Techmonk

@Techmonk實際上，您可以調用相同的a，b對的函數。 – JakeP

你是對的！去實現內存 – Techmonk

只有尾遞歸算法可以轉換爲迭代算法。您提供的代碼絕對不是尾遞歸，因此不能輕易轉換爲迭代形式。

解決您的性能問題是Memoization

來源

2013-04-13 01:16:00 GoZoner

遞歸到迭代轉換

回答

相關問題