Week 7: Recursion, a Summary

After many weeks spent trying to understand recursion, brows furrowed in befuddlement, today is the day we summarize recursion.

Recursion, in short, is the strategy of breaking down a problem into a single, self-referential function. A convoluted problem can be reduced to a single line solution.

A recursive function has a base case and a general case; the base case is first employed at the deepest point in the input, that is the point at which we can no longer pass a value to the recursive function.  The first value is returned at this point, which allows every recursive call before then to also return a value based on the preceding return values.  Aside from the return statement at the deepest point in the input, all the other recursive calls proceed according to the general case.

The result of this approach, which is both remarkably simple in appearance and difficult to grasp on an intellectual level, is a function with emergent properties, accomplishing in a single line of code what, in our naivete, we expect would require several lines of code.

Despite its simplicity, there are also certain nuances to recursion: for one, having an explicit base case is not necessary when the general case is structured in a manner that will not exceed maximum recursion depth.  Many also err when they fail to consider the most basic input (e.g. an empty list) and the importance of accommodating that (e.g. by appending [0] to the empty list when taking it max).