find the nth catalan number in rust

To find the nth Catalan number in Rust, there are two common approaches, recursion and dynamic programming (memoization).

Recursion Approach

The recursion approach involves directly implementing the recursive formula for Catalan numbers:

C(n) = (2n)! / [(n+1)!n!]

We can translate this to Rust code as follows:

main.rs
fn catalan_number_recursive(n: u32) -> u64 {
    if n == 0 {
        return 1;
    }
    let mut c: u64 = 0;
    for i in 0..n {
        c += catalan_number_recursive(i) * catalan_number_recursive(n - i - 1);
    }
    return c;
}
231 chars
11 lines

This function recursively calls itself to calculate the Catalan number. The base case is when n is 0, and the function returns 1. For all other n values, the function uses a for loop that calculates Catalan numbers based on previously computed results.

Dynamic Programming Approach

The dynamic programming approach involves using an array to store previously computed results so that we can avoid repeating computations.

main.rs
fn catalan_number_dynamic(n: usize) -> u64 {
    let mut catalan = vec![0u64; n+1];
    catalan[0] = 1;
    for i in 1..=n {
        for j in 0..i {
            catalan[i] += catalan[j] * catalan[i-j-1];
        }
    }
    catalan[n]
}
237 chars
11 lines

In this approach, we start by initializing an array with zeros, representing all possible values of Catalan numbers up to n. We set the value of the first element to 1 (C(0) = 1) since it is a base case. We then use two nested loops to update the remaining elements of the array and compute the nth Catalan number.

Both approaches can be used to calculate the nth Catalan number. The dynamic programming approach is preferred for large n values since it avoids repeating computations, making it more efficient.