Recursion

Recursion is a very powerful way of defining functions and data structures. Whenever a problem has self-similarity in its solution, that is whenever it breaks down into simpler problems of the same type, recursion can be used to define a function to solve the problem and achieve the desired result. Also, whenever an object has self-similarity in its structure, recursion can be used to model the object as a recursive data structure. This is because recursion works by using self-reference: the recursive functions call themselves, which might in turn call itself again with a more simple argument, and so on and so forth until one or more base cases of the function are called with the simplest arguments possible where the solution is trivial and defined explicitly. As long as the base case is always reached, the function is well-defined. Recursive data structures work in a similar way: a recursive data structure is defined in terms of simpler cases of the same recursive data structure, which eventually reduce to a simple base case of the data structure. For example, a binary tree can be defined as a list of an object and two binary trees, each of which is a list of an object and two binary trees. A binary tree defined this way with nodes referring to a finite number of objects is well-defined, since eventually the binary trees in the lists reduce to the base case of an empty binary tree, which could be represented by None.

What first struck me was the apparent complexity of the problems given to us to be solved by a recursive function. For example, it seemed an insurmountable problem to find the maximum element of a nested list of integers, since each nested list that could be passed to a function could have a wildly different structure. However, each of the different structures would have a similarity, they are all self-similar: each nested list is made up of smaller nested lists, the degenerate base cases of which are ordinary lists integers. It was then possible to write a very simple, one-line recursive function to find the maximum element of a nested list, and even though it made complete sense that the function would work, it still seemed surprising that it actually did! The solution seemed too simple. It was quite clear to me how recursion worked—it is after all just mathematical induction in disguise and thought of in the reverse way, an idea which I am very comfortable with from doing mathematical proofs—however the power of recursion still makes it seem like magic.

Writing my own recursive functions took a little while to get used to. At first I would begin by focusing on the general case of the problem, trying to figure out a way to reduce it to a simpler case that would eventually reach a base case. This approach was sometimes difficult when the self-similarty of the problem wasn't immediately obvious and when the problem was self-similar in more than one way it wasn't clear which approach would work best. A strategy I found more effective was to first consider degenerate, base cases and what the function would return, then pretend as if I had a solution to the an arbitrary case of the problem and extend that solution to the next case of the problem. Then, looking in reverse, the extended solution can be used as the general solution which breaks down to the solution to arbitrary case it was extended from, and so on and so forth, until the base case is reached. I was able to figure out the recursive solutions much more quickly with this approach, and writing recursive functions became more easy. The lab on recursive functions helped me develop the method of thinking of recursion that works best for me. Recursive functions are a great deal of fun to write and the results when first testing out a successfully written one are very satisfying.