Even with an iterative form, this isn't going to get any faster. The problem isn't the recursion limit; you're still an order of magnitude below the recursion limit. The problem is that the size of your output is O(2^n)
. For n=100
, you have to build a tuple of about a thousand billion billion billion elements. It doesn't matter how you build it; you'll never finish.
If you want to convert this to iteration anyway, that can be done by managing state with an explicit stack instead of the call stack:
def moves_three(n, a=0, b=1, c=2):
first_entry = True
stack = [(first_entry, n, a, b, c)]
output = []
while stack:
first_entry, n1, a1, b1, c1 = stack.pop()
if n1 == 1:
output.append((a1, c1))
elif first_entry:
stack.append((False, n1, a1, b1, c1))
stack.append((True, n1-1, a1, c1, b1))
else:
output.append((a1, c1))
stack.append((True, n1-1, b1, a1, c1))
return tuple(output)
Confusing, isn't it? A tuple (True, n, a, b, c)
on the stack represents entering a function call with arguments n, a, b, c
. A tuple (False, n, a, b, c)
represents returning to the (True, n, a, b, c)
call after moves_three(n-1, a, c, b)
ends.