Implementing an Iterative Process: Python

Question

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?

Python doesn't have tail-call optimisation ([see this question](http://stackoverflow.com/q/13591970/660921)), so the recursion doesn't unwind like you describe. You need to use a loop. — Martin Tournoij, Nov 15 '16 at 17:14
Are you saying we cannot implement an iterative process in Python? — sarthak, Nov 15 '16 at 17:18
It's quite straightforward to implement an iterative process -- but that suggests that you use the iterative control structures: **for, while**, etc. — Prune, Nov 15 '16 at 17:45
well...actually recursive process and recursive procedure call are different things: see http://stackoverflow.com/questions/17254240/sicp-recursive-process-vs-iterative-process-using-a-recursive-procedure-to-gene — sarthak, Nov 15 '16 at 17:51
then I presume that you come from Haskel or some other functional language ?? — Copperfield, Nov 15 '16 at 17:51
well no...I just wanted to implement the iterative process using recursive calls...Is it not possible in Python? — sarthak, Nov 15 '16 at 17:53
yes, you can as long as you use tail recursion optimization helper of some kind because [python don't have one](http://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion). You can use this decorator for that [tail-call-optimization-decorator](http://code.activestate.com/recipes/474088-tail-call-optimization-decorator/) — Copperfield, Nov 15 '16 at 18:13

denvaar · Answer 1 · 2016-11-15T17:29:43.693

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.

Prune · Accepted Answer · 2016-11-15T18:15:05.317

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.

But shouldn't an iterative process use just one stack frame. — sarthak, Nov 15 '16 at 18:05
@sarthak yes if its implementing as a iteration with the while/for loop construct, but here you are using a recursive call and python don't know how to optimize that even if you use a tail recursion form, so each call add a new stack frame for each function you call regardless of the function. — Copperfield, Nov 15 '16 at 18:24

Implementing an Iterative Process: Python

2 Answers2