Week 7 - Recursion

For me, tracing recursion is not really a difficult concept, as it involves going into a list and just using a function on the various elements in the list. It basically involves a function calling itself, as mentioned previously. An example of recursion on a list can be:

L = [[1, 5], [9, 8], [1, 2, 3, 4]]

sum([sum_list(x) for x in L]) - this takes the sum of elements at each index position in L, or just x if x is an integer

To trace this, just do:

>>> sum_list[[1, 5], [9, 8], [1, 2, 3, 4]]

>>> sum([sum_list[1, 5], sum_list[9, 8], sum_list[1, 2, 3, 4]])

>>> sum([6, 17, 10])

33

Tracing inside lists more complicated than this one can be confusing, but if one just traces simpler examples first, he/she can automatically write the result of the nested list in upcoming examples of lists of increasing complexity. They will not need to trace through individual elements in the nested lists again, such as [sum_list(9), sum_list(8)]. In fact, when one moves on to tracing more and more complicated list calls, they must not do this. This is because they would have already traced through like this in previous simpler examples.

The depth of the list is also not that difficult to understand. It took me some time, however, to understand how the code for determining the maximum depth of a list made sense and worked. This is the code for determining the depth for the list:

if instance(L, list):

     return 1 + max([depth(x) for x in L])

else:   # L is not a list

     return 0

At first, I was confused as to how this function was able to determine the depth of a nested list with just the word depth(x) in its code. Before finding out the solution, I thought about it to myself and got the correct answer just by seeing the number of lists and nested lists. A simple example of this is:

>>> depth(17)

0

>>> depth([1, 2, 3])

1                   # because there is only one list

>>> depth([3, 4, [2, 5], 9])

2                   # because there is a list and nested list

Later, I figured out how the code worked, just by remembering that it was nothing but recursion at action! Since it called itself, depth(x) works on a nested list, such as [2, 5], just like it would work on a list without a nested list, such as [1, 2, 3]. 

Furthermore, the professor also covered how to find the maximum number in a simple list, lists that are one deep, two deep and etc. For example, this is a call to a simple/flat list:

>>> rec_max([2, 5, 1, 3])

>>> max([rec_max(2), rec_max(5), rec_max(1), rec_max(3)])

>>> max(2, 5, 1, 3)

5

When the list increases in complexity, it must be evaluated in the same way as the sum_list() and depth() functions. One thing that I found particularly fascinating was recursion in a file named tree_burst.py. This gave a visual application of recursion and I found this particularly interesting, as it involved red, blue and green arrows branching out in 3 different directions. These arrows formed a ternary tree. I didn't fully understand how this implementation of recursion worked, but I enjoyed it as I like learning through visuals.

By far, this course continues to become more and more interesting, and challenging as well. I look forward to upcoming material and am a bit apprehensive of their level of difficulty.