0

I need to define this function n_choose_k(n,k) which returns the value of n choose k and number of recursive calls made as a tuple, while keeping in mind the following:

The number of recursive calls should not include the initial function call.

the function returns (-1,0) if:

  • k is negative
  • n is negative
  • n is less than k

Here is what I have so far:

def n_choose_k(n, k):
    if k == 0 or k == n:
        return 1,0
    
    elif n < k or k < 0 or n < 0:
        return -1,0
    
    return n_choose_k(n-1,k) + n_choose_k(n-1, k-1)


    >>> print(n_choose_k(5,2))
    (10, 18) ---> Expected
    (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0) ---> Getting
Madeye Alastor Moody
  • 11
  • 5
  • What does the 18 do? If you just do `print(sum(n_choose_k(5,2)))` then you get 5 choose 2 which is 10. – ramzeek Jan 28 '22 at 04:37
  • 18 is the number of recursive calls made. The function returns the value of n choose k and number of recursive calls made as a tuple – Madeye Alastor Moody Jan 28 '22 at 04:39
  • i think you will find [this Q&A](https://stackoverflow.com/a/53464291/633183) helpful. let me know if you have any questions. – Mulan Jan 28 '22 at 06:26
  • In that case you could just do something like `a=n_choose_k(5,2)` and then `print(sum(a), len(a)-2` (see Kevin's answer). – ramzeek Jan 28 '22 at 12:34

1 Answers1

1

Your issues are with the lines return 1,0 and return n_choose_k(n-1,k) + n_choose_k(n-1, k-1). Python lists (in this case you can think of them as such) get appended when you added them. For example

>>> [1,2,3] + [3,4]
[1, 2, 3, 3, 4]

So in this case, all of your 1,0's are being added together. (If you exclude the initial function call values, 2, from the total number of inputs, 20, you should get the desired 18 as the number of recursive calls).

I expect you were thinking this happens in Python.

# INCORRECT, FALSE Python
>>> [1,2,3] + [3,4,5]
[4,6,8]

If you're using Numpy arrays, this can work

# With Numpy
>>> import numpy as np
>>> np.array([1,2,3]) + np.array([3,4,5])
np.array([4,6,8])

So you have options, either modify your code such that your recursion doesn't append lists or use Numpy.

Kevin M
  • 158
  • 10
  • Thank you for the clarification! However, I'm not sure how I can modify the code so it actually returns the value and the number of recursive calls – Madeye Alastor Moody Jan 28 '22 at 18:23
  • I don't want to give too much away, since I presume this is an assignment. One option is to have a helper function and to pass a counter from function to function. This could keep track of the number of recursive calls and you can return the value at the same time. – Kevin M Jan 29 '22 at 01:26