循環是否比遞歸更快？

Question

根據我的教授，循環比使用遞歸更快更缺乏，但我想出了使用遞歸和循環計算斐波那契數列的C++代碼，結果證明它們非常相似。所以我最大化了可能的輸入，以查看性能是否有差異，並且由於某種原因遞歸的時鐘比使用循環更好。有人知道爲什麼先謝謝了。

下面的代碼：

#include "stdafx.h" 
#include "iostream" 
#include <time.h> 
using namespace std; 

double F[200000000]; 
//double F[5]; 

/*int Fib(int num) 
{ 
    if (num == 0) 
    { 
     return 0; 
    } 

    if (num == 1) 
    { 
     return 1; 
    } 

    return Fib(num - 1) + Fib(num - 2); 

}*/ 

double FiboNR(int n) // array of size n 
{ 


    for (int i = 2; i <= n; i++) 
    { 
     F[i] = F[i - 1] + F[i - 2]; 
    } 
    return (F[n]); 
} 

double FibMod(int i,int n) // array of size n 
{ 
    if (i==n) 
    { 
     return F[i]; 
    } 

    F[i] = F[i - 1] + F[i - 2]; 
    return (F[n]); 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    /*cout << "----------------Recursion--------------"<<endl; 
    for (int i = 0; i < 36; i=i+5) 
    { 
     clock_t tStart = clock(); 
     cout << Fib(i); 
     printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC); 
     cout << " : Fib(" << i << ")" << endl; 
    }*/ 

    cout << "----------------Linear--------------"<<endl; 
    for (int i = 0; i < 200000000; i = i + 20000000) 
    //for (int i = 0; i < 50; i = i + 5) 
    { 
     clock_t tStart = clock(); 
     F[0] = 0; F[1] = 1; 
     cout << FiboNR(i);   
     printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC); 
     cout << " : Fib(" << i << ")" << endl; 
    } 

    cout << "----------------Recursion Modified--------------" << endl; 
    for (int i = 0; i < 200000000; i = i + 20000000) 
    //for (int i = 0; i < 50; i = i + 5) 
    { 
     clock_t tStart = clock(); 
     F[0] = 0; F[1] = 1; 
     cout << FibMod(0,i); 
     printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC); 
     cout << " : Fib(" << i << ")" << endl; 
    } 

    std::cin.ignore(); 
    return 0; 
} 

Answer 1

你你去用傳統編程方式循環更快。但是有一類稱爲函數式編程語言的語言不包含循環。我是函數式編程的忠實粉絲，我是一名狂熱的Haskell用戶。 Haskell是一種函數式編程語言。在這個而不是循環你使用遞歸。爲了實現快速遞歸，有一些被稱爲尾遞歸。基本上爲了防止系統堆棧有很多額外的信息，你可以這樣編寫函數：所有的計算都存儲爲函數參數，這樣除了函數調用指針之外，什麼都不需要存儲在堆棧上。所以一旦最終的遞歸調用被調用，而不是展開堆棧，程序只需要進入第一個函數調用棧入口。函數式編程語言編譯器有一個內置的設計來處理這個問題。現在即使是非函數式編程語言也在實現尾遞歸。

例如，考慮找到用於查找正數的階乘的遞歸解決方案。在C中的基本的實施方法是

int fact(int n) 
{ 
    if(n == 1 || n== 0) 
     return 1 
    return n*fact(n-1); 

} 

在上述方法中，每個疊層被稱爲n次被存儲在堆棧中，以便它可以與事實的第（n-1）的結果相乘。這在堆棧放卷期間基本上發生。現在看看下面的實現。

int fact(int n,int result) 
{ 
    if(n == 1 || n== 0) 
     return result 

     return fact(n-1,n*result); 

} 

在這種方法中，我們通過計算結果的變量的結果。所以最終我們直接在變量結果中得到答案。你必須做的唯一事情就是在最初的調用中，在這種情況下爲結果傳遞值1。堆棧可以直接展開到第一個入口。當然，我不確定C或C++是否允許尾遞歸檢測，但函數式編程語言可以。

Answer 2

我不認爲這不是一個好問題。但也許答案爲什麼有些有趣。

首先讓我說，一般來說，這種說法可能是正確的。但是...

關於C++程序性能的問題是非常本地化的。永遠不可能給出一個好的一般答案。每個示例都應該分別進行分析。它涉及很多技術問題。只要C++編譯器不產生可見的副作用（無論正是這種方式），就允許C++編譯器按照自己的意願實際修改程序。所以只要你的計算結果相同就可以了。這在技術上允許將您的程序的一個版本轉換爲等效，即使是遞歸版本，也可以將其轉換爲基於循環的版本，反之亦然。所以它取決於編譯器優化和編譯器的努力。

此外，要比較一個版本與另一個版本，您需要證明您比較的版本實際上是相同的。

如果對編譯器進行優化更容易，也可能發生某種算法的遞歸實現比基於循環的算法快。通常迭代版本更復雜，通常代碼越簡單，編譯器就越容易優化，因爲它可以假設不變量等。

Answer 3

您的「遞歸修改」版本沒有遞歸所有。

事實上，啓用一個非遞歸版本的唯一東西就是在你的主函數中填充一個新條目 - 因此它實際上是一個使用迭代的解決方案（支持immibis和BlastFurnace注意到這一點）。

但是你的版本甚至沒有做到這一點。相反，因爲它總是以i == 0調用，所以它非法讀取F[-1]和。你很幸運（？）該程序沒有崩潰。

您得到正確結果的原因是整個F陣列都預裝了正確的版本。

無論如何，您計算Fib（2000 ....）的嘗試並不成功，因爲您溢出了double。你甚至嘗試運行該代碼？

這是一個能夠正常工作的版本（精確到double，無論如何）並且不使用全局數組（它實際上是迭代vs遞歸而不是迭代vs記憶）。

#include <cstdio> 
#include <ctime> 
#include <utility> 


double FiboIterative(int n) 
{ 
    double a = 0.0, b = 1.0; 

    if (n <= 0) return a; 

    for (int i = 2; i <= n; i++) 
    { 
     b += a; 
     a = b - a; 
    } 
    return b; 
} 

std::pair<double,double> FiboRecursive(int n) 
{ 
    if (n <= 0) return {}; 

    if (n == 1) return {0, 1}; 

    auto rec = FiboRecursive(n-1); 

    return {rec.second, rec.first + rec.second}; 
} 

int main(void) 
{ 
    const int repetitions = 1000000; 
    const int n = 100; 
    volatile double result; 

    std::puts("----------------Iterative--------------"); 
    std::clock_t tStart = std::clock(); 
    for(int i = 0; i < repetitions; ++i) 
     result = FiboIterative(n); 
    std::printf("[%d] = %f\n", n, result); 
    std::printf("Time taken: %.2f us\n", (std::clock() - tStart)/1.0/CLOCKS_PER_SEC); 

    std::puts("----------------Recursive--------------"); 
    tStart = std::clock(); 
    for(int i = 0; i < repetitions; ++i) 
     result = FiboRecursive(n).second; 
    std::printf("[%d] = %f\n", n, result); 
    std::printf("Time taken: %.2f us\n", (std::clock() - tStart)/1.0/CLOCKS_PER_SEC); 
    return 0; 
} 

-

可以說任何隱藏的錯誤實際上是不吉利的。