python - 在python中用循环重写递归函数

Question

我想foo用foo2(non-resursion) 替换我的函数，但foo2工作不正确。有什么问题foo2？

def foo(n, k=0,s=0):
    if k < n:
        for i in xrange(k==0,10):
            foo(n, k+1, 10*s + i)
    else: 
        print s,

def foo2(n):
    s=0
    for k in xrange(n):
        st = s
        for i in xrange(k==0, 10):
            st = 10* st + i
        print st
foo(3)
foo2(3)

更新

如果我替换10*s + i为s + i**3，我该如何重写它？

Answer 1

foo打印 10 ^n-1 ~ 10 ⁿ -1；迭代xrange(10**(n-1), 10**n)。

def foo2(n):
    for s in xrange(10**(n-1), 10**n):
        print s,

---

以下是使用堆栈的递归函数的翻译：

def foo2(n):
    stack = [(0, 0)] # corresponding to (..., k=0, s=0)
    while stack:
        k, s = stack.pop(0)
        if k < n:
            for i in xrange(k==0, 10):
                stack.append((k+1, 10*s + i))
        else:
            print s,

注意要实现严格等效的迭代版本，您还应该推送迭代器（xrange...）；在循环中一次只消耗一项。