这个交错递归函数是如何工作的？

Question

我想搞明白这个递归函数到底是怎么工作的。我知道它接收两个列表并将它们交错在一起。有人能帮我解释一下函数里面的嵌套部分吗？

def interleave(lst):
    def interleaveHelper(lst1,lst2):
        if not lst1:
            return lst2
        elif not lst2:
            return lst1
        return lst1[0:1] + interleaveHelper(lst2, lst1[1:])
    return interleaveHelper(lst[:len(lst)/2], lst[len(lst)/2:])

Answer 1

交错函数其实就是 interleaveHelper(l1, l2)。假设你有两个列表，l1=[1,2,3] 和 l2=['a', 'b', 'c', 'd', 'e']，我们用这个例子来说明。为了简化，我们可以把 interleaveHelper(l1, l2) 简称为 f(l1,l2)。那么，最后一行的结果会是：

f([1,2,3], ['a', 'b', 'c', 'd']) = [1] + f(['a', 'b', 'c', 'd'], [2,3])
                                 = [1] + ['a'] + f([2,3], ['b', 'c', 'd']) 
                                 = [1, 'a'] + f([2,3], ['b', 'c', 'd'])
                                 = [1, 'a'] + [2] + f(['b', 'c', 'd'], [3])
                                 = [1, 'a', 2] + f(['b', 'c', 'd'], [3])
                                 = [1, 'a', 2] + ['b'] + f([3], ['c', 'd'])
                                 = [1, 'a', 2, 'b'] + f([3], ['c', 'd'])
                                 = [1, 'a', 2, 'b'] + [3] + f(['c', 'd'], [])
                                 = [1, 'a', 2, 'b', 3] + f(['c', 'd'], [])
                                 = [1, 'a', 2, 'b', 3] + ['c', 'd']
                                 = [1, 'a', 2, 'b', 3, 'c', 'd']

我觉得这样理解起来非常简单……

Answer 2

其实这里有两个不同的东西在使用。interleaveHelper这个函数会先从第一个列表中拿出第一个元素，然后再递归调用自己，不过这次是把两个列表的位置调换了。也就是说，下一次调用的时候，它会从第二个列表中拿出第一个元素。

现在这个问题澄清了，你应该能看到另一个函数：interleave。这个函数会把一个列表分成两半（见最后一行），通过切片的方式来实现（比如说，lst[:len(lst)/2]就是前半部分）。然后它会把这两半混合在一起。

这就意味着这个函数会像洗牌一样把列表里的元素打乱：先分成两半，然后一个一个地混合在一起。:-)

一个简单的例子是：

In [2]: a = range(10)

In [3]: interleave(a)
Out[3]: [0, 5, 1, 6, 2, 7, 3, 8, 4, 9]

Answer 3

这个递归的嵌套函数首先取第一个参数的第一个元素，然后在递归调用时交换参数（去掉那个第一个元素）。

比如说，给定一个列表 [1, 2, 3, 4]，外层调用会把这个列表分成两部分，然后递归会这样进行：

([1, 2], [3, 4]) -> [1] + ([3, 4], [2])
    ([3, 4], [2]) -> [3] + ([2], [4])
        ([2], [4]) -> [2] + ([4], [])
            ([4], []) -> return [4]  # lst2 is empty, return lst1
        return [2] + [4]
    return [3] + [2, 4]
return [1] + [3, 2, 4]