Issue 7: Recursion

In order to understand recursion, one must first understand recursion.
- Anonymous  


Recursion is a notorious source of confusion for many people going into Computer Science. The problem with recursion is that recursion is not intuitive. In recursion a function calls itself to get a value, while in the middle of writing the function. This presents the question of: "How can we write our function in a way to use a value, before we even know what the value is going to be?"

Recursion is used to solve a big problem by solving a series of smaller problems. Divide and conquer if you will. Thus, I found that the best way to approach a recursive problem is to first analyze the simplest scenario, and then work my way up.

Let's take the ADT "SearchList" as an example. A SearchList is a python list with 3 elements.
element 0 is an integer.
element 1 is either None or a SearchList that contains integers smaller than element 0
element 2 is either None or a SearchList that contains integers larger than element 0
We want to create a function that returns whether or not an integer n exist somewhere in the SearchList.

We want to begin by writing out some examples, starting from the simplest case, and going into more complicated cases

def find_num(SL: 'SearchList', n: int) -> bool:
    """
    Return True if n is in SL, False otherwise.
    
    >>> find_num([0, None, None], 0)
    True
    >>> find_num([1, [0, None, None], None], 0)
    True
    >>> find_num([0, None, [3, None, None]], 3)
    True
    >>> find_num([5, [2, [1, None, None], [3, None, None]], [6, None, None]], 6)
    True
    >>> find_num([5, [2, [1, None, None], [3, None, None]], [6, None, None]], 3)
    True
    """

The simplest scenario is finding n whether n is equal to element 0, so we start by writing that.

def find_num(SL: 'SearchList', n: int) -> bool:
    """Omitted for brevity.
    >>> find_num([0, None, None], 0)
    True
    """
    if SL[0] == n:
        return True

Next, we know that if n is not element 0, then it must be smaller or greater than element 0. We know that if n is smaller than the integer 0, then n is somewhere in element 1. 

However, since we are writing this function recursively, we already know that this very function is capable of finding out whether element 0 is equal to n. So instead of writing more code, we can simply call this function to search element 0.

def find_num(SL: 'SearchList', n: int) -> bool:
    """Omitted for brevity.
    >>> find_num([1, [0, None, None], None], 0)
    True
    """
    if SL[0] == n:
        return True
    elif SL[0] > n and isinstance (SL[1], list):
        return find_num(SL[1], n)

We check to see whether element 1 is a list because element 1 could be None. Similarly, if n is greater than element 0, we check element 2 in the same way.

def find_num(SL: 'SearchList', n: int) -> bool:
    """Omitted for brevity.
    >>> find_num([0, None, [3, None, None]], 3)
    True
    """
    if SL[0] == n:
        return True
    elif SL[0] > n and isinstance (SL[1], list):
        return find_num(SL[1], n)
    elif SL[0] < n and isinstance (SL[2], list):
        return find_num(SL[2], n)

Finally, if n is no where to be found, we can simply return False.

def find_num(SL: 'SearchList', n: int) -> bool:
    """
    Return True if n is in SL, False otherwise.
    
    >>> find_num([0, None, None], 0)
    True
    >>> find_num([1, [0, None, None], None], 0)
    True
    >>> find_num([0, None, [3, None, None]], 3)
    True
    >>> find_num([5, [2, [1, None, None], [3, None, None]], [6, None, None]], 6)
    True
    >>> find_num([5, [2, [1, None, None], [3, None, None]], [6, None, None]], 3)
    True
    """
    # [0, None, None]
    if SL[0] == n:
        return True
    elif SL[0] > n and isinstance (SL[1], list):
        return find_num(SL[1], n)
    elif SL[0] < n and isinstance (SL[2], list):
        return find_num(SL[2], n)
    else:
        return False

In this example, there is only a single "branch" or "path" that the code can take, and the final result will only be either True or False. This makes it fairly simple to trace the code, as the function will keep searching until either element 0 is n, and every depth of the recursion will return a True; or the function will reach a None, and then every branch of the recursion will return a False. However, there are also recursive function where each branch returns varying values. We will discuss more on those next time!