Are loops really faster than recursion?

Question

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.

Here's the code:

#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

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.

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

}

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

}

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.

Answer 2

Your "recursion modified" version doesn't have recursion at all.

In fact, the only thing enabling a non-recursive version that fills in exactly one new entry of the array is the for-loop in your main function -- so it is actually a solution using iteration also (props to immibis and BlastFurnace for noticing that).

But your version doesn't even do that correctly. Rather since it is always called with i == 0, it illegally reads F[-1] and F[-2]. You are lucky (?)¹ the program didn't crash.

The reason you are getting correct results is that the entire F array is prefilled by the correct version.

Your attempt to calculate Fib(2000....) isn't successful anyway, since you overflow a double. Did you even try running that code?

Here's a version that works correctly (to the precision of double, anyway) and doesn't use a global array (it really is iteration vs recursion and not iteration vs memoization).

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

--

¹Arguably anything that hides a bug is actually unlucky.

Answer 3

I don't think this is not a good question. But maybe the answer why is somehow interesting.

At first let me say that generally the statement is probably true. But ...

Questions about performance of c++ programs are very localized. It's never possible to give a good general answer. Every example should be profiled an analyzed separately. It involves lots of technicalities. c++ compilers are allowed to modify program practically as they wish as long as they don't produce visible side effects (whatever precisely that means). So as long as your computation gives the same result is fine. This technically allows to transform one version of your program into an equivalent even from recursive version into the loop based and vice versa. So it depends on compiler optimizations and compiler effort.

Also, to compare one version to another you would need to prove that the versions you compare are actually equivalent.

It might also happen that somehow a recursive implementation of algorithm is faster than a loop based one if it's easier to optimize for the compiler. Usually iterative versions are more complex, and generally the simpler the code is, the easier it is for the compiler to optimize because it can make assumptions about invariants, etc.