如何重寫遞歸函數來代替使用循環？

這個堆棧溢出線程聲稱每個遞歸函數都可以寫成一個循環。如何重寫遞歸函數來代替使用循環？

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

如何重寫遞歸函數來代替使用循環？

回答

相關問題