這種交錯遞歸函數是如何工作的？

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

我認爲它很容易通過這種方式來了解...