Week 7: Recursion

In computer science, recursion is (loosely) the idea of defining something in terms of itself. It is useful as it allows for flexible, concise code. My experience with recursion in 148 has been entirely in the context of using it for defining functions in Python, but I suspect it can used in other ways/types of definitions.

Usually, these recursive definitions have at least two parts to them, both of which lie behind an if statement. The first is the "exit clause", for cases in which the function is called on the most basic elements. It signifies the end to that particular recursive loop, and is comparable to the "base case" of proofs by induction.

The other half is more interesting, and is where the actual recursion takes place. If the given value does not satisfy the exit clause, the function will call itself again on the object. To prevent infinite loops from occurring, this new call shouldn't be on the exact same object; it should be on a modified version of the object, or a specific part of the object. Continuing the induction analogy, this would be the inductive step.

For example, when calling a function on a list of nested lists, often you will want it to be evaluated on each of the most nested lists. A recursive function would see if the current list contains more lists, and if it does, call itself on each of the smaller lists. Without recursion, this would likely require multiple functions and complicated regular for-or-while-looping.

When writing code, the recursive call should be placed after the exit clause. This is to ensure that the recursive calls don't go on indefinitely, since the exit clause will never be reached if it comes after. One has to be careful not to accidentally create infinite loops. Thorough testing is necessary.