如何理解特定嵌套列表中的递归？

Question

我一直在试图获得与递归更好，作为一个练习，我试图创建一个返回和下面的嵌套列表中的所有int元素功能：[1, [2, 3, [4], []], [5]]

后几个小时，我放弃了，发现了一个我想在这里理解的美丽解决方案。

def lsum(l): 
    if type(l) is int:   
     return l 
    elif type(l) is list and len(l) > 0: 
     print l 
     return lsum(l[0]) + lsum(l[1:]) 
    return 0 

上面运行的功能和打印如下：

[1, [2, 3, [4], []], [5]] 
[[2, 3, [4], []], [5]] 
[2, 3, [4], []] 
[3, [4], []] 
[[4], []] 
[4] 
[[]] 
[[5]] 
[5] 

问：什么我不明白是怎么当我们的名单是[[]]函数发现[[5]]因为[[]][0]是[]和[[]][1:]是[]？

Answer 1

这种修改可以帮助你了解发生了什么：

def lsum(l, depth=0): 
    print depth, l 
    if type(l) is int:   
     return l 
    elif type(l) is list and len(l) > 0: 
     return lsum(l[0], depth+1) + lsum(l[1:], depth+1) 
    return 0 

在使用中：

>>> lsum([1, [2, 3, [4], []], [5]]) 
0 [1, [2, 3, [4], []], [5]] 
1 1 
1 [[2, 3, [4], []], [5]] 
2 [2, 3, [4], []] 
3 2 
3 [3, [4], []] 
4 3 
4 [[4], []] 
5 [4] 
6 4 
6 [] 
5 [[]] 
6 [] 
6 [] 
2 [[5]] 
3 [5] 
4 5 
4 [] 
3 [] 
15 

来看待它的另一种方式：

0 : [1, [2, 3, [4], []], [5]] 
    /   \   
1 : 1 [[2, 3, [4], []], [5]] 
      /   \ 
2 :  [2, 3, [4], []]  [[5]] 
     /  \   | \ 
3 : 2  [3, [4], []] [5] [] 
      / |  /\ 
4 :   3 [[4], []] 5 [] 
       / \ 
5 :   [4]  [[]]  
      /\  /\ 
6 :   4 [] [] [] 

的Split这里是l[0]在左边，l[1:]右侧之间。如您所见，发现5的分支与探索[2, 3, [4], []]的分支分开，并找到空列表[]。

---

请注意，例如， ininstance(l, int)通常优于type(l) is int。

Answer 2

你可以做以下一些修改

def recursive_sum(l): 
    if type(l) is int:  # If an int, just return the value 
     return l 
    elif not l:   # If an empty list, return 0 
     return 0 
    else:   # recursively call this function, and sum the returned values 
     return sum(recursive_sum(i) for i in l) 

测试

>>> a = [1, [2, 3, [4], []], [5]] 
>>> recursive_sum(a) 
15