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