遞歸在C++中真的很慢嗎？

-1

我知道，遞歸是在一些語言快（甚至快於迭代）。但我在談論C++（也許C也是一樣）。遞歸在C++中真的很慢嗎？

我正在解決在線裁判問題（不是作業）。我使用自頂向下的動態編程方法解決了這個問題。但最後2例我得到了TLE。然後，我採用自下而上的方法，並接受了解決方案。然而，在這個問題中，我認爲自上而下應該更快，因爲可以優化來跳過一些不計算的狀態。

問題陳述：http://www.hkoi.org/training2004/files/need-for-speed.pdf

守則如下：

#include <cstdio> 
#include <algorithm> 

using namespace std; 

int n, max_t; 
int num[51][50001]; 
int ts[50][50]; 
int ms[50]; 
int ls[50]; 

#ifdef RECURSION 
int solve(int rn, int tleft) 
{ 
    if (rn >= n) 
     return 0; 

    if (num[rn][tleft] != -1) 
     return num[rn][tleft]; 

    int t; 
    int max_num = solve(rn + 1, tleft); 
    for (int i = rn; i < n; ++i) 
    { 
     t = ls[i]; 
     for (int j = 0; j < ms[i]; ++j) 
     { 
      t += ts[i][j]; 
      if (t > tleft) 
       break; 

      max_num = max(max_num, solve(i + 1, tleft - t) + j + 1); 
     } 
    } 

    num[rn][tleft] = max_num; 
    return max_num; 
} 
#endif 

int main() 
{ 
    scanf("%d %d", &n, &max_t); 

    for (int i = 0; i < n; ++i) 
    { 
     scanf("%d %d", ls + i, ms + i); 

     for (int j = 0; j < ms[i]; ++j) 
     { 
      scanf("%d", ts[i] + j); 
     } 

     sort(ts[i], ts[i] + ms[i]); 
    } 

    for (int i = 0; i <= n; ++i) 
    { 
     for (int j = 0; j <= max_t; ++j) 
     { 
      #ifdef RECURSION 
      num[i][j] = -1; 
      #else 
      num[i][j] = 0; 
      #endif 
     } 
    } 

    #ifdef RECURSION 
    printf("%d\n", solve(0, max_t)); 
    #endif 

    #ifndef RECURSION 
    int t; 
    for (int i = n - 1; i >= 0; --i) 
    { 
     for (int j = 0; j <= max_t; ++j) 
     { 
      t = ls[i]; 
      num[i][j] = num[i + 1][j]; 
      for (int k = 0; k < ms[i]; ++k) 
      { 
       t += ts[i][k]; 
       if (t > j) 
        break; 

       num[i][j] = max(num[i][j], num[i + 1][j - t] + k + 1); 
      } 
     } 
    } 

    printf("%d\n", num[0][max_t]); 
    #endif 
}

正如你在遞歸版本中看到，有一條線max_num = max(max_num, solve(i + 1, tleft - t) + j + 1);。由於t用一個整數遞增並不總是= 1，某些情況下被跳過。但是，在迭代版本中，計算了許多無用的狀態。

我認爲如果迭代解決方案更快，那麼遞歸必須比迭代慢得多。我的聲明是正確的嗎？

來源

2014-04-23 qpalz

比語言更多，這取決於你如何實現它。以完全無用或低效的方式創建一個實現遞歸的函數是非常容易的。 –

有沒有這樣的事情，「遞歸比迭代慢」。這裏只有「在這個特殊的語言這一特定問題的這個特殊的遞歸解決方案與這個特殊的編譯器是比較慢」（再次，不是** **具體迭代求解，在同一臺機器上，在相同的語言，使用相同的編譯器）。 –

性能優化是一個非常複雜的領域，您通常無法將其縮小爲簡單的建議，如「迭代比遞歸更快」。

快速找到計數器例子：例如，大多數最快的排序算法（如Quicksort）通常是遞歸實現的。

對於您的情況，執行一些便宜的操作往往可能比執行復雜的檢查以防止它們快得多，例如緩存未命中次數較少。判斷一個解決方案是否優於另一個解決方案的唯一方法是使用分析器進行仔細分析。

看到這個出色答卷（實際上它更像是一篇文章），涵蓋分支預測：Why is it faster to process a sorted array than an unsorted array?

來源

2014-04-23 06:10:16

Theoratically迭代==遞歸，授予您不使用編譯器優化。的主要區別在於，堆棧被填充功能與遞歸需要解決。然而，遞歸是最經常容易轉化爲多線程應用程序。此外，如果你有很多的if語句，遞歸解決方案有助於使代碼更抽象的，你可以在執行過程中確實方便地切換到另一種類型的遞歸（只是調用函數不同，或致電完全不同的功能）。

來源

2014-04-23 06:01:36

遞歸在C++中真的很慢嗎？

回答

相關問題