Recursion binomial coefficient

Question

I have to define a function that takes two numbers: n and k (n >= k) and returns the binomial coefficent of these two numbers.

#defining a function that computes the factorial of an integer

def fac(b):
    if b==1:
        return 1
    else:
        return b * fac(b-1)

#takes two integers and does the binomial coefficient operand

def combinations(n,k):
    result = (fac(n)) / (fac(k) * fac(n-k))
    return result

n=10
k=2

print(combinations(n,k))

This works well for small numbers, but when I take larger numbers such as 1000 etc, it doesn't work. It returns: line 5 in fac return b * fac(b-1) several times. Followed by: RuntimeError: maximum recursion depth exceeded in comparison.

Can someone explain why these functions doesn't work with large numbers and perhaps give any tips on what I can do to solve this problem? How does python deal with recursion and large numbers?

A much better solution would use memoization of doubles from the natural log of the gamma function, eschewing recursion and integers. — duffymo
– duffymo, Commented Oct 15, 2014 at 17:14
Please don't ask two completely unrelated questions at once. — Fred Foo
– Fred Foo, Commented Oct 15, 2014 at 17:15
What do you mean by "it doesn't work"? Too slow? Recursion depth exceeded? Anything else? — uselpa
– uselpa, Commented Oct 15, 2014 at 17:15
@uselpa It returns: line 5 in fac return b * fac(b-1) several times. Followed by: RuntimeError: maximum recursion depth exceeded in comparison — raspberrysupreme
– raspberrysupreme, Commented Oct 15, 2014 at 17:16

uselpa · Accepted Answer · 2014-10-15 17:46:45Z

2

Python limits the recursion depth to 1000 by default. You can change that by adding the following at the beginning of your code (setting the limit to 2000 in this example):

import sys
sys.setrecursionlimit(2000)

To ask the user for input, try:

n=int(input("Enter n:"))
k=int(input("Enter k:"))

So here's the full code (just copy/paste it):

import sys
sys.setrecursionlimit(2000)

def fac(b):
    if b==1:
        return 1
    else:
        return b * fac(b-1)

def combinations(n,k):
    result = (fac(n)) / (fac(k) * fac(n-k))
    return result

n=int(input("Enter n:"))
k=int(input("Enter k:"))

print(n, k, combinations(n,k))

edited Oct 15, 2014 at 17:46

answered Oct 15, 2014 at 17:26

uselpa

19k2 gold badges36 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

raspberrysupreme Over a year ago

I tried my function with n=999 and k=10. Still recursion depth exceeded.

uselpa Over a year ago

Works fine for me. What limit did you set?

uselpa Over a year ago

You mean you didn't set the recursion limit to, say, 2000 as I showed in my answer? If so, why not?

uselpa Over a year ago

I posted the whole code in my answer. Try to copy/paste it (entirely!). It works fine for me with 999 and 10.

raspberrysupreme Over a year ago

Okay, first: It did work with both eval & int, so thanks for that. Second: You said python has limit the recursion depth to 1000, that means that it can take numbers less the 1000, right? I tried with 999, didn't work. When I used: import sys sys.setrecursionlimit(2000) everything worked great, but is there another way to make this work without importing? Thanks. @uselpa

|

Collectives™ on Stack Overflow

Recursion binomial coefficient

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related