Maximum recursion depth exceeded for python division problem

Question

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

Python doesn't do tail call optimization, so the best solution is to not use recursion for problems that require arbitrarily long iterations. Use a regular old iterative loop instead. — Samwise
– Samwise, Commented Jun 20, 2022 at 2:34
the problem is that i cant use an iterative loop for this problem only conditional statements and integer arithmetic — raph c
– raph c, Commented Jun 20, 2022 at 2:36
something along the lines of (end - start) // n, with some checking for edge cases? — Samwise
– Samwise, Commented Jun 20, 2022 at 2:50

Nick · Accepted Answer · 2022-06-20 04:11:45Z

1

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

answered Jun 20, 2022 at 4:11

Nick

147k23 gold badges67 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

hrokr · Accepted Answer · 2022-06-20 03:47:21Z

0

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.

edited Jun 20, 2022 at 3:47

answered Jun 20, 2022 at 3:05

hrokr

3,6194 gold badges26 silver badges43 bronze badges

1 Comment

Blckknght Over a year ago

Can you explain why you think the existing recursion is O(n^2)? It looks pretty linear to me, with exactly one recursive call for each start value from 1 to 10**12.

Collectives™ on Stack Overflow

Maximum recursion depth exceeded for python division problem

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related