Week 7 – Recursion

Though I've mostly been writing about recursion for my weekly topics (as that is what we've been learning), this post is to be solely dedicated to this very important concept.

Recursion is the concept of calling a function from within itself. Usually we would define a function and then call it after we've completely finished writing its body and output. But in recursion, we define a function and call it within its own body. This is very useful with objects whose structures are defined recursively, and we've seen it used with binary trees, linked lists, nested lists, and other types of the sort.

A binary tree, for example, has an internal node as its root and left and right children, which are also binary trees themselves. So to count the number of nodes in the tree, we would count the number of nodes in the left subtree, then count the number of nodes in the right subtree, then add 1 more node for the internal node at the root. This turns into a function like the following:

def count(n: Tree):

return 1 + sum([count(n) for n in t.children])

We use the count function inside its body because we are also counting the number of nodes in the tree's left and right children. And what are those children? Trees. So it only makes sense that we would use the same function for the same operation. And when there are no children, the recursive calls stop because t.children will have no values and the return value will only be 1. Then the function will begin to wind back up, counting 1 for each leaf and adding up the number of leaves in a child, then adding 1 for that node and combining the value with the value of the other child, and finally adding 1 to account for the root node.

So, as seen, we have no doubt focused a lot on recursion this semester. But what is so important about it? Why is it so useful that we are expected to know how it works and to be able to use it in any applicable situation?

The way I see it, our golden rule is a key reason: laziness. Recursion will usually provide the easiest and shortest solution to a problem.

It's the easiest to write, read, and understand code, which makes it less work for anyone doing anything with the program.

First, as the initial writer of the code, simply calling the function that you just wrote (since you know it does exactly what you want) is much easier than writing nested loops or having counter variables to try and keep track of how deep you are into the structure...and other things like that. In most cases a function involving a recursive structure will be very difficult to write non-recursively. Here, recursion is easier because it will automatically stop as long as you provide the action to perform when the base case is reached. You don't need to know when the base case is reached (and knowing this is hard because there will be many layers/depths, one within another, so you can't really count them), because the function will recognize that.

Afterwards, when the next person has to read your code, they will see the places where you've called the function recursively and think something like, 'Ah, they just did the same operation on the next level of this object.'. In other words, when reaching a level where we already know what happens, we can just stop and substitute the previously-found result. This is also what we do when writing recursive code.