Recursive functions are slower than their non-recursive counterpart

Question

I used a recursive function for the factorial of a Fibonacci number and series (Done in C ++), and I found that the recursive function of the factorial works fine as expected, and the execution speeds are not much different.

However, at Fibonacci, this happens slowly. Why is this so?

Recursive approach:

unsigned long int fib_num(int n)  //This is My code
{
    switch (n)
    {
    case 1:
        return 0;
        break;
    case 2:
        return 1;
        break;
    default:
        return fib_num(n - 1) + fib_num(n - 2);
        break;
    }
}

Iterative approach:

first = 0;
second = 1

for(i = 0; i < num; i++)   
{
    cout<<"\n"<<first;

    next = first + second;

    first = second;
    second = next;
}

Answer 1

Your observation is correct, the recursive approach to calculating Fibonacci numbers in this case, if you look carefully, calculates each Fibonacci term from the very beginning, i.e.

To calculate F [n] + F [n-1], for example, the function calculates both terms separately and performs the same task several times.

: F [5] = F [4] + F [3]

F [3]: : F [2], F [1], F [1], F [0]

F [4]: ​​ : F [2], F [2], F [1], F [1], F [0], F [0] F [3]/p >

:

, , , : O (2 ⁿ).

---

- memoization:

// header needed for the container: map
#include <map> 

int mem_fact (int i, std::map<int, int>& m)
{
    // if value with key == i does not exist in m: calculate it
    if (m.find(i) == m.end()) 
    {
        // the recursive calls are made only if the value doesn't already exist
        m[i] = mem_fact (i - 1, m) + mem_fact (i - 2, m); 
    }

    // if value with key == i exists, return the corresponding value
    return m[i];
}

int fast_factorial (int i)
{
    // key (Fibonacci index) - value (Fibbonaci number)
    std::map<int, int> memo;

    // initialize the first two Fibonacci numbers
    memo.insert(std::pair<int,int>(0, 0));
    memo.insert(std::pair<int,int>(1, 1));

    return mem_fact(i, memo);
}

: main() fast_factorial(num_of_fib);