将树形递归转换为loop

class Stack(object):
def __init__(self,**kwargs):
self.__dict__.update(kwargs)
def __str__(self):
return '|'.join(
['%s:%s'%(k,getattr(self,k))
for k in sorted(self.__dict__)])
__repr__ = __str__def fab(n):
if n==1 or n==2:
return 1
return fab(n-1) + fab(n-2)def xfab(n):
rst = 0
stack = [Stack(n=n,stage=0)]
while stack:
#print(stack,rst)
crt=stack.pop()
if crt.stage == 0:
if crt.n == 1 or crt.n == 2:
rst = 1
continue
else:
crt.stage = 1
stack.append(crt)
stack.append(Stack(n=crt.n-1,stage=0))
continue
if crt.stage == 1:
crt.adv = rst
crt.stage = 2
stack.append(crt)
stack.append(Stack(n=crt.n-2,stage=0))
continue
if crt.stage == 2:
rst = crt.adv + rst
continue
return rst

#----------递归--------------------------------
def tmove(n,a=0,b=1,c=2):
if n==1:
yield a,c
else:
yield from tmove(n-1,a,c,b)
yield a,c
yield from tmove(n-1,b,a,c)def fmove(n,a=0,b=1,c=2,d=3):
if n==1:
yield a,d
else:
i = int((math.sqrt(1+8*n)-1)/2)
yield from fmove(n-i,a,d,b,c)
yield from tmove(i,a,b,d)
yield from fmove(n-i,c,b,a,d) #----------循环--------------------------------
def xtmove(n,a=0,b=1,c=2):
stack = [Stack(n=n,a=a,b=b,c=c,stage=0)]
while stack:
crt=stack.pop()
if crt.n == 1:
yield crt.a,crt.c
continue
if crt.stage==0:
crt.stage=1
stack.append(crt)
stack.append(Stack(n=crt.n-1,a=crt.a,b=crt.c,c=crt.b,stage=0))
continue
if crt.stage==1:
yield crt.a,crt.c
stack.append(Stack(n=crt.n-1,a=crt.b,b=crt.a,c=crt.c,stage=0))def xfmove(n,a=0,b=1,c=2,d=3):
stack = [Stack(n=n,a=a,b=b,c=c,d=d,stage=0)]
while stack:
crt=stack.pop()
if crt.n == 1:
yield crt.a,crt.d
continue
i = int((math.sqrt(1+8*crt.n)-1)/2)
if crt.stage==0:
crt.stage=1
stack.append(crt)
stack.append(Stack(n=crt.n-i,a=crt.a,b=crt.d,c=crt.b,d=crt.c,stage=0))
continue
if crt.stage==1:
yield from xtmove(n=i,a=crt.a,b=crt.b,c=crt.d)
stack.append(Stack(n=crt.n-i,a=crt.c,b=crt.b,c=crt.a,d=crt.d,stage=0))if __name__=='__main__':
for x,y in xfmove(10000000000):
pass
for x,y in fmove(10000000000):
pass