Recursion, Recursion, Recursion

Maleeha Bhuiyan
6 min readNov 14, 2020

This is a sweet beginners guide to the world of recursions! When I initially started my journey into algorithms, recursion was a difficult concept to grasp. However with much (much much) practice, I was able to work out a strategy that helps me tackle recursive problems. If you have no clue where to start, then you have come to the right place! All you need to have in your tool belt is a basic understanding of JavaScript syntax for the purpose of the examples.

What is recursion?

Recursion in simple words is: a function that calls itself.

It sounds a little weird at first so why don’t we take a look at an example:

The function factorial is taking in a number as its argument and will spit out the factorial result of that number. A factorial is where we have a number (in this case it is going to be whatever number we pass into the function) and then multiply all the positive integers less than or equal to that number.

This is a recursive function because factorial is calling factorial, as seen in the part of the code that is underlined. Don’t worry, we will dive deeper behind the scenes of this function momentarily.

Why is recursion important?

Take a look at the function factorial without recursion. This version of the function is using iteration.

Both iteration and recursion accomplish the same thing and there is no performance benefit when using recursion. Sometimes using loops will actually be the preferable method. However which one looks cleaner to read? That might’ve been an objective question but many would agree that the recursive function is easier on the eyes.

A quote by Leigh Caldwell on Stack Overflow: “Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!”

Recursion is a very important concept to understand because it is common with many complex algorithms. It is seen in a lot of places like JSON.parse, JSON.stringify, document.getElementById and DOM traversal algorithms.

How do recursive functions work?

Recursions are made up of two parts: the base case and the recursive case.

The base case: is a condition that states where the recursion must end.
The recursion case: is where we call the function again but with a different input.

Let’s look back at our recursion factorial and map out the location of these parts.

Each time factorial runs, it will call itself with a new input that is one less than num. This recursion will stop once num is equal to 1. Let’s console.log num to visualize this pattern.

Now that we know the parts that make up a recursion function, there is one last concept to understand: the call stack.

What is the call stack?

Functions do not get invoked randomly, there is a certain order. The stack is a data structure that manages the order of function calls. We will not go too much into it in this article but all you need to know is that whenever a function is invoked, it gets placed (pushed) on top of the call stack. When JavaScript sees the return keyword or when the function ends, the compiler will remove (pop) that function off of the call stack. The call stack is important to know in order to build effective recursive code that does not break because it is what is going on “behind the scenes” for recursive calls. The book Grokking Algorithms: An illustrated guide for programmers and other curious people by Aditya Bhargava has a great diagram show casing the call stack for the factorial recursion call. In this diagram fact() is equivalent to the factorial() function we have been working with and x is equivalent to num.

Let’s do a recursion problem together!

Okay now that we know what recursion functions are, let’s actually do a problem together!

Write a function called productOfArray which takes in an array of numbers and returns the product of them all

Examples:
productArray([1,2,3]) // 6
productArray([1,2,3,10]) // 6

There are many ways in which you can solve this problem, this is the way that I would tackle it.

  1. Put the problem in your own words:
    We have an array with numbers. Our function has to multiply all the numbers in the array and return the final product.
  2. Identify the base case:
    When should this recursion stop? Since we are multiplying all the numbers in an array, it should end once we have multiplied the last number.
  3. What should we return once we reach the base case?
    It makes sense to return 1 because once we have reached the base case, all the numbers will have been multiplied. If we return 1 we are essentially multiplying by one, thus keeping the final product.
  4. Identify how to get the new inputs:
    To create this function I think it will make sense to call a new array that does not include the first element of the previous array called. So if we have the array [1,2,3]; the next function call should use the array [2,3] and the last function call should use [3]. This way we can use the use arr[0] to multiply all the elements of the initial array.

This is the complete productOfArray function. It multiplies the first element of the new array. The new new array is always one less than the previous array because we are using .slice to take out the first element. Once there are no more elements in the array, the product will be multiplied with one and return the final product!

If you are a newbie to recursions, console.logging your new inputs and your base case can further your understanding on how a specific function operates behind the scenes.

So thats it! All the basic information you need to know when starting your journey into recursions. We have identified what recursions are, why they are important, parts of a recursion and the call stack. We also walked through a strategy that you may use when encountering a recursion problem. Even with all this knowledge, the real secret to mastering recursions is with practice (lots and lost of practice). Good luck!

--

--