Functions throws error on recursing large numbers

Question

I'm using Python 2.7.3 and have this function:

def f(n):
    if n == 0:
        return 0
    else:
        return (n % 3 == 0 or n % 5 == 0) * n + f(n - 1) 
f(999)

It works until f(993), but not f(999). When I try, infinite amount of errors keep popping out. I don't get it. Can anyone tell me what's wrong?

Edit: Thanks everyone for your answers. I guess i'm better off using iteration in python.

Yes, if the last line of output is `RuntimeError: maximum recursion depth exceeded`. — Dan D., Apr 20 '13 at 09:50
This can verily easily be changed into a loop to avoid such a problem. — Paul S., Apr 20 '13 at 09:52

score 4 · Answer 1 · edited May 23 '17 at 12:18

In Python, recursion is limited to 999 recursion call.

If you really want to change the limit of recursion call, you can use sys.setrecursionlimit(limit).

For example:

sys.setrecursionlimit(2000)

However, changing recursion limit can be dangerous. The stack frames might get too big.

From the doc:

This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. It can be set by setrecursionlimit().

What you can do is:

Like @Dan D. said, you better rewriting your code iteratively. Here is the reason why you should.

Dan D. · Accepted Answer · 2013-04-20T10:13:43.387

3

Better off using the iterative:

def f(n):
    s = 0
    while n > 0:
        s += (n%3==0 or n%5==0)*n
        n -= 1
    return s
print f(999)

which outputs:

Also one could write this with sum:

def f(n):
    return sum((n%3==0 or n%5==0)*n for n in reversed(range(1,n+1)))

edited Apr 20 '13 at 10:13

answered Apr 20 '13 at 09:53

Dan D.

73,243
15
104
123

`(n%3==0 or n%5==0)*n` could also be written `n if n%3==0 or n%5==0 else 0`, which might be more clear. Or you could reverse the logic and do `0 if n%3 or n%5 else n`. Or in your last version, since you're using a generator expression, you could put the condition at the end, rather than as part of the expression: `sum(n for n in range(1, n+1) if n%3==0 or n%5==0)` – Blckknght Apr 20 '13 at 11:40

score 3 · Answer 3 · answered Apr 20 '13 at 10:27

As you have already known from the other answers as to the reason for your code failure, and you have possibly got alternative solutions either by increasing the recursion limit or using an iterative solution

Alternatively, there is a smarter approach to your problem which requires a bit introspection to what you actually want to achieve

Sum all factors of 3 and 5 from 0 to N

Which simply boils down to

>>> def fn_ab(n):
    numbers = [0]*n
    numbers[0:n:3] = range(0,n,3)
    numbers[0:n:5] = range(0,n,5)
    return sum(numbers)

Or better, `sum(n for n in range(1, n+1) if n % 3 == 0 or n % 5 == 0)` — Eric, Apr 20 '13 at 10:32

Functions throws error on recursing large numbers

3 Answers3