循环真的比递归快吗？

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++ 是否允许尾递归检测，但函数式编程语言可以。