如何重写递归函数以使用循环？

Question

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

哪些递归函数不能使用循环重写？

感觉。但我不确定如何将以下递归函数表示为循环，因为它具有预递归逻辑和后递归逻辑。

显然解决方案不能使用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)]

Answer 2

假设您想要找到 [1, 2, 3, 4] 的所有排列。其中有 24 个（=4！），因此将它们编号为 0-23。我们想要的是一种非递归的方法来找到第 N 个排列。

假设我们按数字升序对排列进行排序。那么：

• 排列 0-5 从 1 开始
• 排列 6-11 从 2 开始
• 排列 12-17 从 3 开始
• 排列 18-23 从 4 开始

因此，我们可以通过将 N 除以 6（=3！） 得到第一个排列数 N。 ，并向上舍入。

我们如何得到下一个数字？看看排列 0-5 中的第二个数字：

• 排列 0-1 有第二个数字 2。
• 排列 2-3 有第二个数字 3。
• 排列 4-5 有第二个数字 4。

我们在排列 6-11 中看到类似的情况：

• 排列6-7 的第二个数字为 1。
• 排列 8-9 的第二个数字为 3。
• 排列 10-11 的第二个数字为 4。

一般来说，先除以 6 后取余数，再除以 2（=2！），然后舍入向上。这将为您提供 1、2 或 3，第二个项目是列表中剩余的第 1 个、第 2 个或第 3 个项目（在您取出第一个项目之后）。

你可以继续这样下去。这是执行此操作的一些代码：

from math import factorial

def gen_perms(lst):
    all_perms = []

    # Find the number of permutations.
    num_perms = factorial(len(lst))

    for i in range(num_perms):
        # Generate the ith permutation.
        perm = []
        remainder = i

        # Clone the list so we can remove items from it as we
        # add them to our permutation.
        items = lst[:]

        # Pick out each item in turn.
        for j in range(len(lst) - 1):
            # Divide the remainder at the previous step by the
            # next factorial down, to get the item number.
            divisor = factorial(len(lst) - j - 1)
            item_num = remainder / divisor

            # Add the item to the permutation, and remove it
            # from the list of available items.
            perm.append(items[item_num])
            items.remove(items[item_num])

            # Take the remainder for the next step.
            remainder = remainder % divisor

        # Only one item left - add it to the permutation.
        perm.append(items[0])

        # Add the permutation to the list.
        all_perms.append(perm)

    return all_perms

Answer 3

我不太熟悉 python 语法，但假设 python 可以嵌套 for 语句，那么下面的代码（在“c”中）应该不会太难翻译。

int list[3]={1,2,3};
int i,j,k;

for(i=0;i < SIZE;i++)
for(j=0;j < SIZE;j++)
for(k=0;k < SIZE;k++)
if(i!=j && j!=k && i!=k)
printf("%d%d%d\n",list[i],list[j],list[k]);