Week 7 - RECURSION

RECURSION

Recursion is a way of defining a functions in which the function is applied in its own definition. It 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 exercise 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

The function calls itself on each list. This is how recursion works.