The topic in week 4 is recursion. If we want to sum all nums in a nest list, a recursion method will be useful. Recursion means we can let a fuction call itself in order to solve this problem. Some recursion codes are hard to understand so we can trace the code step by step:
def sum_list(L):
’’’
(arbitrarily nested list of int or int) -> int
Return the sum of all ints in L.
>>> sum_list([1, [2, 3], [4, 5, [6, 7], 8]])
36
’’’
if isinstance(L, list):
return sum([sum_list(x) for x in L])
else:
return L
Trace:
sum_list([[4,2], 1, 8]) --> sum( [ sum_list(4), sum_list(1), sum_list(8) ] )
--> sum( [6, 1, 8])
-->15
For some recursion, if we enter a empty list it may cause error, e.g.
def nested_concat(L):
’’’ (list or non-list) -> int
Return 0 if L is not a list, or the maximum of len(L)
and the lengths of L’s non-empty sublists.
Assume: L is a non-list, or a non-empty list
>>> length(17)
0
>>> length([1, [2, 3, 4, 5], 6])
4
>>> length([1, [2, 3, [4, 5]], 6])
3
’’’
if isinstance(L, list):
return max(len(L),max([length(x) for x in L]))
else:
return 0
Therefore, we can add a str to the list, so it will return 0:
if isinstance(L, list):
return max(len(L),max([length(x) for x in (L + ['hi']]))
else:
return 0
Recursion can also be used for drawing diagrams, such as a snow flake or a tree diagram. Divergence will keep going until it mathes the depth that we want.
