Recursion In Javascript – Simplified For Beginners

Welcome to a quick tutorial and examples of recursion in Javascript. So you may have heard of “recursion” and wondering what it does… Or you are absolutely confused about how it works. Well, in very simple terms:

  • Recursion happens when a function calls itself.
  • For example, function factorial (x) { return x<=1 ? 1 : x * factorial (x-1); }

Yes, recursion is deceptively confusing. But at the same time, it is also very simple. Let us walk through a few more examples to help you better understand, read on!

ⓘ I have included a zip file with all the example source code at the start of this tutorial, so you don’t have to copy-paste everything… Or if you just want to dive straight in.

 

 

TABLE OF CONTENTS

Download & Notes Basics Examples
Useful Bits & Links The End

 

DOWNLOAD & NOTES

Firstly, here is the download link to the example code as promised.

 

EXAMPLE CODE DOWNLOAD

Click here to download the source code, I have released it under the MIT license, so feel free to build on top of it or use it in your own project.

 

QUICK NOTES

If you spot a bug, please feel free to comment below. I try to answer questions too, but it is one person versus the entire world… If you need answers urgently, please check out my list of websites to get help with programming.

 

 

RECURSION BASICS

All right, let us get started by a quick run-through of the boring basics.

 

WHAT IS RECURSION?

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

GeeksForGeeks

Some technical folks like to make things sound difficult, some beginner code ninjas overthink themselves into confusion. No need to be confused – It is what it is. Recursion is just a function that calls itself.

 

RECURSION – A LOOP USING FUNCTIONS

function countdown (num) {
  console.log(num);
  num--;
  if (num > 0) { countdown(num); }
}
countdown(10);

This may not the best example, but that covers the basic idea of recursion:

  • We pass num into function countdown.
  • The function decrements num, and calls itself until num hits 0.

If you are thinking along the lines of for or while loop – You are on the right track. A recursive function is just like a loop that accepts parameters.

 

PROPER RECURSION

Remember that for and while loops have a “termination clause”? They will turn into infinite loops if the termination clause is not met. The same will happen in recursion, and it is recommended to “implement” the following “proper steps” for recursive functions:

  1. Safety Check – Immediately stop and throw an error when things go wrong.
  2. Recursion – What to do on every “cycle”.
  3. Termination – When to stop the recursion.

 

 

RECURSION EXAMPLES

So far so good? Recursion is actually just like learning how to ride a bicycle. The more you do it, the more you know how. Here are a few examples to get you started.

 

1) SIMPLE COUNTDOWN

1-countdown.js
function countdown (count) {
  // (A) SAFETY CHECK
  if (count < 0) { throw "Count below 0!"; }

  // (B) TERMINATION
  if (count == 0) { console.log("END"); }

  // (C) RECURSION
  else {
    console.log(count);
    count--;
    countdown(count);
  }
}

// (D) GO!
// 10, 9, 8, 7, ... END
countdown(10);

// Uncaught exception
countdown(-5);

Following up with the previous countdown example, here is one with the “proper controls” in place.

  1. Safety – The count should not be lesser than 0. Additional checks can be done to see if count is a proper integer.
  2. Terminate – Stop when the count reaches 0.
  3. Recursion – Decrement the count on every cycle.

 

2) POWER OF

2-power.js
function power (base, exp) {
  // (A) SAFETY CHECKS
  if (base < 0) { throw "Negative base value"; }
  if (exp < 0) { throw "Negative exponential value"; }

  // (B) TERMINATION
  if (base == 0) { return 0; }
  if (exp == 0) { return 1; }

  // (C) RECURSION
  else {
    exp--;
    return base * power(base, exp);
  }
}

// (D) GO!
var result = power(2, 5);
console.log(result); // 32

// ERROR
result = power(2, -5);

For you guys who have somehow… forgot basic Math, power simply works by multiplying a given base number a specific number of times. For example, 23 equals to 2 X 2 X 2.

  1. Safety – Both the base number and exponential cannot be less than 0.
  2. Terminate – Stop when the exponential hits 0.
  3. Recursion – Keep on multiplying the base number until the exponential hits 0.

 

 

3) FACTORIAL

3-factorial.js
function factorial (number) {
  // (A) SAFETY CHECK
  if (number <= 0) { throw "Invalid number!"; }

  // (B) TERMINATION
  if (number == 1) { return 1; }

  // (C) RECURSION
  else { return number * factorial(number-1); }
}

// (D) GO!
// FACTORIAL 4 = 4 X 3 X 2 X 1 = 24
var result = factorial(4);
console.log(result);

// ERROR
result = factorial(-5);

For the guys who are not Math wizards, factorial is simply “multiply in decrement order”. For example, factorial 3 means 3 X 2 X 1.

  1. Safety – The given number cannot be 0 or less.
  2. Terminate – Stop multiplying when the number hits 1.
  3. Recursion – Keep on multiplying the number until it hits 1.

 

4) REVERSE A STRING

4-string.js
function rString (text) {
  // (A) SAFETY CHECK
  if (text.length <= 0) { throw "Invalid string!"; }

  // (B) TERMINATION
  if (text.length == 1) { return text; }

  // (C) RECURSION
  else { return text.slice(-1) + rString(text.slice(0, -1)); }
}

// (D) GO!
var myString = rString("world");
console.log(myString); // dlrow

// ERROR
myString = rString("");

This one returns a string in reverse order… It probably does not have a real-world use, but a good student assignment nonetheless.

  1. Safety – Stop when the given string is empty.
  2. Terminate – Stop when there is only 1 character left.
  3. Recursion – Pick out the last character of the string, continue concatenating the rest.

 

 

5) TRAVERSE AN OBJECT

5-traversing.js
function totalSales (data, total) {
  // (A) SAFETY CHECK
  if (typeof data != "object") { throw "Invalid data"; }
  if (isNaN(data[0].amount)) { throw "Invalid amount"; }

  // (B) TERMINATION
  if (data.length == 1) { return data[0].amount; }

  // (C) RECURSION
  else {
    if (total == undefined) { total = 0; }
    return data[0].amount + totalSales(data.splice(1), total);
  }
}

// (D) GO!
var sales = [
  {
    name : "John Doe",
    amount : 123
  },
  {
    name : "Jane Doe",
    amount : 45
  },
  {
    name : "Jack Doe",
    amount : 67
  },
  {
    name : "Joy Doe",
    amount : 89
  }
];
var total = totalSales(sales); // 324
console.log(total);

For this final example, we are using recursion to loop through an array.

  1. Safety – The given data must be an object.
  2. Terminate – Stop when there is only 1 element left.
  3. Recursion – Read and add to the total amount on every cycle.

 

 

USEFUL BITS & LINKS

That’s all for the tutorial, and here is a small section on some extras and links that may be useful to you.

 

RECURSION IS STILL CONFUSING!

Then take it in a step-by-step manner:

  1. Start with the input and output. What parameters do you need and what is the end result? For example, factorial only requires a number input. The end result will be a “decremental multiplication” of the given number.
  2. Next, implement the recursion. Does require a little bit of “brainpower”, what to do on every cycle.
  3. Finally, the safety checks and the termination clause. The recursion has to stop somewhere.

If that is still difficult – Just think of it as working on a normal loop.

 

INFOGRAPHIC CHEATSHEET

Javascript Recursion (click to enlarge)

 

LINKS & REFERENCES

 

THE END

Thank you for reading, and we have come to the end of this guide. I hope that it has helped you with your project, and if you want to share anything with this guide, please feel free to comment below. Good luck and happy coding!

Leave a Comment

Your email address will not be published. Required fields are marked *