sarthak - 1 year ago 64

Python Question

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 Source

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.