Как лучше рассчитать nCr

Подход 1:
C (n,r )= n!/ (n -r )!r!

Подход 2:
В книге Комбинаторные алгоритмы Уилфа я нашел это:
C (n,r )можно записать как C(n-1,r) + C(n-1,r-1).

например.

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
      .  .
      .  .
      .  .
      .  .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

Как видите, окончательное решение не требует умножения. В каждой форме C (n,r )либо n==r, либо r==1.

Вот пример кода, который я реализовал:

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

См. вывод здесь.

В подходе 2 есть перекрывающиеся подзадачи -, когда мы вызываем рекурсию для повторного решения тех же подзадач -. Мы можем избежать этого, используя динамическое программирование .

Я хочу знать, как лучше вычислить C (n,r )?.