This week, we learned recursion. Basically, recursion is a technique that using the function itself as a helping function and call itself. With this method, we can dive into many sub problem and solve each of them by the similar technique and finally solve the bigger problem.
Recursion is like doing a puzzle. Whenever you get into a cross road, you choose one first, and when you touch the bottom, the program start to backtracking and try the other possibility. So we can traverse all the possibility with recursion because we tried all the path from top to bottom. To be more precise, let's say we want to find the sum of a list, for example [1,[1,2],3,4]. Using the normal method sum function will give us a error because the element [1,2] is also a list in the whole list. To solve this problem, we can use recursion.
def Sum( L):
if isinstance(L,list) :
return sum([Sum(x) for x in L])
else:
return L
This function is easy to understand, whenever we meet a list, we call Sum again to put all the sub element in to a list, and finally return all the sum and get the answer. However, I met a problem that require us to find the longest length of a list. For example, [1,[1,2,3]] will return 3, because the sub list [1,2,3] has length 3 which is the longest. If we use the same method as before
def length(L):
if isinstance(L, list):
return max([length(x) for x in L])
else :
return 0
we will have two problems. Firstly, we did not add the length of the most outside list in the comparing list. Secondly, what we put into the comparing list is all the sub element instead of the length of the list. So we change it to
def length (L):
if isinstance(L, list):
l = []
for x in L:
if isinstance (x,list):
l.append(len(x))
l.append(len(L))
maxLength = max(l)
print(l)
for x in L:
maxLength = max (maxLength,length(x))
return maxLength
else:
return 0
will solve the problem because it get maxLength in a level and compare it with sub list leave *maxLength.
No comments:
Post a Comment