CODEWITHSUNDEEP
pythonrecursion
sarthak
sarthak

Reputation: 794

Implementing an Iterative Process: Python

I find the smallest divisor of a number with this code:

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

However, when I run this with a large enough value, I get:

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

I do not understand the recursion error. Isn't this code implementing an iterative process? 

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

If not, how can I implement an iterative process for this algorithm?

Upvotes: 0

Views: 298

Answers (2)

Prune
Prune

Reputation: 77837

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.

Upvotes: 1

denvaar
denvaar

Reputation: 2214

As has been stated in the comments, Python does not have tail recursion optimization. You're seeing the error simply because the stack becomes too big to handle.

EDIT

Here is one way to get the smallest factor iteratively:

# if you're using python3, import reduce from functools
from functools import reduce

def get_factors(n):
    factors = []
    i = 2
    while i < n:
        if (n % i) == 0:
            factors.append(i)
            if reduce(lambda x,y: x*y, factors) >= n:
                return factors
        i = i + 1
    return factors

This will return a list of all of the factors. To get the smallest, you can look at the first element. since 32452843 is prime, the list will be empty.

Upvotes: 2

Related Questions