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