Recursion

When I first saw recursion, I thought it was a pretty cool. It was a neat little trick that can solve certain problems while being very succinct when written. However, this interpretation is purely superficial and completely masks the true power of the technique and how central it is to computer science. Recursion is used in many powerful algorithms and there are man problems that exist which are most efficiently solved through recursion.

At its core, recursion is about breaking a problem into smaller versions of the same problem and then recursively breaking those smaller problems into even smaller problems until you reach a base case which can be solved directly. Using the solution of the base case, you then move up the chain solving each problem until the original problem is solved. An example of this would be a function which calculates the factorial of an integer n. The factorial of n or n! is equal to n(n-1)...1. One can immediately see that n! = n(n-1)!, this serves as the so-called recursive case and by definition we'll take 0! = 1, which will be the base case. So to solve n!, you  would to solve (n-1)! and to solve (n-1)! you would solve (n-2)! and so on. If you keep applying the same procedure you eventually reach the base case 0! and then you can evaluate the entire chain of factorials before it. An implementation of this algorithm in python would be the following:

def factorial(n: int) -> int:
    # recursively calculates n! for int n >= 0
    if n == 0:
        return 1 # base case
    else:
        return n*factorial(n-1) # recursive case

We can examine how this function works by tracing the code when it calculates something simple, like for example 3!.

factorial(3) ->  [3*factorial(2)] -> 
3*[2*factorial(1)]  -> 3*2*[1*factorial(0)] -> 3*2*1 -> 6

So it essentially multiplies n by a recursive call on n-1 and it keeps doing this recursively, generating the familiar n(n-1)...1 expression as expected.   

Now this is not a particularly interesting example of recursion, in fact recursion is not necessary to solve this problem and iteration would work just fine so let's move on to a slightly more interesting example. Take a function which sums a list of nested lists, i.e. a list within a list within a list, etc. Summing a list of nested lists is the same as summing each nested list and then summing the result of those sums. If an element within a nested list is another nested list, then you apply the same procedure until you reach the base case which is just a list of integers. An example of a function using this algorithm in python would be the following.  

def sum_list(L: list) -> int:
    # recursively sums a list of nested listed lists L
    return sum([sum_list(element) if isinstance(element, list)                   else element for element in L])

So this function iteratively goes through the elements of the list L and checks if each element is a list or not. If it is, the function then calls itself on the element and then replaces the element with the result of that function call and if not, the function leaves it alone. Once the list is exhausted, it then returns the sum of the list. It will keep evaluating recursive calls until the list L is entirely filled with integers at which point it just sums everything.

One of the wonderful things about this function is that it can handle lists of any arbitrarily large depth and it will sum any arbitrarily large number of lists. This ability to scale is one of the most powerful aspects of recursion.

 Now notice that in both of these algorithms, each recursive call brings the function closer to the base case. This is extremely important because if either a) the base case doesn't exist or b) the base case is never reached, then the function leads to an infinite recursion which will not return anything.

Now the above talks about recursive functions/algorithms, there is another very important area of computer science in which recursion is of utmost importance, that being recursive data types. In a recursive data type, the definition of the data type links to itself. An example of which is a linked list, which is defined to have a head, which contains some data, and a tail, which is (a reference to) another linked list. The main advantage of recursive data types is that they can grow dynamically to arbitrarily large sizes if need be, in contrast to statically-defined data types which are fixed after creation. For example, a list created using linked lists need not have all its elements stored together in memory like a static array implementation would require, elements can be freely added or removed by simply creating another linked list and then changing the appropriate memory references. One should not be surprised to hear that recursive functions and algorithms lend themselves surprisingly well to working with these data types.

So in conclusion, recursion is very useful whenever a problem can be broken up into smaller instances of the same problem.  Recursive solutions should be admired for being very succinct answers to complicated problems and for their ability to handle an arbitrarily amount of scaling. One should look for recursive solutions whenever possible but one must also recognize that they are not always possible to find in many cases.