幫助理解這個遞歸python函數是如何工作的？

我是一名程序員，我做了一些C＃perl和python，反正，我發現這個遞歸代碼來生成符號和字母列表的排列，但我無法弄清楚它是如何工作的？任何人都可以照顧請解釋一下嗎？幫助理解這個遞歸python函數是如何工作的？

#!/usr/bin/env python 
#-*- coding:utf-8 -*- 

def generate(charlist,state,position): 
    for i in charlist: 
     state[position] = i 
     if position == (len(state)-1): 
      print "".join(state) 
     else: 
      generate(charlist,state,position+1) 

generate("1234567890qwertyuiopasdfghjklzxcvbnm",[None]*8,0)

這裏是代碼，所有正確的間距。

來源

2011-07-14 TheEliteNoob

您永遠不會返回該函數，因此它不能正確遞歸。 –

我們走了，確保它是完美的，代碼的作品也是如此。也編輯標題，以配合你所說的Jakob。 – TheEliteNoob

@Jakob Bowyer遞歸函數是調用自身的任何函數。 –

這是的不是生成排列。它生成n維笛卡爾產品。（在這個過程中，它也產生所有排列，但算法生成只排列會有所不同。）

這是一個有點難以解釋它是如何工作的，但如果你看看輸出較小的輸入，你可以看到發生了什麼。考慮'abc'和[None] * 3輸出（我修改了代碼作爲一個真正的生成）：

>>> def generate(charlist,state,position): 
...  for i in charlist: 
...   state[position] = i 
...   if position == (len(state)-1): 
...    yield "".join(state) 
...   else: 
...    for j in generate(charlist,state,position+1): 
...     yield j 
... 
>>> print list(generate('abc', [None] * 3, 0)) 
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 
'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 
'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

正如你所看到的，什麼情況是，最初，generate自稱爲三次，遞增每次position（從0至1至2）。每次通過遞歸循環時，它會將'a'置於當前位置，並測試它是否已到達state列表的末尾。如果是這樣，它會得出結果，並且不是自己調用。

在這種情況下，當發生這種情況時，position == 2。現在for循環開始，將'b'和'c'存儲在state[2]中，併產生這些狀態中的每一個。然後該功能結束，並且控制返回給調用者，其中position == 1。呼叫者然後繼續其for循環;它集state[1] = 'b'然後，因爲position是在state列表的末尾不再，它再次調用自身......現在position == 2，並在for循環設置state[2] == 'a'，'b'，'c'，等等。

順便說一句，如果你想計算笛卡爾乘積的蟒蛇，這裏是一個不錯的方式，不需要你的讀者解析出遞歸算法：

>>> import itertools 
>>> [''.join(c) for c in itertools.product('abc', 'abc', 'abc')] 
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 
'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 
'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

你也可以做

>>> [''.join(c) for c in itertools.product(*['abc'] * 3)]

來源

2011-07-14 14:27:48 senderle

謝謝！這非常有幫助！ – TheEliteNoob

你不知道它是如何工作的？把這一行剛def generate...後：

print charlist, state, position

，它會告訴你變量在每次調用使用了什麼。

來源

2011-07-14 14:20:18 eumiro

嗯，好的，我會試試看。好的，這是有用的，但我試圖找出它爲什麼有效，以及每一行的功能。 – TheEliteNoob

該函數輸出每個可能的（除非第三個參數是非零）給定字符的組合。

它需要作爲輸入：

列表或將要組合字符的字符串，
其長度表示多少個字符應立即進行組合的列表，
一個數，其表示每個組合的多少個字符應該用第二個列表中的相應字符替換（這會相應地減少可能的組合的數量）。

如果第二個參數是8個None值的列表（因爲[None] * 8 == [None, None, None, None, None, None, None, None]），第三個參數設置爲非零值將導致TypeError。

@ senderle的答案解釋了函數中發生了什麼。

我應該說這是一個非Pythonic代碼的例子，正是因爲很難從第一眼看到它的目的。

來源

2011-07-14 14:37:47 Tony

幫助理解這個遞歸python函數是如何工作的？

回答

相關問題