如何重写递归函数来代替使用循环？

这个堆栈溢出线程声称每个递归函数都可以写成一个循环。如何重写递归函数来代替使用循环？

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的每一个排列。

来源

2011-03-16 Philluminati

@nmichaels：Python没有goto语句。 – 2011-03-16 18:59:33

个人...我认为它可以解决，但你需要引用一些变量来管理你的递归在一个循环内执行的事实...因此你需要存储循环的位置和你通过递归...“变成”或“变成”可以这么说。 – Philluminati 2011-03-16 19:06:18

是的，你可以使用相同的算法并假装成解释器并管理自己的堆栈。或者，你可以想出一个用于生成排列的迭代算法，这将更容易表达为循环。 – nmichaels 2011-03-16 19:08:44

我不太熟悉python语法，但是下面的代码（在'c'中）不应该太难转换，假设python可以嵌套语句。

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]);

来源

2011-03-16 19:09:10 Adam

这样做是否行得通，因为每个数字都有一个索引......即。如果列表大小为4，我需要另一个循环吗？ – Philluminati 2011-03-16 20:28:55

是的，这只适用于列表大小为3的情况。我对此类迟到的评论表示歉意。 – Adam 2011-03-17 02:58:23

做置换的最Python的方式是使用：

>>> 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)]

来源

2011-03-16 19:13:29 fabrizioM

该函数的文档显示了如何迭代生成排列：http://docs.python.org/py3k/library/itertools#itertools.permutations – ncoghlan 2011-03-16 19:26:00

这似乎不适用于我。我可以在Python 2.5.2中导入itertools，但我没有排列函数 – Philluminati 2011-03-16 19:29:04

@Philluminati来自版本2.6 – fabrizioM 2011-03-16 20:53:32

比方说，你想找到的所有排列[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，第二项是列表中剩下的第一，第二或第三项（在你取出第一项后）。

你可以继续这样。这里有一些代码是这样的：

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

来源

2011-03-16 23:48:36

如何重写递归函数来代替使用循环？

回答

相关问题