Recursion

Recursion, at it's simplest (bahahahaha) is a method that calles itself. My understanding is that recursion will break a task down into smaller and smaller tasks, complete the smaller tasks and pass their outcomes back up to the next bigger tasks in line, and keep this up until a base case (or point at which the method should no longer call itself) is reached.

To put a pop culture reference on it, recursion is like the movie Inception: a dream within a dream within a dream. You could also think about it as those Russian stacking dolls.

It seems as though anything you can solve recursively you can also solve by using loops and iterators, but it seems as though there may be some cases where recursion is more efficient and vice-versa.

Perhaps one simple way to see recursion in action when writing a method for a factorial in Ruby:

Here, the idea is that the factorial of a number is that number times all the numbers that came before it. (So, 5! = 5*4*3*2*1). Because the factorial 0 is 1, we can use recursion to break this problem down like so:

So here, recursion has split the task into smaller and smaller tasks until there is no smaller task to complete. Then, it sends the output back up the line, plugging them in where they belong in the chain, until we reach the base case, which in this example is factorial(5).

The Bastard's Guide to Ruby has an awesome metaphor that involves weighing a huge pile of rocks. It's worth a read.