Recursion

One of the interesting computer science topics that Udacity CS101 introduces is "recursion". Recursion is where you define a function in terms that in some cases require the function to call itself. This is the main topic of Unit 6 of the course. There are important design considerations to be taken into account if you are going to use "recursion" in your implementation of a function.

1. Base case(s) - It is crucial that your function have at least one combination of inputs that do not trigger yet another recursion. This non-recursive case is called the base case of your function. If you don't have at least one base case, then you are fairly certain to have an unending loop that never produces a final result.
2. Progress - It is similarly crucial that your function make progress toward the base case(s) as it recurses. If you have situations where sometimes the function re-invokes itself with the same inputs and state as it had previously, then it may be more subtle, but almost surely you are stuck in an unending loop that never produces a final result.

Not every programming language supports recursion. Cobol and Fortran for example traditionally do not. Some languages (e.g. PL/I) support it, but only if you declare that a specific function may be invoked recursively. ("PROC OPTIONS(RECURSIVE)"). Python supports recursion without any need to declare your intent to use the capability, but Python's support of recursion does not include "tail recursion optimization". Tail recursion optimization is where a language processor recognizes the special case that a procedure is being called recursively, but that when the procedure returns to the point of the call, there's nothing more to do than to return to an earlier call to this procedure. A clever compiler can transform the code for such a program to do a plain loop instead of a recursive call. Alas, in Python, there's much that cannot be known for certain about the code until run time. Guido Von Rossum, the creator of Python and it's "Benevolent Dictator for Life" (BDFL) has blogged about why Python doesn't bother to try harder for this particular case. See: Tail Recursion Elimination.

A key fact to note is that if you've got code with a tail recursion in it, then it is reasonably straight forward for you to restructure that code to explicitly use a loop in place of the recursion. It apparently is in this fact that Guido draws enough comfort to not bother trying to optimize the handling of this kind of code.

Some folks look at the limitation of Python's support of recursion and wrongly conclude that recursion is a feature of the Python programming language that you should avoid. Ned Batchelder did a great job of de-bunking that assertion in his essay: Recursive Dogma.

There are lots of interesting discussions of recursion in the Udacity CS101 forum. Much of the debate is over whether or not recursion is something easy or hard to get your brain wrapped around. Some folks find recursion is an elegant way to express a function while others opine that iteration is a more natural way to conceive of a function's processing. My opinion in this debate is that even if recursion provides a straightforward clean design for a function, do think through how to transform that design into an iteration. Compare the readability, performance and limitations of the 2 alternative designs and pick the alternative that makes the most sense for your needs.