以下递归算法是一种计算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的函数的big-O时间复杂度是多少？
当n k，则通过命中k = 0停止递归操作，k的步数少于n = 0，但是总体复杂度仍为2 ^ n。
但是真正的问题是递归本身-您很快就会达到堆栈限制。
Let
C(n,k)be the cost of computingbinom(n,k)in that way, with作为基本案例。
复发明显
如果我们用加法得到成本1。那么，我们可以轻松地检查
通过归纳。
So for
k >= n, the cost is2^(n+1) - 1,C(n,n-1) = 2^(n+1)- 3,C(n,1) = 2*n+1,C(n,2) = n*(n+1)+1, (and beyond that, I don't see neat formulae).我们有明显的上限
independent of
k, and fork < n/2we can coarsely estimatewhich gives a much smaller bound for small
k, so overall(need to clamp the
kfor the minimum, sincebinom(n,k)decreases back to 1 fork > n/2).