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

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

递归嵌套函数只取第一个参数的第一个元素，然后交换递归调用的参数（减去第一个元素）。

所以给出的列表[1, 2, 3, 4]，外呼拆分列表中2个，然后递归的作用：

([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] 

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

交错功能实在是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'] 

我认为它很容易通过这种方式来了解...