Следующий рекурсивный алгоритм - это (довольно неэффективный) способ вычисления n, выбирающего k:

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

Он основан на следующем рекурсивном понимании:

На самом деле оценка этой функции требует много вызовов функций. Например, вычисление 2 выбирает 2 таким образом, делает эти вызовы:

 combinationsOf(2, 2)
   |  |
   |  +- combinationsOf(1, 2)
   |       |  |
   |       |  +- combinationsOf(0, 2)
   |       |
   |       +-- combinationsOf(1, 1)
   |             |  |
   |             |  +- combinationsOf(0, 1)
   |             |
   |             +- combinationsOf(1, 0)
   +- combinationsOf(2, 1)
        |  |
        |  +- combinationsOf(2, 0)
        |
        +- combinationsOf(1, 1)
             |  |
             |  +- combinationsOf(0, 1)
             |
             +- combinationsOf(1, 0)

Естьмного способы улучшить время выполнения этой функции - мы могли бы использовать динамическое программирование, использовать формулу замкнутой формы nCk = n! / (k! (n - k)!) и т. д. Впрочем, мне просто любопытнокак неэффективен этот конкретный алгоритм.

Какова временная сложность этой функции в зависимости от n и k?