Realization of combination on C++

the following source code make many recursive overheads.

We can see the redundancy happened.

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

#include <iostream> using namespace std;   int combination(int n, int r);   void main(){     cout<<combination(7,3); }   int combination(int n, int r){       if( (n==r) || (r ==0) ) return 1;          return combination(n-1,r-1) + combination(n-1,r); }

In order to reduce these redundancy, we can use previous value which was calculated before.

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

#include <iostream> using namespace std;   const int MAX = 20;   int combination(int n, int r);   void main(){     cout<<combination(7,3); }   int combination(int n, int r){     static int memo[MAX][MAX];       if( memo[n][r] >0 ) return memo[n][r];       if( (n==r) || (r ==0) ) return memo[n][r] = 1;;          return memo[n][r] = combination(n-1,r-1) + combination(n-1,r); }

The static int value are initialized to 0;