Week 7: Recursion

    Recursion is a programming strategy, and a major topic in this course. It makes the functions of computer programs a ton more efficient, but it takes more sophisticated thinking to write. All recursion really is, is including a function call of itself within the body of a function. For example, having a line in the function f(x) that calls f(x-1). It sounds pretty simple, but there's a lot of guidelines to consider when making a recursive call or else you will lead to bugs and errors.

    First off, you must include a base case. Your function won't stop running if there isn't a set point to reach. Recursive functions are meant to break down a task into smaller versions of the same task, until it can't be broken down anymore. The point where the task can no longer be broken down is called the base case. I'll take an example of one we used in class, modified so the body isn't a single line, just to make it easier to read.

def preorder(tl: 'TreeList') -> list:
    """
    Return list of values in tl in preorder

    >>> preorder([5, [4, None, None], [3, [2, None, None], [1,                       None, None]]])
    [5, 4, 3, 2, 1]
    """
    if tl is None:
        return []
    else:
        return ([tl[0]] + preorder(tl[1]) + preorder(tl[2]))

In case you haven't noticed, this is the pre-order traversal I explained in my last post, now as a python function. In the end of that post, I explained that a tree can be represented as a list of [int, Tree or None, Tree or None] I also mentioned a simple recursive 3-step approach to doing all pre-order traversals. All three steps of that approach are expressed in the else statement above. The if statement is our base case. This is the non-recursive action that the program makes when the problem has been broken down as far as it should go. t1 is None translates to the root / child node not existing, therefore adding nothing to the resulting list that represents the pre-order traversal.

    Recursion can get much more complicated than this. To make good use of recursion, you need lots of practice with writing different function bodies to develop a good sense of what actions can work recursively, and what actions should be part of the base case. A more complicated example of recursion is in a function learned in class that writes the steps to solving the Towers of Hanoi game with 3 stools, in the least steps possible. That function involved breaking down the game into 3 smaller recursive steps:

1) Move all rings except bottom to intermediate stool.

2) Move bottom ring to destination stool.

3) Move all rings except bottom to destination stool.

When you begin step one, all three steps are used again just to complete step one. That means the second-to-bottom ring is used as the bottom ring when step 2 is called during the process of completing step 1. Also, that second-to-bottom ring will be taken to the overall intermediate stool. Every function call changes what the source, destination, and intermediate stools are, to make sure the function still works. When enough rings are involved in this game, the game can be broken down to the point where the (third, fourth, fifth, etc.)-to-bottom ring is used as the bottom ring. This is recursive to the point where there is only one ring above the "bottom" ring, and that ring is simply taken to whatever the current intermediate stool may be.

    In Assignment 1, I invented my own set of recursive steps for a function that completes the Towers of Hanoi game with 4 stools, using the same ideas. It was very efficient and it broke the game down into 5 smaller recursive steps:

1) Move all rings except the bottom two to i1 (since there are 4 stools, the two intermediates are labeled i1 and i2)

2) Move second-to-bottom ring to i2

3) Move bottom ring to destination

4) Move second-to-bottom ring to destination

5) Move all rings except the bottom two to destination

My function looks like this in python:

def fourD_m_c(n, source, inter1, inter2, dest):
    if n == 2:
        print("Move top cheese from {} to {}".format(source, inter1))
        print("Move top cheese from {} to {}".format(source, dest))
        print("Move top cheese from {} to {}".format(inter1, dest))
    elif n > 2:
        fourD_m_c(n - 2, source, inter2, dest, inter1) #all but bottom 2
        fourD_m_c(1, source, inter1, dest, inter2) #second to bottom
        fourD_m_c(1, source, inter1, inter2, dest) #bottom
        fourD_m_c(1, inter2, source, inter1, dest) #second to bottom
        fourD_m_c(n - 2, inter1, source, inter2, dest) #all but bottom 2
    else:
        print("Move top cheese from {} to {}".format(source, dest))

    The words ring and cheese can be used interchangeably. The five steps I explained before are expressed under the elif n > 2 statement. The else statement is the base case, and I still haven't at all explained the purpose of the body of code below the if n == 2 statement. This is sort of like a second base case and this was necessary because my 5 steps don't know how to handle the game when the bottom two rings are in fact all of the rings involved in the game. Therefore, the purpose of this body of code is to manually move those two rings when the situation arises. This body of code is only ever reached when the overall game involves an even number of rings. When the overall game involves an odd number of rings, the game is never broken down into smaller games that involve exactly 2 rings, so this body won't be needed or used.

    My function completed the 4-stool game in less steps than the function given in our lecture. I was proud of my function, but my assignment partner discovered an even more efficient function, and that function was submitted instead :<