Week 7

Recursion

Recursion is one of the main ideas of Computer Science. A common thing done when writing code is to divide the problem into smaller problems and then combine the results. It is mostly used when the problem can not be solved by a for or while loop for example, checking elements in an arbitrarily nested list. One of the exercises we did in lecture was tracing this code:

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  

In the code above, the function sum_list is calling itself inside its own definition. It keeps on looking inside the nested lists until there are no lists left and returns the sum in the end. There are three helper functions used in this code, sum, isinstance and sum_list. Our base case is when L is an integer, we do not need recursion for this. So, when the function is called on an integer, it will the integer. For example, sum_list(25), L is not a list, so the if condition is false and it returns L which is 25 in this case. Here, recursion is needed when calling the function on nested lists. For example,

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

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

                                      -> sum([4, 9, 9])

                                      -> 22

Recursion is basically a method where the solution of a problem depends on smaller instances of the same problem. Recursion is very useful, big problems can efficiently be solved by dividing the problem into smaller versions and then combine the results to get the solution to the big problem. Recursion actually helps in saving up so many lines of code. Recursion is so far my favourite topic. Although sometimes it does get quite hard to trace the code but it is an extremely useful thing. A code with recursion looks beautiful but it is hard to understand at first.