Possibly an overflow?

Question

My program works for smaller numbers like 144,123, or 60 but seems to stop working when the numbers increase in magnitude. I've taken an introduction course in c++ and I vaguely remember overflows. However, I am not sure how python variables precisely work as the variable type does not seem to be explicitly declared. 1024 seems to be to small for an integer to overflow but perhaps I'm overlooking something within the recursion as I am only beginning to get the hang recursion. Can someone please explain to me why this algorithm breaks down at larger numbers?

Code

num = 1024

#Used to remove duplicates of the same prime
def simplify (num,prime):
    if(num % prime == 0):
        return simplify(num/prime,prime)
    else:
        return (num,num)

#used to find the prime factors
def pFact(num,a,b):
    if a == 1:
        return
    elif b == 1:
        print (a, "is a prime")
        return pFact((simplify (num,a))[0],(simplify (num,a))[1],a)
    elif a % b == 0:
        return pFact(num,b,b-1)
    elif a % b != 0:
        return pFact (num,a,b-1)
    elif b == 0:
        return (num,num,num-1)

pFact(num,num,num-1)

Output

RecursionError: maximum recursion depth exceeded in comparison

Process returned 1 (0x1) execution time : 0.082 s Press any key to continue . . .

How would I know approximately how much to increase the depth to? What would happen if I made the depth too high? — Tony, Sep 01 '18 at 03:21
Python people always point to maximum recursion depth only because it’s configurable – it’s silly because no matter what you configure it to, there is still a limit. A *real* solution such as a trampoline is easy to implement and allows for infinite recursion. — Mulan, Sep 01 '18 at 03:30

score 0 · Answer 1 · answered Sep 01 '18 at 03:58

Since all the recursive calls are made at the end of the function, you can use baruchel's Tail Call Optimization for Python (installed with pip install tco):

from tco import with_continuations
num = 10240

#Used to remove duplicates of the same prime
def simplify (num,prime):
    if(num % prime == 0):
        return simplify(num/prime,prime)
    else:
        return (num,num)

#used to find the prime factors
@with_continuations()
def pFact(num,a,b, self=None):
    if a == 1:
        return
    elif b == 1:
        print (a, "is a prime")
        return self((simplify (num,a))[0],(simplify (num,a))[1],a)
    elif a % b == 0:
        return self(num,b,b-1)
    elif a % b != 0:
        return self(num,a,b-1)
    elif b == 0:
        return (num,num,num-1)

pFact(num,num,num-1)

This outputs:

5 is a prime
2 is a prime

Possibly an overflow?

Code

Output

1 Answers1