如何在python中正确使用递归和副作用

Question

在树形结构中，我试图找到一个分支的所有叶子。以下是我写的:

def leafs_of_branch(node,heads=[]):
    if len(node.children()) == 0:
        heads.append(str(node))
    else:    
        for des in node.children():
           leafs_of_branch(des)
    return heads

leafs_of_branch(node)

我不知道为什么，但我感觉不对。它工作，但我想知道是否有一个更好的方法来使用递归，而不创建heads参数。

Answer 1

This

def leafs_of_branch(node,heads=[]):

总是一个坏主意。最好是

def leafs_of_branch(node,heads=None):
    heads = heads or []

，否则您总是为leafs_of_branch使用相同的列表。在你的特殊情况下，这可能没问题，但迟早你会遇到问题。

我建议:

def leafs_of_branch(node):
    leafs = []
    for des in node.children():
        leafs.extend(leafs_of_branch(des))
    if len(leafs)==0:
        leafs.append(str(node))
    return leafs
leafs_of_branch(node)

不是做if len(node.children()==0，而是在降下到所有(可能为零)子节点后检查len(叶子)。因此我只调用node.children()一次。

Answer 2

我相信这应该能行:

def leafs_of_branch(node):
    if len(node.children()) == 0:
       return [str(node)]
    else:
       x = []
       for des in node.children():
           x += leafs_of_branch(des)  #x.extend(leafs_of_branch(des)) would work too :-)
       return x

它不是很漂亮，可能可以更浓缩一点，但我试图尽可能保持原始代码的形式，使其明显发生了什么

你的原始版本实际上不会工作，如果你调用它不止一次，因为当你追加到heads列表，该列表实际上会保存调用之间

Answer 3

只要递归进行，我认为你做得对;你在递归调用中丢失了heads参数。不管怎样，它工作的原因是其他人说，默认参数是全局的，并在调用之间重用。

如果你想完全避免递归，在这种情况下，你可以使用Queue或Stack和循环:

def leafs_of_branch(node):
    traverse = [node]
    leafs = []
    while traverse:
        node = traverse.pop()
        children = node.children()
        if children:
            traverse.extend(children)
        else:
            leafs.append(str(node))
    return leafs

Answer 4

也可以这样递归地定义迭代器。

def leafs_of_branch(node):
    if len(node.children()) == 0:
        yield str(node)
    else:    
        for des in node.children():
            for leaf in leafs_of_branch(des):
                yield leaf
leafs = list(leafs_of_branch(node))

Answer 5

首先，避免使用可变对象(列表，字典等)作为默认值，因为默认值是全局的，并且在函数调用之间重用:

def bad_func(val, dest=[]):
    dest.append(val)
    print dest
>>> bad_func(1)
[1]
>>> bad_func(2)
[1, 2]  # surprise!

因此，后续调用将产生完全意想不到的结果。

对于递归问题，我将这样重写:

from itertools import chain
def leafs_of_branch(node):
    children = node.children()
    if not children:  # better than len(children) == 0
        return (node, )
    all_leafs = (leafs_of_branch(child) for child in children)
    return chain(*all_leafs)