sarthak - 1 year ago 71
Python Question

# Implementing an Iterative Process: Python

I have the following code, where I am trying to find the smallest divisor of a number:

``````def smallestDisvisor(n):
return factor(n,2)

def factor(n,divisor):
if (square(divisor) - n > 0):
return n
elif (n % divisor == 0):
return divisor
else:
return factor(n,divisor + 1)

print(smallestDisvisor(32452843))
``````

But when I am running this I am getting the following error:

``````RecursionError: maximum recursion depth exceeded
[Finished in 0.5s with exit code 1]
``````

I do not understand why is this error coming. Isn't this code implementing an iterative process?

``````factor(32452843,2) -> factor(32452843,3) -> factor(32452843,4)...
``````

If not, why and how will I implement an iterative process for the same.

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