Recursion

      Recursion is a pretty new stuff that we just learned in class. It is somehow different from what we already known about python.
      Recursion is used in functions to solve problem with unknown layers and cannot be solved simply by for or while loops, for example, checking elements in arbitrarily nested-lists and that is the main problem that we've trying to solve with recursion so far. Recursion and loops are doing the same job which is repeating some lines of code, but the difference between them is that when recursion is used in a function, it is calling the function itself inside this function.
      This is an example of recursion:

    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

      This function is summing all the elements in the list up. The recursive idea in this function is that we keep looking inside nested-lists until there are no nested-lists left. As we can see in this function, a recursion contains an if statement. This if statement is important when we are trying to make a recursion. How do we so that?
      First, we need a base case which can be done without recursing. Base case is also the thing we are looking for using the recursion. In this case, is when L is an int, so that we don't need to look inside lists to find int and there is no need so sum up an int so we return that int. Now we have our first part of the code. Then we need to consider other cases. If L is a list, we should check the elements in L. If the element is an int, we return it and if it is a list, we keep checking the elements inside it. This is where we need recursion. We call this function on every element in L, so that this function does what we want. Using a list comprehension to collect the results and sum them up. The recursion basically looks like this: 'if base case, else: recursion'.
      When running this function on the doctest, the process should be as follows:
      sum_list([1, [2, 3], [4, 5, [6, 7], 8]])
-> sum([sum_list(1), sum_list([2, 3]), sum_list([4, 5, [6, 7], 8])])
-> sum([1, sum([sum_list(2), sum_list(3)]), sum([sum_list(4), sum_list(5), sum_list([6, 7]), sum_list(8)])])
-> sum([1, sum([2, 3]), sum([4, 5, sum([sum_list(6), sum_list(7)]), 8])])
-> sum([1, 5, sum([4, 5, sum([6, 7]), 8])
-> sum([1, 5, sum([4, 5, 13, 8])])
-> sum([1, 5, 30])
-> 36
      Basically what recursion does is it stops and return stuff when we find what we need, int for example, if not we keep checking.