What’s So Scary About Recursion?

The B in Benoit B. Mandelbrot stands for Benoit B. Mandelbrot

The Fibonacci sequence is one of the better known sequences of numbers, and one of my favourites. If you’ve never seen it — or, more likely, if you only ever saw it in some long-forgotten maths lesson and need a refresher — here are its first 10 terms:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

The Fibonacci sequence is defined by the following, recursive, function:

f(n) = f(n-1)+f(n-2)

Starting from:

f(0) = 0 & f(1) = 1

That is, after the first two terms, each successive term is the sum of the two terms before it.

If it’s clearly a recursive function, why would you use iteration to find the nth term of the Fibonacci sequence? Why reach for your trusty for loop?

Is it because recursion is hard? Let’s have a look at an iterative solution using a simple for loop in Javascript:

const fibonacci = n => {
  if(n<=1) return n       //f(0)=0, f(1)=1
  let [a,b,c] = [0,1,1]   
  for(let i = 1;i<n;i++){
    c = a + b
    a = b
    b = c
  }
  return c
}

So far so good. If we run this to find the 50th term of the Fibonacci sequence:

$ node ./fibonacci-iterative.js
12586269025
Calculated in 2ms

2 milliseconds! Pretty, pretty, pretty good. Now let’s look at a recursive solution:

const fibonacci = n => {
  if(n<=1) return n                       // f(0)=0, f(1)=1
  return fibonacci(n-1) + fibonacci(n-2)  // f(n) = f(n-1) + f(n-2) 
}

So recursion. Many elegance! The key tenet of recursion is to gradually reduce the problem until we get to the simplest possible solution. When we start to write our recursive function, we start with our “base case”: in this case it’s the values to return for the first two terms. For greater values of n we simply return the sum of the previous two numbers in the sequence, which we calculate using the function itself. See how similar it is to the mathematical definition? If anything, the recursive solution is easier to reason about than having to shuffle variables around, and risking an off-by-one error in defining our for-loop! Let’s run this bad-boy to find the 50th term of the Fibonacci series and see it in action!