CODEWITHSUNDEEP
pythonrecursionpython-3.x
Snarre
Snarre

Reputation: 597

How many combinations are possible?

The recursive formula for computing the number of ways of choosing k items out of a set of n items, denoted C(n,k), is:

           1                    if K = 0
C(n,k) = { 0                    if n<k
           c(n-1,k-1)+c(n-1,k)  otherwise

I’m trying to write a recursive function C that computes C(n,k) using this recursive formula. The code I have written should work according to myself but it doesn’t give me the correct answers.

This is my code:

def combinations(n,k):
    # base case
    if k ==0:
        return 1
    elif n<k:
        return 0
    # recursive case
    else:
        return combinations(n-1,k-1)+ combinations(n-1,k)

The answers should look like this:

>>> c(2, 1)
0
>>> c(1, 2)
2
>>> c(2, 5)
10

but I get other numbers... don’t see where the problem is in my code.

Upvotes: 3

Views: 2200

Answers (3)

duffymo
duffymo

Reputation: 308938

I would try reversing the arguments, because as written n < k.

I think you mean this: 

>>> c(2, 1)
2
>>> c(5, 2)
10

Upvotes: 6

AJMansfield
AJMansfield

Reputation: 4165

This is one of those times where you really shouldn't be using a recursive function. Computing combinations is very simple to do directly. For some things, like a factorial function, using recursion there is no big deal, because it can be optimized with tail-recursion anyway.

Here's the reason why:

Why do we never use this definition for the Fibonacci sequence when we are writing a program?

def fibbonacci(idx):
    if(idx < 2):
        return idx
    else:
        return fibbonacci(idx-1) + fibbonacci(idx-2)

The reason is because that, because of recursion, it is prohibitively slow. Multiple separate recursive calls should be avoided if possible, for the same reason.

If you do insist on using recursion, I would recommend reading this page first. A better recursive implementation will require only one recursive call each time. Rosetta code seems to have some pretty good recursive implementations as well.

Upvotes: 4

poke
poke

Reputation: 388023

Your calls, e.g. c(2, 5) means that n=2 and k=5 (as per your definition of c at the top of your question). So n < k and as such the result should be 0. And that’s exactly what happens with your implementation. And all other examples do yield the actually correct results as well.

Are you sure that the arguments of your example test cases have the correct order? Because they are all c(k, n)-calls. So either those calls are wrong, or the order in your definition of c is off.

Upvotes: 5

Related Questions