An Introduction to Recursion

To understand it, you must first understand recursion...

March 8th, 2015 : 3 minutes

In the English language, recursion is defined as "of, relating to, or constituting a procedure that can repeat itself indefinitely". Thus, facing two mirrors together is recursive because each mirror is reflecting a reflection of itself. In computer science, 'recursion' piggybacks this idea of "calling onto itself" but involves an end point. It is a method or technique in which a function calls itself repeatedly, until a specified condition is met.

All recursive algorithms, they have three parts:

(1) a base case; a final destination; a place to stop

(2) a step to work towards reaching the base case (or final destination)

(3) a recursive call

Let's learn more about recursion on the Internet.

The goal or base case is to fully understand recursion. The step working toward this is clicking on and reading a page explaining recursion. The recursive call is to search the web for recursion. You can imagine doing this 5, 10, 15 times repeatedly until you've met the specified condition. (In this case, it is to understand recursion well enough to explain it to someone else.)

Consider six factorial (6!)...

You can see that we are recursively calling (n-1)! on each line as we count down from six. We could re-write this in Ruby as follows:

Here, we have create a method that calls itself until 'num > 0' is no longer true. In the recursive algorithm for factorials, you can see that we rely on the computer's "memory" in order for the method to carry out its business. The computer must hold on to the information from the previous state (in what is called the "activation stack") in order to apply it to the next call.

Even though recursion is one of the central ideas in computer science, it is not always the prefered option. In fact, many programming languages (including Ruby) are not built to support recursion and therefore lean towards iteration and looping. In a much more complicated problem or method, the stack requires more space on your computer and can be prone to stack overflow (aka, a program crash). In these cases, iterating through loops is preferable.

Using recursion can produce more elegant solutions to a given problem, but it is important to understand when it is appropriate. In the field of computer science, a deep understanding of recursion is thought to separate experts from novices, so it is a good time to start learning.

recursion: "a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first"

recursion: "defining a problem in terms of itself, or creating a solution to a problem with simpler versions of itself"