3

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.

Improve this question
9
  • 2
    Your calls, e.g. c(2, 5) means that n=2 and k=5 (as per definition of c at the top). So n<k and as such the result should be 0. Are you sure that the arguments of your example test case has the correct order? Commented May 29, 2013 at 20:07
  • 2
    What @poke said: you define C(n, k) but invoke C(k, n). poke, please make an answer out of your comment. Commented May 29, 2013 at 20:09
  • 4
    The non-recursive solution is much easier and better. For example C(10,5) = (10*9*8*7*6)/(5*4*3*2*1) Commented May 29, 2013 at 20:10
  • @shiplu.mokadd.im: the recursive solution will probably perform better on very large values of n without integer overflows. Commented May 29, 2013 at 20:11
  • 2
    @9000 before integer overflow the stack-overflow will occur on recursive solution. Commented May 29, 2013 at 20:13

3 Answers 3

Reset to default
6

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

I think you mean this: 

>>> c(2, 1)
2
>>> c(5, 2)
10
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Paul, your edit is incorrect. I had it right the first time. C(1, 2) should return zero.
@duffymo: the current edit has C(2,1) giving two different values.
I see that Tom. Paul Woolcock is the eejit who insists on switching it back, in spite of my protest. What can you do? I didn't write it that way. I'm sure he understands neither the code nor my answer.
5

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.

Improve this answer

Comments

4

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.