Follow me on Twitter, happy to take your suggestions on topics or improvements /Chris

Ok, a big picture of sheep. Now he really lost it or? Actually, it's an analogy to Recursion, a lot of similar function invocations, almost same same but different ;) If you read on you will see Recursion explained and a few problems solved even.

I'm writing a fundamentals series on Computer Science topics. Why you ask, why not the latest JS Framework or something similar?

Well, there is more than one reason, knowing the fundamentals is a timeless skill, regardless of what framework, language or library you learn, fundamentals will always be there.

Ok, that sound like a textbook answer, are we supposed to buy that?

There is more to it of course. I've been in the IT industry for more than a decade and what you find after using a ton of libraries and languages is that after a while you strive after expanding your mind, solve problems you haven't seen before or even solving the same ol problems but in a new way.

Is it fair to say you've just been solving problems, sometimes in a hacky way?

Yea, I think we all can testify to that, sometimes our solutions have been good and sometimes less so.

And if I'm being completely honest I wasn't the most attentive student at University and the more I look into things like Big O notation, algorithms, recursion, compilers and so on, the better it feels when I finally get it and appreciate its elegance.

So for that reason, I will start this series by covering Recursion, one of the Big Whales, one of the big concepts to conquer. I hope to show the following:

• What is Recursion
• Why Recursion, what problems it can be used for and why it can be a really elegant approach
• Problem solving We will show a series of problems where Recursion really shines and how to solve them

What is Recursion

One of the standing jokes of recursion is:

If you want to know what Recursion is, see Recursion

In short, recursion is a method calling itself a number of times.

That sounds like a while-true loop like we are going to run out of memory

Yup, that's one of the pitfalls of recursion, if you do it wrong you will see error messages looking like this:

 Why

Why on earth would I want to be calling myself x number of times?

Well, it's about the nature of your problem. Some problems can be seen as a reoccuring pattern that you can apply the same solution to over and over.

Ok, you'll have to explain that better.

Sure we will show what we mean by working through a series of problems.

Ok fair enough but you still haven't explained the why?

In a word elegance, written correctly a recursive solution usually, consist of very few lines of code. This means our cognitive load for understanding and even modifying the code lowers drastically.

Ok I get that, everyone likes simple, what else?

Recursion is often used as a replacement for for-loops and while statements. It's in its very nature to loop or rather reapply it's logic. I think it's fair to say it has a divide and conquer approach. Not be confused with the actual divide and conquer. All I wanted to say here was that, we slowly conquer our problem by realizing that we are looking at a dataset full of patterns that look similar, self-similarity. This self-similarity makes it possible to apply the same algorithm over and over.

You REALLY have to explain that

Well, you start off working on a set of data that gradually decreases which means we work towards a point. Once we reach that point we consider the problem solved.

What type of problems can we solve?

Well, here is a non-exhaustive list, so you get a sense for it:

• summation, we can easily sum up all the items in a list
• power, calculate the power of something is the same as multiplying a number by itself x number of times
• factorial, factorial is about multiplying all numbers in a descending fashion
• trees, trees are used for a lot of things in Computer Science, like compilers, post-pre fix processing like a calculator, etc.
• conversion, for example, turning a string to a number
• sorting, recursion is often used to implement sorting algorithms like merge sort for example.

This is just a small subset of problems we can solve and yes you can solve most of the above with for loops and while constructs but that usually leads to messier code.

Solving some problems

You must be itching by now to see some code so let's first start off by showing what a typical recursion looks like:

function recursion(data) {
  if(condition) {
    return 'something'
  } else {
   recursion(data)
  }
}

As you can see above we start with an IF clause, this is also called a base case or terminating condition. For you not to end up in a while-true condition you need to make sure that this condition is met.

Our ELSE statement is where we call ourselves again, as you can see we call the method recursion() again. The idea here is to modify it slightly so we ultimately reach our base case.

Let's look at some real problems next.

Factorial

In a factorial, the idea is to multiply all the numbers going up to and including the number itself. For number 5 that would mean we would need to compute it like so:

5 * 4 * 3 * 2 * 1

As we can see above we are working with a series of numbers that slowly descends towards a base condition 1. Let's see some code:

function factorial(num) {
  if(num === 1) {
    return 1;
  } else {
    return num * factorial(num -1); 
  }
}

I have to admit that the first time I saw a solution like this my head just exploded, I couldn't take it in, I was like is this even valid code or this would have been so much simpler using a for-loop like so:

function factorial(num) {
  var sum = 1;
  for(var i = num; i > 0; i--) {
    sum *= i; 
  }
  return sum;
}

I understand my past self and some of you reading this. Recursion hurts when you first look at it unless your brain is wired in a certain way ;).

So why is the recursive solution better? For me, at least, it's about simplicity. If we look at a specific row:

return num * factorial(num -1); 

All we think about here is returning num and we leave the rest to its own computation when we call factorial() again and this time with an adjusted value of num. The hard bit to understand, for me, was that this was valid code. I could see that this would lead to a 5 * 4 * 3 * 2 * 1 scenario. I just didn't get that the compiler was OK with it. But it is, which leads us to our next problem.

Conversion, string to number

Now, this is an interesting one. What really happens when we convert something from "234" to 234. Well, it's an addition. It's 200 + 30 + 4. What does that look like?

A descending series?

Yes, exactly, but let's be even more detailed, it looks like the following:

2 * 10^2 + 3 * 10 ^ 1 + 4 * 10 ^ 0

Given what we learned from our factorial we can start sketching on it:

currentcharacter * Math.pow(10, pow) + convert(character)

Ok, we get roughly the how. The next question is what does our base condition look like? The answer is that we are working with one character only, like so:

if (chars.length === 1) {
  return parseInt(chars[0]);
}

The above tells us that we will process our number from left to write and as soon as we process the leftmost character, it's considered processed and we should keep working on a smaller dataset. It's crucial that we make the dataset smaller so we reach our base condition. So let's see the rest of the code:

function convert(num) {
  let chars = (num + '');

  if(chars.length === 1) {
    return parseInt(chars[0])
  } else {
    let pow = chars.length -1;
    return Math.pow(10, pow) * parseInt(chars[0]) + convert(num.substr(1));
  }
}

Zooming in our else condition:

else {
  let pow = chars.length -1;
  return Math.pow(10, pow) * parseInt(chars[0]) + convert(num.substr(1));
}

We can see that we apply our descending pattern of 2* 10^2 + 3* 10^1 + 4 or "234" turns into 234. The reason it's descending is that we do this:

convert(num.substr(1))

We pick off one character from the left so 234, becomes 34 and finally 4 and thereby we reach our base condition.

Summary

I could be showing you trees and a ton of other implementations but let's stop here. Have a look at this repo in which I've solved some more problems with recursion. The point I wanted to get across was what recursion is, why it for certain problems constitute a simpler and more elegant solution and I of course also wanted to explain the building blocks of recursion and how to think when solving such problems.

I hope it was educational. If you want me to write a follow-up article on this topic let me know in the comments.

You might not be convinced at the end of this that recursion is for you. I wasn't for the longest time. To be honest, I enjoy the pattern that comes with recursion. If part of your job is to write algorithms or if you got aspirations towards becoming the next Code Wars master or applying for a job at a famous tech firm, this is a thing you will need to know. If not, carry on, for-loops are part of the language too :)

Or as they say where I live:

Keep calm and carry on :)