python之帮助理解这个递归 python 函数是如何工作的

我是一名程序员，我会使用 C# perl 和 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) 

这是代码，所有间距都正确。

请您参考如下方法:

这不会生成排列。它生成 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'，依此类推。

顺便说一句，如果你想在 python 中计算笛卡尔积，这里有一个很好的方法，不需要你的读者解析出递归算法:

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