Recursion

For this technical blog post I will discuss and show examples of Recursion. Because we have been reviewing and thinking about Ruby and Javascript I will show examples using both.

Recursion is sort of difficult to understand, as it says in HTML Goodies: "To understand recursion you must first understand recursion".

There are many great examples of Recursion. You could think of it as dressing room mirrors where one mirror reflects the other until the reflection is repeated ad infinitum until it is too small to see.

In programming recursion is a function calling itself to solve a problem. It is frequently used to break a big problem down into smaller easier to solve sections.

I love this illustrative story which is a great metaphor for Recursion. It is called "The King and His Rocks" from The Bastards Book of Ruby and can be found here. The author also retells the same story using Ruby code. Check it out!

Here are examples of Recursion in Ruby and Javascript. Importantly, the function needs to terminate with a "base case" so it repeats until that condition is met and doesn't repeat forever.

With Ruby:

With Javascript:

In the end Recursion is usually NOT considered to be the best way to solve problems. Frequently it is possible to replace Recursive code with an iterative loop of some kind. As it says on Refactoring.com:

The old recruiting practice says, "Never hire a developer who computes the factorial using Recursion". Recursion is often used without considering alternatives before using it. Though it is true that recursive solution is often more elegant and easier to spot than the iterative solution, one should take care not to abuse it. Complex Recursion that is hard to understand should probably be considered a "bad smell" in the code and a good candidate to be replaced with Iteration (usually in combination with some other Refactorings). Moreover, iterative solutions are usually more efficient than recursive solutions as they don't incur the overhead of the multiple method calls.

Which leads us to the factorial. Here are examples of the same factorial with and without Recursion with both Ruby and Javascript.