CODEWITHSUNDEEP
pythonpython-2.7
Minar Ashiq Tishan
Minar Ashiq Tishan

Reputation: 312

Functions throws error on recursing large numbers

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.

Upvotes: 3

Views: 146

Answers (3)

Abhijit
Abhijit

Reputation: 63757

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)

Upvotes: 3

Thanakron Tandavas
Thanakron Tandavas

Reputation: 5683

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.

Upvotes: 4

Dan D.
Dan D.

Reputation: 74655

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:

233168

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

Upvotes: 3

Related Questions