Let's Talk Recursion

One of those things that lots of new coders ask about is recursion. I mean I get it, most people learning to code will run into explanations about recursion, if only that it relates to functions and allows for some elegant solutions. Unfortunately, that's basically useless. Since I've had the good fortune to give a few lectures on the subject to beginning coders and explore the concept in some tutoriing sessions, hopefully this post helps you make some sense out of recursion.

If you want to watch a video (and see where I ripped most of my lesson from), check out the first lesson of Structure and Interpretation of Computer Programs (SICP) on MIT OpenCourseware.

First, let's make sure we all know the meaning of some words:

Recursion: A process that repeats itself
Iteration: A repeating process

These are EXTREMELY similar, but crucially different. An iterative process may also be recursive, but a recursive process is not necessarily iterative.

...Just like the all squares are rectangles but not all rectangles are squares.

The computer sciency and mathematical definitions are also similar: A recursive function references itself in its definition; iteration is repeating a given definition.

So what the hell does that mean, right? Basically, any list of instructions that has a 'Repeat steps 2-4 until...' can be thought of as recursive, where the base case is whatever appears after the 'until.' Repeating steps are more common, as anyone who's assembled furniture is familiar with ("Now take part E and insert into hole H [...and do the same thing you did on the other side...]").

Why have I spent so many words trying to highlight this minor difference? Because ANY problem you can solve iteratively (ie: with a FOR or WHILE loop) can also be solved recursively, and vice versa. The difference is in structure of your logic/code, and in how it looks while it's executing (actively running).

In fact, there are two main differences in how a recursive function will execute. The function can be either purely recursive (which will inflate the call stack) or iteratively recursive (which may not). That potential improvement is commonly known as tail-call optimization (more correctly, eliminination), and it's coming soon to Javascript.

Let's take a look at this in code, starting with a simple function that takes a a number N returns a value as follows:

(N-k)+(N-k_next) ... where k=0, incrementing by 1 each step until N-k=0

N+(N-1)+(N-2)+(N-3) ... until N-k=0

Example: N = 3

(3-0) + (3-1) + (3-2) + (3-3)
  3   +   2   +   1   +   0
              6

Iteration

We'll start with method you're probably most familiar with, and one of the first tools most programmers learn. You can use a FOR or WHILE loop to repeat (ie: iterate) over a given block of code.I hope most folks reading this would feel confident writing code to accomplish the above task!

var iteration = function(n) {
  var sum = 0;
  for (n; n>0; n--) {
    sum+=n;
  }
  return sum;
};
console.log(iteration(3)); //-> 6

The above process runs very vertically, like so:

sum = 0

sum = sum + i
sum =  0  + 3
sum =  3  + 2
sum =  5  + 1

return 6 <-- sum

Where we start with the 0 value, rather than adding it at the end.

Recursion

Next we'll run through a naive recursive solution. There's one GIANT thing every recursive function needs: A base case, or ending condition. If you don't have some condition where the function returns a value, rather than calling itself, the recursion will never end! Practically, you'll get a call stack exceeded error when that happens - sometimes it will crash or freeze either your computer or the executing application.

var recursive = function(n) {
  if (n===0) { return n; }
  return n+recursive(n-1);
};
console.log(recursive(3)); //-> 6

Below is a rough drawing of how this process happens. Pay particular attention to the way it forms a sideways pyramid - the operations are dependent upon the next call completing before you can get the final answer, so this recursion will grow in size for every call until it reaches the base case. You need to maintain the information from each call to recursive until you reach the 0 before you can add the numbers together and get an answer.

recursive(3)
   return 3 + recursive(2)                         
                 return 2 + recursive(1)            
                               return 1 + recursive(0)
                                             return 0
                               return 1 + 0
                 return 2 + 1 + 0
   return 3 + 2 + 1 + 0
6

That pyramid is what I'm referring to when I say "call stack" - you can picture in your mind a stack of functions being executed when your program runs. Tilt your head to the right and you can imagine placing each of those function calls on top of each other, then pushing the numbers back down until we get our final number.

Iterative Recursion

This method is a mix of the previous two, but with a key difference. The return value of this function is not a new operation dependent upon another function call to complete, but simply another call to itself. By maintaining the state of the step in the arguments to the function, a sufficiently smart compiler can replace the existing function call with the next one! As with the imperative iteration above using the FOR loop, this process can be stopped & restarted at any given step: We know the sum, and how much farther to go to get to 0. The pure recursive function cannot stop & restart without maintaining all of the information from the previous functions, any individual function from that list getting called later will give you a different answer (eg: recursive(2) will never give us back 6).

Note the extra, hidden argument that is only used when making the recursive call here.

var iterative = function(n,sum) {
  var sum = sum || 0; // default value for hidden parameter sum
  if (n===0) return sum;
  return iterative(n-1,sum+n);
};
console.log(iterative(3)) //-> 6

Again, examine the way this function executes visually:

iterative(3)
         return iterative(2,0+3)
         return iterative(1,3+2)
         return iterative(0,5+1)
6

Notice that this structure also extends horizontally, but only once, before moving in a vertical fashion like the first example of iteration. The importance of this single function is that s sufficiently smart compiler can replace the previous call with the next one and merely update the argument values. This is similar to a GOTO statement or how the machine code for a loop would look. In purely functional languages, this tail call method is the only way to iterate.

Fibonacci Sequence

Below are examples of a famous mathematical operation and favorite for demonstrating recursion, the Fibonacci function.

This sequence is typically defined as follows:

1 2	F(0) = 0, F(1) = 1 F(n) = F(n-1) + F(n-2)

Which creates a pattern of numbers like so:

1	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

The first thing you should notice (assuming you read this in order) is that the definition is recursive! You can see that the first step is to define the two base cases, then for every subsequent number the same function is applied repeatedly on decreasing values, until either 0 or 1 is reached.

At this point, you should try to implement this function yourself in all three of the ways discussed, before looking at the solutions below.

Note: You can run the solution code below and verify the answers by changing the variable n to whatever Fibonacci number you wish to generate. The functions are written in a certain order so you can see the runtime differences by examing the time it takes them to print - what happens on larger values of n?

Second note: Before you put in a number over 30, make sure you know how to kill a long-running process in Node or your browser!

Fibonacci Solutions

var n = 12;

var fib_iter = function(n) {
  if (n===0) return 0;
  var prev = 0;
  var current = 1;
  var temp;
  for (var i=1;i<n;i++) {
    temp = current;
    current = prev+current;
    prev = temp;
  }
  return current;
}
console.log('Iteration (for loop) fib sequence for '+n+':');
console.log(fib_iter(n));

var fib_iterRecur = function(n,cur,prev) {
  prev = prev || 0;
  cur = cur || 1;
  if (n<1) return 0;
  if (n===1) return cur;
  return fib_iterRecur(n-1,cur+prev,cur);
}
console.log('Recursive iteration fib sequence for '+n+':');
console.log(fib_iterRecur(n));

var fib_recur = function(n) {
  if (n<1) return 0;
  if (n===1) return 1;

  return fib_recur(n-1)+fib_recur(n-2);
}
console.log('Recursive fib sequence for '+n+':');
console.log(fib_recur(n));

And the last thing I'll mention is my terminology usage in this article. I use "iterative recursion" to reference the tail-recursive structure because I think it's descriptive and is an easy way to remember what's happening, but that's not super-common term. Purely functional languages tend to just call this process iteration and other languages will refer to it as "tail call optimization" or "tail call elimination" if supported, because the compiler or interpreter will reuse/replace the previous function call with the next one. In languages without this feature (like Javascript currently, as of Feb 2016), the runtime is often better using iterative recursion because there are often fewer function calls and the final solution doesn't have to be computed as you move back down the stack, but you will still encounter call stack exceeded errors at some point.