將具有兩個遞歸調用的函數轉換爲一個迭代函數

我有一個函數有兩個遞歸調用，我試圖將它轉換爲迭代函數。我已經知道我可以在哪裏用一個電話很容易地做到這一點，但我無法弄清楚如何合併另一個電話。將具有兩個遞歸調用的函數轉換爲一個迭代函數

功能：

def specialMultiplication(n): 
    if n < 2: 
     return 1 
    return n * specialMultiplication(n-1) * specialMultiplication(n-2)

如果我只是其中之一，這將是非常容易：

def specialMult(n, mult = 1): 
    while n > 1: 
     (n, mult) = (n-1, n * mult) # Or n-2 for the second one 
    return mult

我只是無法弄清楚如何添加第二個電話中總體上得到正確的答案。謝謝！

來源

2016-12-31 firelover

你的算法的運行時間的一個簡化版本是指數。無論是遞歸實現還是迭代實施，只會以一個常數因子改變運行時間。 – merlin2011

謝謝@ merlin2011。我現在看到了。試圖找出如何將其轉換爲動態樣式。 – firelover

Blckknght的答案是應該以線性時間運行的DP解決方案。 – merlin2011

如果您不介意更改算法的結構，您可以從最小值開始以自下而上的方式計算值。

def specialMultiplication(max_n): 
    a = b = 1 
    for n in range(1, max_n+1): 
     a, b = b, a*b*n 
    return b

來源

2016-12-31 22:25:14 Blckknght

轉換的遞歸迭代函數使用輔助「待辦事項列表」：

def specialMultiplication(n): 
    to_process = [] 
    result = 1 
    if n >= 2: 
     to_process.append(n) 
     while to_process: # while list is not empty 
      n = to_process.pop() 
      result *= n 
      if n >= 3: 
       to_process.append(n-1) 
       if n >= 4: 
        to_process.append(n-2) 
    return result

創建工作列表（to_process）
如果n >= 2，加n到列表
而to_process不爲空，從列表中彈出項目，乘以結果
如果n-1 < 2，請勿pe rform「左」的操作（不追加到工作表）
如果n-2 < 2，不執行「正確」的操作（不追加到工作表）

此方法具有消耗的優點更少的堆棧。我已經針對從1到25的值遞歸版本檢查了結果，它們是相等的。

請注意，它仍然很慢，因爲複雜性是O(2^n)所以它開始從n=30（當n增加1時的時間加倍）開始非常慢。 n=28在我的筆記本電腦上計算時間爲12秒。

我已經成功地使用此方法修復了執行洪泛填充算法時的堆棧溢出問題：Fatal Python error: Cannot recover from stack overflow. During Flood Fill但這裏Blcknght答案更適合，因爲它重新考慮了從一開始就計算它的方式。

來源

2016-12-31 22:16:54

我剛剛嘗試過，並且適用於小數目。但是，當你達到90時，仍然需要相當長的時間。有什麼方法可以提高性能嗎？ – firelover

我發現現在它仍然很慢。將這個翻譯成動態風格的好方法是什麼？我不太熟悉這一點，可悲的是（但至少它指出了一些學習！） – firelover

即使它不是你的函數翻譯迭代，BlckKnght答案要快得多。 –

的OP的函數具有相同的遞歸結構作爲斐波那契和Lucas的功能，只是有用於F0，F1，和g不同的值：

f(0) = f0 
f(1) = f1 
f(n) = g(f(n-2), f(n-1), n)

這是一個recurrence relation的一個例子。這是一個通用解決方案的迭代版本，可以n步計算f（n）。它對應於一個自底向上的尾部遞歸。

def f(n): 
    if not isinstance(n, int): # Can be loosened a bit 
     raise TypeError('Input must be an int') # Can be more informative 
    if n < 0: 
     raise ValueError('Input must be non-negative') 
    if n == 0: 
     return f0 
    i, fi_1, fi = 1, f0, f1 # invariant: fi_1, fi = f(i-1), f(i) 
    while i < n: 
     i += 1 
     fi_1, fi = fi, g(fi_1, fi, n) # restore invariant for new i 
    return fi

Blckknight的回答是這

來源

2016-12-31 23:20:00

將具有兩個遞歸調用的函數轉換爲一個迭代函數

回答

相關問題