recursion - Pascal Triangle Recursive Program optimization in C++ -

i have built recursive function compute pascal's triangle values.

is there way optimize it?

short reminder pascal's triangle: c(n, k) = c(n-1, k-1) + c(n-1, k) code is:

int pascal(int n, int k) { if (k == 0) return 1; if (n == 0) return 0; return pascal(n - 1, k - 1) + pascal(n - 1, k); } 

the inefficiency see stores values twice. example: c(6,2) = c(5,1) + c(5,2) c(6,2) = c(4,0) + c(4,1) + c(4,1) + c(4,2) call c(4,1) twice

any idea how optimize function?

thanks

the following routine compute n-choose-k, using recursive definition , memoization. routine extremely fast , accurate:

inline unsigned long long n_choose_k(const unsigned long long& n,                                      const unsigned long long& k) {    if (n  < k) return 0;    if (0 == n) return 0;    if (0 == k) return 1;    if (n == k) return 1;    if (1 == k) return n;     typedef unsigned long long value_type;     class n_choose_k_impl    {    public:        n_choose_k_impl(value_type* table,const value_type& dimension)       : table_(table),       dimension_(dimension / 2)       {}        inline value_type& lookup(const value_type& n, const value_type& k)       {          const std::size_t difference = static_cast<std::size_t>(n - k);          return table_[static_cast<std::size_t>((dimension_ * n) + ((k < difference) ? k : difference))];       }        inline value_type compute(const value_type& n, const value_type& k)       {          // n-choose-k = (n-1)-choose-(k-1) + (n-1)-choose-k          if ((0 == k) || (k == n))             return 1;          value_type v1 = lookup(n - 1,k - 1);          if (0 == v1)             v1 = lookup(n - 1,k - 1) = compute(n - 1,k - 1);          value_type v2 = lookup(n - 1,k);          if (0 == v2)             v2 = lookup(n - 1,k) = compute(n - 1,k);          return v1 + v2;       }        value_type* table_;       const value_type dimension_;    };     static const std::size_t static_table_dim = 100;    static const std::size_t static_table_size = static_cast<std::size_t>((static_table_dim * static_table_dim) / 2);    static value_type static_table[static_table_size];    static bool static_table_initialized = false;     if (!static_table_initialized && (n <= static_table_dim))    {       std::fill_n(static_table,static_table_size,0);       static_table_initialized = true;    }     const std::size_t table_size = static_cast<std::size_t>(n * (n / 2) + (n & 1));     unsigned long long dimension = static_table_dim;    value_type* table = 0;     if (table_size <= static_table_size)       table = static_table;    else    {       dimension = n;       table = new value_type[table_size];       std::fill_n(table,table_size,0ll);    }     value_type result = n_choose_k_impl(table,dimension).compute(n,k);     if (table != static_table)       delete [] table;     return result; }