# Convert Tail-Call Recursive Code to Loop [closed]

Posted on

Problem

So, I’m in the midst of writing a programming language interpreter in Python, and one of the problems I’m concerned about is that since I’ve been using a lot of recursions to implement the interpreter, I’ll get a stack overflow if the size of the code is too large. For example, I have a piece of code that evaluates an `and` operation. Since the language I’m implementing is a logic programming language (like Prolog), it needs to try out all the options, so it consumes a generator and loops over it looking at the rest of the `and` operation. Behold:

``````def evaluate_and(and_clauses, binds={}):
if and_clauses == []:
yield binds
else:
for p in possible:
yield from evaluate_and(tail, p)
``````

The issue with this is that if the `and` operation is buried deep within the program, and the call stack is already large, then if the `and` has too many clauses the interpreter will crash.

If anyone could suggest a way to make this not possible, that would be amazing!

PS: I have an even bigger problem, which is that since recursion is the only way to do looping in a logic programming language if you loop more than a 100 times in my language, it creates a stack overflow in my interpreter.

Solution

A quick search for “python tail call optimization” results in this SO answer which has a PyPI package, `tco`. Converting your code to return lists rather than generators should be all you need.

recursion is the only way to do looping in a logic programming language

This is wrong.

If you want it to stay as a generator, then you’ll have to manually handle the stack. The following doesn’t account for order so if you need that then you’ll have to figure that out yourself.

``````def evaluate_and(and_clauses, binds={}):
stack = [(clauses, binds)]
while stack:
and_clauses, binds = stack.pop()
if and_clauses == []:
yield binds
else: