Why is the memoized solution slower than the normal recursive solution?

Question

I was implementing a function to compute the nth Catalan number. The formula for the sequence is the following:

I noticed that the memoized solution was slower than the normal recursive solution. This is my code:

#include <bits/stdc++.h>
using namespace std;


int catalan_number_recursive(int n){
    if (n == 0) return 1;

    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_recursive(i)*catalan_number_recursive(n - 1 - i);
        }

        return ans;
    }
}

int catalan_number_memo(int n, map<int, int> memo){
    memo[0] = memo[1] = 1;


    if (memo.count(n) != 0){
        return memo[n];
    }
    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_memo(i, memo)*catalan_number_memo(n - 1 - i, memo);
        }

        memo[n] = ans;
        
        return memo[n];
    }
    

}

int main(){

    printf("Catalan Numbers - DP\n\n");

    int num = 12;

    auto start1 = chrono::high_resolution_clock::now();
    printf("%dth catalan number (recursive) is %d.\n", num, catalan_number_recursive(num));
    auto finish1 = chrono::high_resolution_clock::now();

    chrono::duration<double> elapsed1 = finish1 - start1;

    cout << "Time taken: " << elapsed1.count() << "s.\n\n";

    auto start2 = chrono::high_resolution_clock::now();
    printf("%dth catalan number (memo) is %d.\n", num, catalan_number_memo(num, {}));
    auto finish2 = chrono::high_resolution_clock::now();

    chrono::duration<double> elapsed2 = finish2 - start2;

    cout << "Time taken: " << elapsed2.count() << "s.\n";

    return 0;
}

The output of the code for n = 12 is:

Catalan Numbers - DP

12th catalan number (recursive) is 208012.
Time taken: 0.006998s.

12th catalan number (memo) is 208012.
Time taken: 0.213007s.

Also, when I try with n = 20, it gives me a negative value, which is not correct, but for smaller values it is correct. Thank you for your answer.

Answer 1

#include <bits/stdc++.h>
using namespace std;
int catalan_number_recursive(int n){
    if (n == 0) return 1;
    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_recursive(i)*catalan_number_recursive(n - 1 - i);
        }

        return ans;
    }
}

int catalan_number_memo(int n, map<int, int>& memo){
    memo[0] = memo[1] = 1;


    if (memo.count(n) != 0){
        return memo[n];
    }
    else{
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += catalan_number_memo(i, memo)*catalan_number_memo(n - 1 - i, memo);
        }
        memo[n] = ans;
        return memo[n];
    }
}

int main(){

    printf("Catalan Numbers - DP\n\n");

    int num = 12;

    auto start1 = chrono::high_resolution_clock::now();
    printf("%dth catalan number (recursive) is %d.\n", num, catalan_number_recursive(num));
    auto finish1 = chrono::high_resolution_clock::now();

    chrono::duration<double> elapsed1 = finish1 - start1;

    cout << "Time taken: " << elapsed1.count() << "s.\n\n";

    auto start2 = chrono::high_resolution_clock::now();
    map<int, int> m;
    printf("%dth catalan number (memo) is %d.\n", num, catalan_number_memo(num, m));

    chrono::duration<double> elapsed2 = finish2 - start2;

    cout << "Time taken: " << elapsed2.count() << "s.\n";

    return 0;
}

Here is your code but with one single change - the map (it is now map<int, int>&) is passed by mutable reference instead of a value.

What was happening is that previously the program was copying the map and passing the copied map as the recursive argument everytime, so

0: You do not really memorized anything. at every return point the learned value is only put into a map that is unique to that function, so there is no learning across calls. It is still exponential.

1: It is very slow. At every recursion you copy the whole data structure, while the original code only has a loop sum.

Now that I fixed it, the program run as below:

Catalan Numbers - DP

12th catalan number (recursive) is 208012.
Time taken: 0.00236639s.

12th catalan number (memo) is 208012.
Time taken: 0.000103588s.