Python递归示例说明

Question

因此，目前正在通过麻省理工学院的开放课件计算机科学在线课程，我有困难试图理解其中一个递归的例子。你知道吗

def f(L):
    result = []
    for e in L:
        if type(e) != list:
            result.append(e)
        else:
            return f(e)
return result

当给出以下输入时：

print f([1, [[2, 'a'], ['a','b']], (3, 4)])

输出为：

[2, 'a']

我很难理解这个函数实际上是如何工作的，或者它在做什么。函数不应该最终将每个字符串或int添加到结果列表中吗？我只是需要帮助来理解这个函数是如何“结束”和“展开”的

我觉得输出应该是：

[1,2,'a','a','b',3,4]

任何帮助都将不胜感激谢谢！你知道吗

Answer 1

所以根据你建议的答案，我看到你理解了代码的思想。它越挖越深，直到找到一个元素。但是看看上面的那一步：

当它第一次到达最深的点（[2，'a']列表的元素）时，它完成这个级别的循环并返回结果2和a。。。这意味着循环已停止，因此找不到其他元素。你知道吗

现在的问题是，为什么结果中没有显示1？出于同样的原因，回报是较低水平（2，a）和较高水平的结果。如果将“result”更改为全局变量，结果将是[1，2，'a']

致以最诚挚的问候

Answer 2

函数f返回深度优先搜索遇到的第一个平面列表的（浅）副本。你知道吗

为什么？首先让我们看看基本情况：一个包含no列表的列表。就像[1,'a',2,5]。在这种情况下，if语句将始终成功，因此e的所有元素都将添加到result并返回result。你知道吗

那么递归的情况呢。这意味着有一个列表元素。比如[1,['a',2],5]。现在对于第一个元素，if成功，因此1被添加到result列表中。但是对于第二个元素['a',2]，if失败了。这意味着我们使用['a',2]对f执行递归调用。现在由于该列表不包含任何子列表，我们知道它将返回该列表的副本。你知道吗

但是请注意，我们立即return返回递归调用的结果。所以从我们使用else分支的那一刻起，result就不再重要了：我们将返回f(e)返回的内容。你知道吗

如果我们假设我们不能构造一个无限深的子列表循环（实际上我们可以，但在这种情况下，我们将得到一个堆栈溢出异常），我们最终将获得一个平面列表并获得该副本。你知道吗

示例：如果我们采用您的示例输入[1, [[2, 'a'], ['a','b']], (3, 4)]。我们可以追踪通话。因此，我们首先对该列表调用f，它将生成以下“trace”：

# **trace** of an example function call
f([1, [[2, 'a'], ['a','b']], (3, 4)]):
    result = []
    # for 1 in L:
    # if type(1) == list: # fails
    # else
    result.append(1) # result is now [1]
    # for [[2,'a'],['a','b']] in L:
    # if type([[2,'a'],['a','b']]) == list: succeeds
    return f([[2,'a'],['a','b']])
                      result = []
                      # for [2,'a'] in L:
                      # if type([2,'a']) == list: succeeds
                      return f([2,'a'])
                                        result = []
                                        # for 2 in L:
                                        # if type(2) == list: fails
                                        # else:
                                        result.append(2) # result is now [2]
                                        # for 'a' in [2,'a']:
                                        # if type('a') == list: fails
                                        # else:
                                        result.append('a') # result is now [2,'a']
                                        return [2,'a']
                      return [2,'a']
    return [2,'a']

扁平化：

如果希望将列表展平，而不是返回第一个平面列表，可以将代码重写为：

def f(L):
    result = []
    for e in L:
        if type(e) != list:
            result.append(e)
        else:
            result += f(e)
    return result

请注意，这将仅展平lists（甚至不展平lists的子类）。你知道吗

Answer 3

posted函数在运行到第一个不包含列表的自下而上列表元素时返回/退出-这会阻止遍历递归的所有进一步分支。例如：

print( f([1, [[2, 'a', [3, 'b', [4, 'c']]], ['a','b']], (3, 4)]) )
# gives: [4, 'c']
print( f([1, ['X','Y'], [[2, 'a', [3, 'b', [4, 'c']]], ['a','b']], (3, 4)]) )
# gives: ['X','Y']

造成这种行为的关键点是线路

result = [] 

这会将函数每次调用的结果列表重置为空列表。这样，递归调用链只返回一个项。你知道吗

顺便说一下，下面的函数f实现了你所期望的，不是吗？你知道吗

def f(L, result):
    for e in L:
        if type(e) != list:
            result.append(e)
        else:
            f(e, result)

result=[]; f([1, [[2, 'a', [3, 'b', [4, 'c']]], ['a','b']], (3, 4)], result) print( result )
# gives: [1, 2, 'a', 3, 'b', 4, 'c', 'a', 'b', (3, 4)]
result=[]; f( [1, ['X','Y'], [[2, 'a', [3, 'b', [4, 'c']]], ['a','b']], (3, 4)], result); print( result )
# gives: [1, 'X', 'Y', 2, 'a', 3, 'b', 4, 'c', 'a', 'b', (3, 4)]

注意：（3，4）元组不是列表。。。你知道吗

上面的函数f从一个列表中收集项目，如果这些项目本身不是一个列表。在特殊情况下，当列表中的项是一个列表时，函数将调用自身从该列表中收集项。通过这种方式，从层次结构中的所有元素都被收集起来，无论需要挖掘多深。这就是递归的美妙之处——一个函数调用它自己就可以实现访问树上所有分支及其叶子的“魔力”：