1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

use num::{BigInt, One};

pub fn catalan_recursive(n: usize) -> BigInt {
    match n {
        0 => BigInt::one(),
        _ => catalan_recursive(n - 1) * 2 * (2 * n - 1) / (n + 1),
    }
}

pub fn catalan_number(n: usize) -> BigInt {
    let mut m = Vec::with_capacity(n);
    m.push(BigInt::one());
    for i in 1..=n {
        let new = m.last().unwrap() * 2 * (2 * i - 1) / (i + 1);
        m.push(new);
    }
    m.pop().unwrap()
}