把一个递规程序转化成循环

把一个递归程序转化成循环
代码如下，请大神帮忙，十分感谢！

def fun(a,b,c,n, r=[]):
if n<1:
r.append([[b, c], [b + a/2, c - a], [b + a, c]])
#print [[b, c], [b + a/2, c - a], [b + a, c]]
else:
fun(a/2.0, b, c,n-1)
fun(a/2.0, b+a/4.0, c-a/2.0, n-1)
fun(a/2.0, b+a/2.0, c, n-1)
return r

print fun(-1, 0.5, 0, 2)

递归 Python 算法
[解决办法]
用列表保存参数，模仿函数出入栈的动作...

def fun_nr(a, b, c, n):
    s = [(a, b, c, n)]
    r = []
    while s:
        a, b, c, n = s.pop()
        if n < 1:
            r.append([[b, c], [b + a/2, c - a], [b + a, c]])
        else:            
            s.append((a/2.0, b+a/2.0, c, n-1))
            s.append((a/2.0, b+a/4.0, c-a/2.0, n-1))
            s.append((a/2.0, b, c,n-1))
    return r

[解决办法]
递归层次若在控制下，就不用强迫改成循环...参数r=[]这个用可变的不好，你print fun(-1, 0.5, 0, 2)两下试试，默然参数应该是方便最外层调用（面对其他用户），自己写的部分把参数带上，或者既然函数有返回r值，就不需要重复带参数。类似：

def fun(a,b,c,n):
    if n<1:
        return [[[b, c], [b + a/2, c - a], [b + a, c]]]
        #print [[b, c], [b + a/2, c - a], [b + a, c]]
    else:
        r = []
        r += fun(a/2.0, b, c,n-1)
        r += fun(a/2.0, b+a/4.0, c-a/2.0, n-1)
        r += fun(a/2.0, b+a/2.0, c, n-1)
    return r

[解决办法]
写了个不简洁的，应该还能优化

def f(ls):
    a,b,c=ls
    return [[a/2.0, b, c], [a/2.0, b+a/4.0, c-a/2.0], [a/2.0, b+a/2.0, c]]
    
def g(ls):
    a,b,c=ls
    return [[b, c], [b + a/2, c - a], [b + a, c]]

def fun(a,b,c,n):
    t=[[a,b,c]]
    for i in range(n):
        t=[y for x in map(f, t) for y in x] 
 
    return map(g, t)

print fun(-1, 0.5, 0, 2)

[解决办法]
这个简洁了一些，

def fun(ls,n):
    r=[ls]
    for i in range(n):
        tmp=[((a/2., b, c), (a/2., b+a/4., c-a/2.), (a/2., b+a/2., c)) for a,b,c in r] 
        r=[y for x in tmp for y in x]
    return [[(b, c), (b + a/2., c - a), (b + a, c)] for a,b,c in r]

print fun([-1, 0.5, 0], 1)

查看更多 下一篇