Возможно переполнение?

Question

Моя программа работает для меньших чисел, таких как 144,123 или 60, но, кажется, перестает работать, когда числа увеличиваются по величине. Я прошел вводный курс по с ++ и смутно помню переполнения. Тем не менее, я не уверен, как именно переменные Python работают точно, так как тип переменной явно не объявляется. 1024 кажется слишком маленьким для переполнения целого числа, но, возможно, я пропускаю что-то в рамках рекурсии, поскольку я только начинаю получать рекурсию зависания. Может кто-нибудь объяснить мне, почему этот алгоритм ломается при больших числах?

Код

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)

Выход

RecursionError: максимальная глубина рекурсии превышена по сравнению

Процесс вернул 1 (0x1) время выполнения: 0,082 с Нажмите любую клавишу для продолжения.,,

Answer 1

Поскольку все рекурсивные вызовы выполняются в конце функции, вы можете использовать оптимизацию Tail Call Baruchel для Python (устанавливается с 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)

Это выводит:

5 is a prime
2 is a prime