Maximum recursion depth exceeded for python division problem-CodePudding

I have created a recursive function to calculate the total numbers divisible by n within a range of (start,end). The function works for smaller numbers except when they start getting larger for ex. start=1 and end=10**12 - 1 gives me an error saying that the maximum recursion depth has been exceeded. How do I fix my code to stop this error:

def count(start, end, n, tot=0):
    if start > end:
        return tot
    else:
        if start % n == 0:
            tot  = 1
    return count(start   1, end, n, tot)


start = 1
end = 10**12 - 1
n = 5
print(count(start, end, n))

CodePudding user response：

Two points.

(directly answering your question) You can increase the recursion depth by using the sys module.

import sys
sys.setrecursionlimit(10**12)

(towards making you a better programmer) You don't need to use recursion for this problem. In fact, it's a really bad idea as others have noted. Recursion like what you would be looking to do is O(n^2) which is, also known as 'really bad'. A linear approach would be O(n) which is pretty good. Better yet is to take the mathematical approach as Samwise and btilly suggested because you arent tasked to return the numbers that meet the criteria.

CodePudding user response：

You can solve this problem with simple arithmetic. Thinking about a range such as (3, 18) (inclusive) and an n of 5, the actual range of interest is from 5 to 15 (since there are no multiples of 5 below 5 or above 15. You can round the start and end values to the new endpoints like this:

start = (start   4) // n * n
end = end // n * n

What you need to do then is just count the values from 5 to 15 (3) which you can do subtracting the new start from the new end, dividing by n and adding 1 i.e.

(end // n * n - (start   4) // n * n) // n   1

which can be simplified to

end // n - (start   4) // n   1

So in total your function becomes:

def count(start, end, n):
    return end // n - (start   4) // n   1