I have written two functions for Fibonacci numbers, one using recursion and the second using memorization(dynamic programming). Since the 2nd is using dp so it should run faster than the first one but the fact is the 2nd one takes more time than the 1st one.

Please correct me, if I have done some mistakes while writing functions.

Thanks in advance :)

Function 1:

Function 2:

CodePudding user response：

long fib(int n, unordered_map<int, long>& mp) will be faster. Notice the & which passes the map by reference. This avoids a costly copy, and most importantly, avoids the modifications to the map from being lost.

CodePudding user response：

You are passing the std::unordered_map by value. This means your code will always skip the if statements and go straight to fetching the Fibonacci number using the recursive function. You are still using the function that you thought you had avoided (at least when trying to fetch the same number twice from the unordered_map) which has its own cost plus the cost of setting up the stack frame of the function and copying the map each time. The second function is indeed slower.

Pass the unordered_map as a reference to avoid copying and most importantly, save the changes or the new values to the map.

long fib(int n, unordered_map<int, long> &mp)