循环真的比递归快吗? [英] Are loops really faster than recursion?

问题描述

据我的Professor循环比使用递归更快，更不足，但是我想出了这个c ++代码，它使用递归和循环来计算斐波那契数列，结果证明它们非常相似.因此，我最大化了可能的输入，以查看性能是否存在差异，并且出于某种原因，递归比使用循环更好.有人知道为什么吗?谢谢你.

According to my professor loops are faster and more deficient than using recursion yet I came up with this c++ code that calculates the Fibonacci series using both recursion and loops and the results prove that they are very similar. So I maxed the possible input to see if there was a difference in performance and for some reason recursion clocked in better than using a loop. Anyone know why? Thanks in advanced.

代码如下:

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

推荐答案

按照常规的编程方法，循环会更快.但是有一类语言称为函数编程语言，其中不包含循环.我是函数式编程的忠实拥护者，并且是Haskell的狂热用户.Haskell 是一种函数式编程语言.在此而不是循环中，您使用递归.为了实现快速递归，有一种称为 tail recursion 的方法.基本上是为了防止向系统堆栈提供很多额外的信息，您可以这样编写函数:将所有计算都存储为函数参数，这样，除了函数调用指针之外，不需要在堆栈上存储任何内容.因此，一旦调用了最后的递归调用，程序就无需移出堆栈，而只需转到第一个函数调用堆栈条目即可.函数式编程语言编译器具有内置的设计来处理此问题.现在，即使非功能性编程语言也实现了尾递归.

You you go by the conventional programming approach loops are faster. But there is category of languages called functional programming languages which does not contain loops. I am a big fan of functional programming and I am an avid Haskell user. Haskell is a type of functional programming language. In this instead of loops you use recursions. To implement fast recursion there is something known as tail recursion. Basically to prevent having a lot of extra info to the system stack, you write the function such a way that all the computations are stored as function parameters so that nothing needs to be stored on the stack other that the function call pointer. So once the final recursive call has been called, instead of unwinding the stack the program just needs to go to the first function call stack entry. Functional programming language compilers have an inbuilt design to deal with this. Now even non functional programming languages are implementing tail recursion.

例如，考虑找到用于找到正数阶乘的递归解.C语言的基本实现是

For example consider finding the recursive solution for finding the factorial of a positive number. The basic implementation in C would be

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

}

在以上方法中，每次调用堆栈n时，都会将其存储在堆栈中，以便可以将它与事实(n-1)的结果相乘.这基本上是在堆栈展开期间发生的.现在检查以下实现.

In the above approach, each time the stack is called n is stored in the stack so that it can be multiplied with the result of fact(n-1). This basically happens during stack unwinding. Now check out the following implementation.

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

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

}

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

In this approach we are passing the computation result in the variable result. So in the end we directly get the answer in the variable result. The only thing you have to do is that in the initial call pass a value of 1 for the result in this case. The stack can be unwound directly to its first entry. Of course I am not sure that C or C++ allows tail recursion detection, but functional programming languages do.

这篇关于循环真的比递归快吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！