python - 如何重写递归函数以使用循环代替？

Question

这个堆栈溢出线程声称每个递归函数都可以写成一个循环。

Which recursive functions cannot be rewritten using loops?

这是完全有道理的。但我不确定如何将以下递归函数表示为循环，因为它具有前递归逻辑和后递归逻辑。

显然解决方案不能使用 goto 语句。代码在这里:

def gen_perms(lst, k, m):

    if k == m:
        all_perms.append(list(lst))
    else:
        for i in xrange(k, m+1):

            #swap char
            tmp = lst[k]
            lst[k] = lst[i]
            lst[i] = tmp

            gen_perms(lst, k+1, m)

            #swap char
            tmp = lst[k]
            lst[k] = lst[i]
            lst[i] = tmp

调用它会是这样的:

all_perms = []
gen_perm([1, 2, 3], 0, 2)

它生成列表 1,2,3 的每个排列。

Answer 1

进行排列的最 pythonic 方式是使用:

>>> from itertools import permutations
>>> permutations([1,2,3])
>>> list(permutations([1,2,3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]