The faculty of two numbers python 3

Question

def choose (x, y):
     if y > x: 
        print ("False")
     elif y == 0 or y == x: 
        return 1
     elif y == 1:
        return x
     else:
        if (x-y) > y:
            biggest = x-y
            smallest = y
        else:
            biggest = y
            smallest = x-y
       resultatet = x * choose (x-1, biggest) 
    res = resultatet // smallest
    return res

My function is working perfectly with whatever x input I insert but with bigger Y inputs like 8000 for example I'm getting

  File "/home/nazel607/labb3b_2.py", line 20, in choose
resultatet = x * choose (x-1, biggest) 
  File "/home/nazel607/labb3b_2.py", line 3, in choose
if y > x: 
RuntimeError: maximum recursion depth exceeded in comparison

Is there a way I can overcome this problem or is it impossible in python due to its limits? Is there another way than increasing the limit?

Hi. Are you interested in finding a different way to calculate this value? Or do you want to know how to implement this specific algorithm, without coming up against this limitation? — jwg, Oct 09 '17 at 09:35
@jwg Hi, I'm more interested in finding a way to use this specific algorithm and overcome the problem of limitation — nazeeroo bu, Oct 09 '17 at 09:37
Have you seen [this](https://stackoverflow.com/questions/8177073/python-maximum-recursion-depth-exceeded)? — RolfBly, Oct 09 '17 at 09:40
Possible duplicate of [What is the maximum recursion depth in Python, and how to increase it?](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it) — user2390182, Oct 09 '17 at 09:41
Possible duplicate of [Python: Maximum recursion depth exceeded](https://stackoverflow.com/questions/8177073/python-maximum-recursion-depth-exceeded) — RolfBly, Oct 09 '17 at 09:42
@DavidG It is correct in my file but I'm not 100% sure if it got correct here when I copied the code — nazeeroo bu, Oct 09 '17 at 09:43

freakish · Accepted Answer · 2017-10-09T10:03:23.330

It seems that you can get rid of the recursion:

def choose2(x, y):
    if y > x:
        raise ValueError()

    if y == 0 or y == x:
        return 1

    if y == 1:
        return x

    result = 1
    while y != x:
        big, small = max(x-y, y), min(x-y, y)
        result *= x // small
        x -= 1
        y = big
    return result

I've tested it over few examples:

for x, y in [
    (4, 2),
    (17, 9),
    (125, 79),
    (8005, 13),
    (9005, 13),
    # (19005, 7004)  # exceeds max recursion depth on my machine
]:
    assert choose(x, y) == choose2(x, y)

and seems to work fine.

score -1 · Answer 2 · answered Oct 09 '17 at 09:49

-1

You are not exiting the program ...

def choose (x, y):
    if y > x: 
        print ("False")
        return
    # ...rest of your program

answered Oct 09 '17 at 09:49

ssm

5,277
1
24
42

You are right but i'm getting the exact same problem even after editing – nazeeroo bu Oct 09 '17 at 09:55
Python is preventing you from recursing too deep. Check out `https://docs.python.org/3/library/sys.html#sys.setrecursionlimit`. Python doesn't do tail recursion – ssm Oct 09 '17 at 10:04

The faculty of two numbers python 3

2 Answers2