帮助理解这个递归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函数是如何工作的？

回答

相关问题