一个貌似比较吊的递归转换为loop--总算成功了.

class Stack(object):
    """
    A class to hold arguements and state data.
    """
    def __init__(self,**kwargs):
        self.__dict__.update(kwargs)

    def __repr__(self):
        extra = "|i:%s"%self.i if hasattr(self,‘i‘) else ‘‘
        return "n:%s|stage:%s%s"%(self.n,self.stage,extra)
    
def memory(function):
    """
    A decorator to help a no-side-effect function avoid
    repeative calculation.
    """
    cache = {}
    def memofunc(*nkw,**kw):
        key=str(nkw)+str(kw)
        if key not in cache:            
            cache[key] = function(*nkw,**kw)
        return cache[key]
    return memofunc

def is_equal(rg,*funclist):
    """
    to test whether or not a list of one-arguement functions
    have the same output if given same arguement.
    """
    for n in rg:
        rst=[]
        for func in funclist:
            rst.append(func(n))
            assert len(set(rst))==1

@memory
def hanoi_recur(n):
    """
    n -> (i,v)
    a recursive function to get the smallest number i
    and correspondent value.
    """
    if n==1:
        return 1,1
    psb=[]
    for i in range(n-1,0,-1):
        _, min_v = hanoi_recur(n-i)
        psb_v = 2*min_v+2**i-1
        psb.append((i,psb_v))
    return min(psb,key=lambda x:x[1])

@memory
def hanoi_loop(n):
    """
    The loop version of hanoi_recur.
    """
    if n==1:
        return 1,1
    stack = [Stack(n=n,stage=0,)]
    cache={1:1} 
    while stack:
        crt=stack.pop()    
        if crt.n in cache:
            psb_v = 2*cache[crt.n]+2**crt.i-1
            crt.prt.psb.append((crt.i,psb_v))
            continue
        if crt.stage==0: 
            crt.stage, crt.pgs, crt.psb= 1, 0, []
            stack.append(crt)
            continue
        if crt.stage==1:
            if crt.pgs != crt.n - 1:
                crt.pgs += 1
                stack.append(crt)
                chd = Stack(n=crt.pgs, stage=0, i=crt.n-crt.pgs, prt=crt)
                stack.append(chd)
            else:
                crt.stage=2
                stack.append(crt)
            continue
        if crt.stage==2 and hasattr(crt,‘prt‘):
            #hasattr - the last stack doesn‘t have attribute ‘prt‘,
            #so it has to be excluded here.
            _, min_v = min(crt.psb,key=lambda x:x[1])            
            psb_v = 2*min_v + 2**crt.i - 1
            crt.prt.psb.append((crt.i,psb_v))
            cache[crt.n] = min_v
            continue
    return min(crt.psb,key=lambda x:x[1])

            
if __name__==‘__main__‘:
    is_equal(range(1,300),hanoi_loop,hanoi_recur)
    print(‘passed test!‘)