W7: Recursion

To state it simply, recursion in computer programming is when a function calls itself. One might ask, like I did at first, how a recursive function is useful if its definition implies that it runs for eternity?

Trying to call an improperly written recursive function, for example:

    def f(x):
        return f(x)

will indeed get you:

    RuntimeError: maximum recursion depth exceeded.

Which basically means that Python apologizes for being unable to run the function infinitely. So the example above is not exactly a recursive function.

Good recursive functions will have two basic components. First, a "base case" which tells the computer what to do once a certain condition is met, and second, a "recursive step" where the function calls itself.

Consider the following example. Suppose you have jar containing two flavors of candy: mango and raspberry. You detest mango but love raspberry. You blindly pick out one piece of candy at a time. If it's raspberry, you eat it and walk off. If it's mango, you discard it, and reach again. If you reach the bottom of the jar, you walk off.

In this example, the function can be seen as you reaching into the candy jar. The base case is finding a raspberry candy, eating it, and walking off. Here, walking off the same as exiting the function and it also occurs if the jar is empty. The recursive step is finding a mango candy and reaching in the jar, again. This is the part where the function calls itself (i.e. you call on your arm to repeat the action).

As you can see from the example, the base case is equally as important as the recursive step. The base case is the entire purpose of the function and the recursive step is the means to get there. A bad base case is equally as detrimental as a faulty recursive step. Furthermore, although it is usually very easy to see when recursion is required (do you have to do the same thing multiple times?) it is not so easy to decide what exactly you want to get out of it.

It is apparent how useful recursion is in computer programming. A programmer may have something they want to achieve that will take several loops but they do not know exactly how many. Thus recursion is necessary:

    1) Recursion saves space by replacing the many lines of code for (regular) loops
    2) It is more readable and better follows the human process of problem-solving
    3) It can achieve something that may take zero loops or hundreds of loops.

The last point is especially demonstrated when working with objects such as Trees, where a Tree can be a single node or conversely hundreds upon hundreds of nodes and leafs. A single recursive function can, for example, count how many nodes there are in any type of Tree, no matter what size. Such cannot be achieved by a single regular function.