求计算组合数NCK的递归代码的时间与空间复杂度

First, let's recap what this code does: it calculates the binomial coefficient ( C(n,k) ) (the number of ways to choose k elements from a set of n) using the standard recursive formula:

( C(n,k) = C(n-1,k-1) + C(n-1,k) )

It includes handy optimizations for edge cases to avoid unnecessary recursion:

• Returns 1 immediately if ( k=0 ) or ( k=n ) (there's only one way to choose nothing or everything)
• Returns n immediately if ( k=1 ) (choosing one element from n has exactly n options)

Time Complexity #

This implementation suffers from massive redundant subproblem calculations, which makes its time complexity exponential:

• Worst Case: When ( k \approx n/2 ), the binomial coefficient is at its largest, and the recursive tree expands fully. Here, time complexity hits ( O(2^n) ). You'll see globalhitsToThisMethod skyrocket here because nearly every subproblem gets computed multiple times.
• Best Case: For ( k=0 ), ( k=n ), or ( k=1 ), we hit the base cases instantly—no recursion needed. Time complexity here is ( O(1) ).
• General Case: Since ( C(n,k) = C(n, n-k) ), the amount of redundant work depends on the smaller of k and n-k. So time complexity simplifies to ( O(2^{\text{min}(k, n-k)}) ).

For your example with ( n=61, k=55 ), this is equivalent to calculating ( C(61,6) )—which is way more efficient than ( C(61,30) ), but still exponential under the hood.

Space Complexity #

Space complexity is driven entirely by the depth of the recursive call stack:

• Each recursive call adds a new frame to Java's call stack. The maximum depth of this stack is the number of steps needed to reach a base case. For ( C(n,k) ), that's either the steps to get to ( C(n-k, 0) ) or ( C(k,k) ), which is at most n steps. So space complexity is ( O(n) ) in the worst case.
• There's no extra memory used for caches or data structures here—just the stack space for recursive calls.

Quick Optimization Note #

The reason this code is slow for larger n/k is that it doesn't cache already computed results. If you add memoization (like a 2D array or hash map to store ( C(n',k') ) values once calculated), you can drop the time complexity to ( O(nk) )—this would drastically reduce the value of globalhitsToThisMethod by eliminating redundant work.

内容的提问来源于stack exchange，提问作者Aditya Goel