Recently I started following #100DaysOfCode on Twitter as I started freeCodeCamp to spend my time.

That hashtag is used by new coders learning a programming language. Perhaps even breaking into the industry and changing careers.

I noticed some concepts, which are hard to understand. Some people I helped to grok the matter.

Take recursion for example. In short, it is a function calling itself.

On freeCodeCamp they explained it with doing multiplication and tasked the student to apply it to a sum. I prefer using Fibonacci sequence as an example. Let's unpack it!

What is the Fibonacci number?

Fibonacci was an Italian Mathematician in the 13th century.

Fibonacci sequence is used to compute the Fibonacci number. It has three prescriptions:

  1. $F_0 = 0$
  2. $F_1 = 1$
  3. $F_n = F_{n-1} + F_{n-2}$ for any $n > 1$

Looks simple, right?

Translation into code

Okay, how would that look like with JavaScript? Small hint: my computer is male. So I use the pronoun 'he'. You can use another gender if you prefer :-)

First, we need a function fibonacci which computes the fibonacci number $F_n$ for any non-negative integer $n$.

function fibonacci (n) {
}

Next, implement $F_0$ and $F_1$:

function fibonacci (n) {
  if (n === 0) {
    return 0
  }

  if (n === 1) {
    return 1
  }
}

Lastly, what if $n$ is neither $0$ or $1$? An attempt could look like this:

function fibonacci (n) {
  if (n === 0) {
    return 0
  }

  if (n === 1) {
    return 1
  }

  const result = fibonacci(n-1) + fibonacci(n-2)
  return result
}

And done!

Wait, I don't get it!

No worries, recursion isn't an easy concept.

If I have to use one, I add some console.logs which help me understand what is going on. If you feel more confident, you can use the debugger of your browser's DevTools (but that's harder to blog about).

Adding those statements will turn the code into the following:

function fibonacci (n) {
  console.log('Computing Fibonacci number ', n)

  if (n === 0) {
    return 0
  }

  if (n === 1) {
    return 1
  }

  console.log('Need to apply recursion')
  const result = fibonacci(n-1) + fibonacci(n-2)
  console.log('Result of recursion ', result)
  return result
}

That is, I want to capture the arguments and the result value mainly.

Imagine now, I made a typo (for example, I forgot one if-condition, so the recursion never ends). How do I notice?

Well, in my case, the fan spins up and makes noise. After my initial panic reaction, I quickly prompt the tab before my whole machine freezes due to CPU exhaustion …

If that does not work, kill the browser. Still too late? Hard shutdown of the computer (and a kitten just died).

Explained with an example

Okay, next, try to understand what goes on for an example case. Take … 5. If you have index cards available, you can use those.

  1. n is 5 1.1 5 === 0 is false, so the block will be skipped 1.2 5 === 1 is false, so the block will be skipped 1.3. The computer reads this (this code won't run):
function fibonacci (5) {
   return fibonacci(5-1) + fibonacci(5-2)
}
  1. n is 4 2.1 4 === 0 is false, so the block will be skipped 2.2 4 === 1 is false, so the block will be skipped 2.3. The computer reads this (this code won't run):
function fibonacci (4) {
   return fibonacci(4-1) + fibonacci(4-2)
}
  1. n is 3 3.1 3 === 0 is false, so the block will be skipped 3.2 3 === 1 is false, so the block will be skipped 3.3. The computer reads this (this code won't run):
function fibonacci (3) {
   return fibonacci(3-1) + fibonacci(3-2)
}
  1. n is 2 4.1 2 === 0 is false, so the block will be skipped 4.2 2 === 1 is false, so the block will be skipped 4.3. The computer reads this (this code won't run):
function fibonacci (2) {
   return fibonacci(2-1) + fibonacci(2-2)
}
  1. n is 1 5.1 1 === 0 is false, so the block will be skipped 5.2 1 === 1 is true, so the computer reads this:
function fibonacci(1) {
  return 1
}
  1. pay attention we partly resolve the stack and jump to 4.3! There we see the second summand and continue, that is, the computer reads
function fibonacci (2) {
   return 1 + fibonacci(2-2)
}
  1. n is 0 7.1 0 === 0 is true, so the computer reads this:
function fibonacci(0) {
  return 0
}
  1. pay attention we are back to 4.3 now. This statement reads
function fibonacci (2) {
   return 1 + 0
}

8.1 Since fibonacci(2) could be computed we go back to 3.3 8.2 pay attention JavaScript is so dumb and will compute

function fibonacci (3) {
   return 1 + fibonacci(3-2)
}

That is, fibonacci(1) again now. We already know that it yields 1.

8.3. fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2

  1. Since fibonacci(3) is computed, we go back to 2.3 and recompute fibonacci(2).

9.1 fibonacci(4) = fibonacci(3) + fibonacci(2) = 2 + 1 = 3

  1. Since fibonacci(4) is computed, we go back to 1.3 and recompute fibonacci(3).

10.1 fibonacci(5) = fibonacci(4) + fibonacci(3) = 3 + 2 = 5

10.2 The function fibonacci(5) returns the result of the computation: 5

Summary of example

Uff, a lot is going on. You could have written each step on an index card. Every time you need to call the function itself, you write down all known variables on an index card and put them on a stack.

Once you have a partial result, you replace the function call with its return value. Actually this is how the computer actual works. But instead of index card, it is using memory called RAM.

You might have seen error messages like

Error Maximum call stack size exceeded

That's when you try to put too many index cards on the stack so that the whole tower falls down. In my case, the fan has hopefully warned me of this fate.

You might have also noticed, that the computer recalculates results he already did before. Yes, he's doing exactly what he was told to.

If you pick a larger number, you might have to wait (it took minutes before I aborted fibonacci(100) without a result …).

You can apply some tricks to save time. I like to use memoisation, but you could also use modern ES6 to implement it if you prefer.

Why not use a loop instead?

In most cases, you can (and should) prefer a loop over recursion. This way, you'll avoid memory problems.

However, there might be circumstances, where you can't estimate, how many steps it will take. Think of building a virtual DOM yourself. Or you parse a XML tree later on. These are cases, where you should think about using recursion.

Sure, you could use a while-loop, but the logic will quickly get out of hand. In this cases, a recursion might be worthwhile.

Also, if you look into other literature on the topic, you will often see arguments called head and tail. The head is the first element in a list, whereas tail means the rest. That is [ head ].concat(tail) is the complete list. For a recursion step, a new element is taken from tail and a step deeper is taken.

Conclusion

Don't use recursion if you don't have to. Try to understand the concept though and know, where you can look up for the details.