cppadvanced15 minutes

Implement a Memoized Recursive Function to Compute the nth Catalan Number

Create an efficient C++ function that calculates the nth Catalan number using recursion with memoization. Catalan numbers appear in various combinatorial problems and grow quickly, so naive recursion is inefficient for larger inputs.

Challenge prompt

Write a C++ function named `catalan` that takes an integer `n` and returns the nth Catalan number. Your solution must use recursion combined with memoization to optimize repeated subproblems. The Catalan numbers are defined as: C0 = 1 and for n > 0: Cn = sum of Ci * C(n-1-i) for i from 0 to n-1. Implement memoization either internally (static or global) or by passing a data structure as argument.

Guidance

• Use a helper function or static data structure to cache results for previously computed values.
• Recall the recursive formula: Cn = Σ (Ci * C(n - 1 - i)) for i in [0 .. n-1] with C0 = 1.
• Optimize to avoid recomputation that leads to exponential time complexity.

Hints

• Consider using a std::unordered_map or std::vector for memoization storage indexed by n.
• Make sure to handle the base case correctly to stop infinite recursion.
• Memoization can radically improve performance from exponential to polynomial.

Starter code

long long catalan(int n) {
    // Implement your memoized recursive solution here
}

Expected output

catalan(0) = 1 catalan(5) = 42 catalan(10) = 16796

Core concepts

recursionmemoizationdynamic programmingcombinatorics

Challenge a Friend

Send this duel to someone else and see if they can solve it.