Recursion binomial coefficient

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?

---

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))

链接地址: http://www.djcxy.com/p/80680.html

上一篇: 编写一个程序来计算递归调用的数量

下一篇: 递归二项式系数