將具有for循環的遞歸函數更改爲迭代函數？

所以我有這個函數，我試圖從遞歸算法轉換爲迭代算法。我甚至不確定是否有正確的子問題，但這似乎確定了我需要以正確的方式，但遞歸無法使用，因此您需要使用動態編程，因此我需要將其更改爲自下而上或頂端迭代下來動態編程。將具有for循環的遞歸函數更改爲迭代函數？

基本遞歸函數如下：

Recursion(i,j) { 
    if(i > j) { 
     return 0; 
    } 
    else { 
     // This finds the maximum value for all possible 
     // subproblems and returns that for this problem 
     for(int x = i; x < j; x++) { 
      if(some subsection i to x plus recursion(x+1,j) is > current max) { 
       max = some subsection i to x plus recursion(x+1,j) 
      } 
     } 
    } 
}

這是一般的想法，但由於遞歸通常沒有在他們的循環，我不知道我會究竟如何將此轉換爲迭代。有沒有人有任何想法？

來源

2009-11-23 Bill

-1

很好，除非有與邏輯尚未列入的問題，它應該是罰款

爲&，而在遞歸確定

只是確保你在可能發生的各種情況下返回

來源

2009-11-23 08:05:06 GeeKieR

我也沒有看到問題。 – AppliedNumbers 2014-12-07 00:19:38

您有可以概括爲這樣一個遞歸函數：

recursive(i, j): 
    if stopping condition: 
     return value 

    loop: 
     if test current value involving recursive call passes: 
      set value based on recursive call 

    return value # this appears to be missing from your example

（我要和僞代碼相當寬鬆，他爲了強調代碼的結構而不是具體的實現）

而你想將它扁平化爲純粹的迭代方法。首先，很好地描述這在一般情況下涉及到什麼，因爲您似乎對此感興趣。然後我們可以繼續展開上面的僞代碼。

現在展平原始遞歸函數非常簡單。當你給出的代碼是這樣的：

simple(i): 
    if i has reached the limit: # stopping condition 
     return value 

    # body of method here 

    return simple(i + 1) # recursive call

您可以快速地看到，遞歸調用將一直持續到i達到了預定的極限。發生這種情況時，將返回value。這樣做的迭代形式爲：

simple_iterative(start): 
    for (i = start; i < limit; i++): 
     # body here 

    return value

這工作，因爲遞歸調用形成以下調用樹：

simple(1) 
    -> simple(2) 
    -> simple(3) 
     ... 
     -> simple(N): 
      return value

我將描述調用樹作爲一條繩子。它有一個開始，一箇中間和一個結束。不同的調用發生在字符串的不同點上。

這樣的調用字符串非常像for循環 - 函數完成的所有工作都會傳遞給下一個調用，並且遞歸的最終結果會傳回。 for循環版本只需要傳入不同調用的值並在其上運行主體代碼。

到目前爲止簡單！

現在你的方法是在兩個方面更爲複雜：

有多種不同的語句進行遞歸調用
這些語句本身是在for循環內

所以你調用樹是這樣的：

recursive(i, j): 
    for (v in 1, 2, ... N): 
    -> first_recursive_call(i + v, j): 
     -> ... inner calls ... 
    -> potential second recursive call(i + v, j): 
     -> ... inner calls ...

正如你可以看到這個我根本不像一根弦。相反，它實際上就像一棵樹（或布什），因爲每次通話都會導致另外兩次通話。此時實際上很難將其轉化爲完全迭代的功能。

這是因爲循環和遞歸之間的基本關係。任何循環都可以重新遞歸調用。然而，並非所有遞歸調用都可以轉換爲循環。

可以轉換爲循環的遞歸調用的類被稱爲原始遞歸。你的功能最初看起來已經超越了它。如果是這種情況，那麼您將無法將其轉換爲純粹的迭代函數（實際上在函數中實現調用堆棧和類似內容）。

此視頻介紹遵循原始遞歸從根本上遞歸類型之間的區別：

https://www.youtube.com/watch?v=i7sm9dzFtEI

我想補充一點，你的條件和分配給max值似乎是相同的。如果是這種情況，那麼你可以刪除一個遞歸調用，使你的函數成爲一個循環包裝的原始遞歸實例。如果你這樣做了，那麼你可能會把它弄平。

來源

2015-02-02 16:28:32

將具有for循環的遞歸函數更改爲迭代函數？

回答

相關問題