循环是否比递归更快？

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; 
} 

-

可以说任何隐藏的错误实际上是不吉利的。