# Can you explain this recursive "n choose k" code to me? - Python

TAGS :
Viewed: 3 - Published at: a few seconds ago

#### [ Can you explain this recursive "n choose k" code to me? ]

Here is the code to a subset problem with arguments n and k. n represents the total number of students and k represents the amount of the students I want to get out of n. The code attempts to give the number of possible combinations of pulling k number of students out of n number of students.

``````def subset(n, k):
if k == 0:
return 1
if n == k:
return 1
else:
return subset(n-1, k-1) + subset(n-1, k)
``````

I understand the first part of the recursive call, but I'm having trouble understanding the + subset(n-1, k) part. Can anyone explain this to me?

The recursion is based on a simple observation, for which I will give a combinatorial argument, as to why it is true, rather than a mathematical proof through formulae.

Whenever you choose `k` elements out of `n`, there are two cases:

1. You choose element `#n`
2. You don't choose element `#n`

Since these events are mutually exclusive, the total amount of combinations is given by the amount of combinations when choosing `#n`, and those when you don't choose `#n`.

## Choosing element `#n`

Since we have already chosen one element, we need only choose another `k-1` elements. Also, since we have decided upon one element – as to whether it is included or not – already, we only need to consider the remaining `n-1` elements.

Thus, the amount of combinations for choosing element `#n` is given by

``````    subset(n - 1, k - 1)
``````

## Not choosing element `#n`

There are still `k` elements to choose, but since we have already made up our mind about element `#n`, there remain only `n - 1` elements to choose from. Thus:

``````    subset(n - 1, k)
``````

## The base case

The recursion uses the fact, that we can usually differentiate between two situations, solutions where element `n` is part of that solution, and those where it is not.

However, such a distinction can not always be made:

• When choosing all elements
• or when choosing no elements at all

In these cases, there is only exactly one solution, hence

``````if k == 0:
return 1
if n == k:
return 1
``````

## Ensuring it works

To do that, we need to convince ourselves (or prove) that the base case is always hit at some point.

Let us assume, that `n < k` at some point. Since per our assumption, `n` was originally greater or equal to `k`, there must have been some point where `n = k`, because `n` and `k` decrease in unison or only `n` decreases by one, i.e. it follows

This implies, that there must have been a call to `subset(n - 1, k)` for it to happen, that `n` decreases below `k`. However, this is not possible since we have a base case on `n = k` where we return a constant `1`.

We conclude that either `n` decreases at some point such that `n = k`, or decrease in unison exactly `k` times such that `k = 0`.

Thus, the base case works.

``````(n, k) = (n-1, k-1) + (n-1, k) with all (n, 0) and (n, n) having a value of 1.