I'm messing around with recursion and decided to turtle. I'm trying to get some code to build a Sierpenski Triangle and it's working pretty well so far! However, when I plug in larger values of n to my function to get more detailed triangles, it just crashes after exactly 990 turtle moves. Here's the error it gives me:
File "C:\Users\[censored]\AppData\Local\Programs\Python\Python311\Lib\tkinter\__init__.py", line 106, in _cnfmerge
elif isinstance(cnfs, (type(None), str)):
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded in __instancecheck__
The way my code works is that it has an initial algorithm that generates a string of characters that code to different things the turtle should do. Here is the algorithm:
def sierpenski(n: int) -> str:
if n==0:
return 'fll'*3
sierpenski_smaller=sierpenski(n-1)
side_length_of_smaller=2**(n-1)
thing_to_return=sierpenski_smaller
thing_to_return+='f'*side_length_of_smaller
thing_to_return+=sierpenski_smaller
thing_to_return+='l'
thing_to_return+='f'*side_length_of_smaller
thing_to_return+='ll'
thing_to_return+=sierpenski_smaller.replace('l',' ').replace('r','l').replace(' ','r')
thing_to_return+='f'*side_length_of_smaller
thing_to_return+='l'
thing_to_return+='f'*side_length_of_smaller
thing_to_return+='ll'
return thing_to_return
After generating this string, my code passes it into a function that recursively runs the commands. Here is the code:
def execute(commands: str) -> None:
if commands=='':
return
if commands[0]=='f':
t.fd(20)
if commands[0]=='l':
t.lt(60)
if commands[0]=='r':
t.rt(60)
execute(commands[1:])
There are recursive algorithms for which a recursion function is reasonable, like your sierpenski() function which computes a recursive fractal. But this isn't true of your execute() function which processes a non-recursive, linear list of characters (str).
Python has a set recursion limit to look for runaway code. You can interrogate this limit using sys.getrecursionlimit() and you can increase, or decrease, this limit with sys.setrecursionlimit(). But, this isn't the fix for you.
When you run sierpenski(10), it works fine as it recurses 10 levels which is well below the default limit of 1000. However, the string it produces has just shy of one million characters (940,685). You can't hope to stretch the recursion limit that far. You need to write the non-recursive interpretation of this string as a non-recursive function as @Stef suggests in their comment (+1):
def execute(commands: str) -> None:
for command in commands:
if command == 'f':
t.forward(20)
elif command == 'l':
t.left(60)
elif command == 'r':
t.right(60)
Now your recursive limitation is on the sierpenski() function alone, which can approach sierpenski(900), but my guess is no one has time to wait for that to complete!