c++ - 循环真的比递归快吗？

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存储在堆栈中，以便与fact(n-1)的结果相乘。这基本上发生在堆栈展开期间。现在检查以下实现。

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

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

}

在这种方法中，我们将计算结果传递到变量 result 中。所以最后我们直接在变量result中得到答案。在这种情况下，您唯一需要做的就是在初始调用中为结果传递值 1。堆栈可以直接展开到它的第一个条目。当然，我不确定 C 或 C++ 是否允许尾递归检测，但函数式编程语言可以。