bench_open_recursion.cpp

#include <unordered_map>
#include <vector>

//------------------------------------------------------------------------

long long bst_count_classic(int n)
{
    if (n <= 1) return 1;
    
    std::vector<long long> memo(n+1, 0);
    memo[0] = memo[1] = 1;
    for (int k = 2; k <= n; ++k)
    {
        for (int i = 0; i < k; ++i)
        {
            memo[k] += memo[i] * memo[k-i-1];
        }
    }
    return memo.back();
}

//------------------------------------------------------------------------

template<typename Recur>
long long bst_count(Recur recur, int n)
{
    if (n <= 1) return 1;
    
    long long sub_counts = 0;
    for (int i = 0; i < n; ++i)
        sub_counts += recur(i) * recur(n - i - 1);
    return sub_counts;
}

//------------------------------------------------------------------------

long long best_count_fix_point(int n)
{
    return bst_count([](int k) { return best_count_fix_point(k); }, n);
}

long long bst_count_memo(int n)
{
    std::vector<long long> memo(n+1);
    for (int i = 0; i <= n; ++i)
        memo[i] = bst_count([&](int k) { return memo[k]; }, i);
    return memo.back();
}

//------------------------------------------------------------------------

static long long lazy_impl(std::vector<long long>& memo, int n)
{
    if (memo[n]) return memo[n];
    auto recur = [&](int k) { return lazy_impl(memo, k); };
    return memo[n] = bst_count(recur, n);
}

long long bst_count_lazy(int n)
{
    std::vector<long long> memo(n+1);
    return lazy_impl(memo, n);
}

//------------------------------------------------------------------------

static long long lazy_map(std::unordered_map<int, long long>& memo, int n)
{
    auto& computed = memo[n];
    if (computed) return computed;
    auto recur = [&](int k) { return lazy_map(memo, k); };
    return computed = bst_count(recur, n);
}

long long bst_count_map(int n)
{
    std::unordered_map<int, long long> memo;
    return lazy_map(memo, n);
}

//------------------------------------------------------------------------

template<typename TestFct>
static void bench_it(TestFct testFct)
{
    int runs = 100;
    int N = 1000;
    for (int i = 0; i < runs; ++i)
    {
        testFct(N);
    }
}

void example()
{
    bench_it(bst_count_memo);
    bench_it(bst_count_lazy);
    bench_it(bst_count_map);
    bench_it(bst_count_classic);
}