I have the following code, where I am trying to find the smallest divisor of a number:
if (square(divisor) - n > 0):
elif (n % divisor == 0):
return factor(n,divisor + 1)
RecursionError: maximum recursion depth exceeded
[Finished in 0.5s with exit code 1]
factor(32452843,2) -> factor(32452843,3) -> factor(32452843,4)...
Now I understand the problem: implement an iterative process using recursion.
Yes, you can do this. What tripped you up is the default stack recursion limit. Since your recursion for a prime N takes sqrt(N) calls, you're limited to handling numbers <= MAX_STACK_RECURSION_DEPTH^2.
Your choices are to increase the depth from the default of 1000:
import sys sys.setrecursionlimit(10000)
or to use a more call-efficient algorithm, such as one that considers only prime divisors:
def smallestDisvisor(n): return factor(n, 2, ) def factor(n, divisor, prime_list): # See whether any prime divides teh current divisor. # Increment it until we get a new prime. while any(divisor % prime == 0 for prime in prime_list): divisor += 1 if (divisor * divisor > n): return n elif (n % divisor == 0): return divisor else: return factor(n, divisor + 1, prime_list + [divisor] ) print(smallestDisvisor(32452843))
Answer to comment:
A call adds a frame to the stack. Regardless of the theoretical nature of the process, you cannot make a function call without adding a stack frame. That's inherent in the run-time system. If you want an iterative process to have only one stack frame, then you must write an iterative implementation.