记住经典的斐波拉契递归和阶乘递归转换为while规律

# 斐波拉契--树形递归

def fab(n):
    if n<3:
        return n
    return fab(n-1)+fab(n-2)

def wfab(n):
    stacks=[(0,n,None)]
    while stacks:
        stg,n,value=stacks.pop()
        if stg==0:
            if n<3:
                res=n
            else:
                stacks.append((1,n,None))
                stacks.append((0,n-1,None))
        elif stg==1:
            stacks.append((2,n,res))
            stacks.append((0,n-2,None))
        else:
            res=value+res
    return res            

#阶乘--线性递归

def fac(n):
    if n<1:
        return 1
    return n*fac(n-1)

def wfac(n):
    stacks=[(0,n)]
    while stacks:
        stg,n=stacks.pop()
        if stg==0:
            if n<1:
                res=1
            else:
                stacks.append((1,n))
                stacks.append((0,n-1))
        elif stg==1:
            res=res*n
    return res

def fab(n):
    if n<4:
        return n
    return (3*fab(n-3)-2*fab(n-1))*4*fab(n-2)

def wfab(n):
    stacks=[(0,n,None)]
    while stacks:
        stg,n,value=stacks.pop()
        if stg==0:
            if n<4:
                res=n
            else:
                stacks.append((1,n,None))
                stacks.append((0,n-3,None))
        elif stg==1:
            stacks.append((2,n,3*res))
            stacks.append((0,n-1,None))
        elif stg==2:
            stacks.append((3,n,value-2*res))
            stacks.append((0,n-2,None))
        else:
            res=value*4*res
    return res