[FIXED] Spyder kernel restarts when I run a recursive algorithm

Issue

import random

 def gcd(a,b):
    if a < b:
        b = b - a
        return gcd(a,b)
    elif a > b:
        a = a - b
        return gcd(a,b)
    else:
        return a

def f(x,n):
    return (x**2 + 1) % n

def PolRho(n):

    x = random.randint(2,n)
    y = x
    d = 1

    while d == 1:
    
        x = f(x,n)
        y = f(f(y,n),n)
        print(x,y)
    
        d = gcd(abs(x-y),n)
    
        if d == n:
            return PolRho(n)
    return [d,n/d]

print(PolRho(16))

This is my code for Pollard's algorithm. The code works fine for 'print(PolRho(15))', but the kernel restarts if I try any other value for example 'print(PolRho(16))'

Solution

I tried your code in Python 3.8.3 under Spyder 4.1.4 and PolRho(15) runs fine but PolRho(16) raises an error, and the (very long!) stack trace ends with

  File "D:\polrho.py", line 13, in gcd
    return gcd(a,b)

  File "D:\polrho.py", line 11, in gcd
    if a < b:

RecursionError: maximum recursion depth exceeded in comparison

So I don't know why your Spyder kernel restarts without reporting the error, but the underlying problem is that your recursion has reached Python's maximum stack depth.

If you really need this code to work as written you can try increasing the stack depth, but a more reliable method would be to use math.gcd to find the greatest common divisor instead of your recursive method.

If you suspect that Spyder (or any other IDE) may be involved with a problem you're seeing with Python code, you should always try running the code from the command line, e.g.

python polrho.py

Answered By - nekomatic