In week 4, we learned a neat little thing called recursion. It involves calling a function within its own function definition, which was a quite confusing concept for me. However, through tracing many instances of recursion, I was able to understand that it worked because of the "else" component in the if-statement, which doesn't result in the function calling itself.
For example, if given the following function:
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
If L is not a list, L is returned. If L is a list, every element of L is passed as an argument to sum_list, which then checks if each element is not a list and should be returned, or if it is a list and sum_list must be called again for each element within that nested list. I initially wondered how the function could return anything if sum_list would just be called indefinitely, but then I realized that at some point, the nested lists would end, and the sum of that would be returned into the list that is one layer outside, which would subsequently return more sums, until the function produced a final integer value. Thus, the else-statement is crucial for the function not to become an infinite loop.
I found recursion to be a clever concept, because all one has to do is prove the function works for the most minimalistic instance of the function, and work from there. For example, in the case of sum_list, if the function works for a single integer, one can apply that to a list of single integers. If it works for a list of depth two, one can apply that to a list of lists of depth one, and so on, in a method very similar to proof by mathematical induction.
No comments:
Post a Comment