Spyder kernel restarts when I run a recursive algorithm

Question

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

You're using a recursive algorithm so at a guess the recursion could be reaching Python's [maximum stack depth](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it). Is there no error message before the kernel restarts? What do you see if you run the code from the command line, outside Spyder? — nekomatic, Feb 11 '22 at 13:14
I assume this is a learning exercise so you want to write all the code yourself but you can use `math.gcd` to find greatest common divisor. — nekomatic, Feb 11 '22 at 13:17
@nekomatic Hey thats funny part it says nothing before restarting. And its not overflowing because i tried a print statement inside the PolRho and its not even running once. — Vibin Ram Narayan, Feb 11 '22 at 14:01

score 0 · Accepted Answer · answered Feb 11 '22 at 15:54

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

Spyder kernel restarts when I run a recursive algorithm

1 Answers1