maximum recursion depth exceeded in comparison

Question

I wrote this piece of code to compute the number of combinations:

def fact(n):
    return 1 if(n == 1) else n * fact(n - 1)

def combinations(n,k):
    return fact(n)/((fact(n - k) * fact(k)))

while(True):
    print(combinations(int(input()), int(input())))

The factorial function seems to work fine. But why does it give me a maximum recursion depth exceeded in comparison error when I try to find the combinations of two numbers? Is there something wrong with the factorial function, since that's where the error seems to be originating from?

This was the error I got:

builtins.RuntimeError: maximum recursion depth exceeded in comparison

Solution 1

Try to replace:

def fact(n):
    return 1 if(n == 1) else n * fact(n - 1)

to:

def fact(n):
    return 1 if(n <= 1) else n * fact(n - 1)

Because if you pass 2 identical numbers, you would try to compute fact(0) (which would call fact(-1) and fact(-2), etc until the maximum recursion depth error).

Solution 2

You should try to avoid recursion for such a simple function as the factorial of a number. Recursion is really powerful, but sometimes it is overused for no reason.

Here is the code for the iterative version of factorial function:

def fact(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Notice what Maxime says in the previous answer, that is exactly the problem you are having: your function doesn't contemplate the factorial of 0.

Solution 3

The default recursion limit in python 3.x version onwards is 2000 only, If you call the same function again and again more than 2000 times, you will get maximum recursion depth error. The ideal approach would be to write a logic without recursion. But If you still stick to recursion, change the default recursion limit by:

import sys

sys.setrecursionlimit(10000)# It sets recursion limit to 10000.

But the above may not meet all your needs in certain contexts.

Solution 4

Your Recursion depth out of the limit.

1. Recursion is not the most idiomatic way to do things in Python, as it doesn't have tail recursion optimization thus making impractical the use of recursion as a substitute for iteration (even if in your example the function is not tail-recursive, that wouldn't help anyway). Basically, that means that you shouldn't use it for things that have a complexity greater than linear if you expect your inputs to be large.

2. If you have a platform that supports a higher limit, you can set the limit higher:

   sys.setrecursionlimit(some_number) sys.setrecursionlimit(some_number)

   This function set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care because a too-high limit can lead to a crash.

ref:
Python recursive function error: “maximum recursion depth exceeded”
Python max recursion , question about sys.setrecursionlimit()

View more solutions