sarthak sarthak - 23 days ago 8
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.

Answer

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.