What **is** recursion? 🤷🏼‍♀️

I was challenged by @100days100 to learn and write about recursion.
This is not something that I've looked into or used before..

This article will answer the question 'what is recursion?' and will hopefully give you a solid way with which to explain it to others.

Recursion is a principle which occurs in many different languages and formats, but we are going to stick with explanations and examples using JavaScript so we don't go completely mad.

So here we gooooooooo 🥳

Recursion (ree-curr-shon) is a Computer Science principle that is found in almost every coding language. It is a type of process or method that is used to break a problem down to solve it in smaller, repetitive ways. It's a method that calls itself.

Like a loop?

Yeah, exactly like a for-loop, except a for-loop is a loop, not a method.

Remember that tech likes to be confusing...

So....a method that keeps referring to itself...?

Imagine someone that keeps referring to themselves in the third person.
Example: "Hi, Faye's name is Faye. Faye likes writing and learning about things that Faye doesn't understand yet - essentially Faye likes to teach people while learning."

Yeah, sounds really weird. Give yourself a minute to come up with some funny sentences and then you'll be able to focus again.

You got it out of your system?

Ok great, let's carry on...

Why would you ever need to make a method refer to itself?

Great question...
A popular 'task' in a coding quiz or even interview is:

Create a function that returns the factorial of a given integer.

Stop right there. What?

Ah yes, this mathematical concept that I also just learned about! So this seems to be the best way to explain recursion
'factorial' is all about multiplying numbers together
So 'factorial 6' - 6! would be 6 * 5 * 4 * 3 * 2 * 1.

You could work this out pretty easily, but what about factorial 97?

This is where a recursive function will be useful.

Your function needs to loop (yes, loop, don't @ me) around all of the numbers, but (and hold on here) do you see the issue?

Let's take factorial 6 again - and I want you to imagine that each of the steps is a block of lego. Also, I'm calling each answer (n). Stay with me for now, we will come back to that later.

1. 6 * 5 = n(30)

So here in our first block, we have the original number multiplied by itself-1

1. 2nd block - (n) * 4 = n(120)
   So this block is relying on the first block because it needs to know what the first blocks' (n) answer was, and then it comes up with its own (n)

2. 3rd block - (n) * 3 = n(360)
   This block is relying on the 2nd block for it's (n) answer, and is also, by extension, relying on the 1st block. This is why we are imagining them as lego - they all fit together and hold each other up)

3. 4th block - (n) * 2 = n(720)
   This fourth block is relying on every other block before it for all of their versions of n, and then it's created another version!

4. 5th block - (n) * 1 = n(720)
   Our 5th block doesn't really do much, it is just multiplying n by 1, nevertheless, we need it to finish our lego tower.

5. 6th block - n * 0 = n(0)
   Our last block feels like it's undoing all of that nice math that we were just doing, right? Yep, but that's math. Hold tight for the... 👀base case👀😱

Ok, that's factorial, what's that got to do with recursion?

The point of me explaining that was to show a recursive function, spread out like a scroll. Now imagine if you could squish all of those 6 lego blocks into 1.

Imagine all of the lego blocks for factorial 50, or even 700!
Imagine it was your task to write that out in code. Sure, achievable with for loops and if/else statements but...

Think of the clean code you could have if you didn't have for loops and if/else statements everywhere.

Elegant 💃🏼

The recursive function that you'd need for the 6! (factorial 6) puzzle would be:

function factorial(n) {
  if (n < 0) return;
  if (n === 0) return 1;
  return n * factorial(x - 1);
}

In the above function, if you wanted to find factorial 6, you'd console.log(factorial(6))

Let's break down exactly what the function would do next.

if (n < 0) return;
if (n === 0) return 1;

Well, 6 is greater than 0, and it isn't 0, so it would jump over these 2 ifs. We passed the termination condition and base case! Carry on!

return n * factorial(n - 1);

Woah....

Yep, this is the actual recursive function.

Bow down to it. This is what this whole article has been about.

What this little friend does is to say 'if you have passed the termination and base...' (we did) '...then multiply 6 by 6-1'

This function will run again and again, forever and ever, until it is stopped by the nets (the termination condition and base case.

Our 6th lego block (the one that undid all our nice math) will be caught in the base case (because it does === 0) and the previous results will be logged in reverse order (like an unravelling spiral)

References!

Recursion In JavaScript

What on Earth is Recursion? - Computerphile

As always, Oliver and Benedikt on Twitter