Python 递归示例说明

Question

目前正在学习麻省理工学院的 OpenCourseWare 计算机科学在线类(class)，但我在尝试理解其中一个递归示例时遇到了困难。

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

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

我觉得输出应该是:

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

如有任何帮助，我们将不胜感激!

Answer 1

函数f返回它在深度优先搜索中遇到的第一个平面列表的(浅)副本。

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

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

但请注意，我们立即返回该递归调用的结果。因此，从我们采用else分支的那一刻起，结果就不再不重要了:我们将返回f(e ) 返回。

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

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

# **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
    <b>return</b> f([[2,'a'],['a','b']])
                      result = []
                      # for [2,'a'] in L:
                      # if type([2,'a']) == list: succeeds
                      <b>return</b> 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']
                                        <b>return</b> [2,'a']
                      <b>return</b> [2,'a']
    <b>return</b> [2,'a']

扁平化:

假设您想要展平列表而不是返回第一个展平列表，您可以将代码重写为:

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

请注意，这只会展平列表(甚至不会展平列表的子类)。