Recursion in programming is important as it provides more elegant solutions which makes the algorithm easier to read than the iteration. But a lot of engineers are having difficulties to understand how the recursion works. In this article, I will dive into it with many examples by showing how it actually works in the call stack. At the end of this article, you will have a much better idea of recursion and how it actually works.

To begin with, let’s talk about the formal definition of recursion.

What is recursion?

Let’s grab the definition from MDN. It says,

The act of a function calling itself, recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (resumes recursion).

Let’s remember those three from the definition:

a function calling itself
base case
recursive case (I am calling it “different input” in this article)

You don’t have to worry about the definition yet. We will go through them all together throughout this article. Instead of trying to explain the formal definition in words, let’s take a look at examples and see how we can write the iterable solutions first and then find the base case and different input. After that, we will write the recursive solution.

Let’s start with a very simple problem, printing numbers counting down.

1. Countdown example

Let’s write a function which prints numbers counting down from the number received as an argument. The given numbers should be bigger than zero. Let’s take a look at the iterable solution first.

Iterable solution

function countDown(n) {
  for (let i = n; i > 0; i--) {
    console.log(i);
  }
}

countDown(5);

And the result should show:

Basically we are iterating the loop starting from the given number until the i reaches zero (excluding zero) and we are decrementing the i value. Now let’s write this in the recursive way. For the recursion, as mentioned above, we need to find the 2 important parts, the base case and different input. Let’s check what those are from the iterable solution.

Base case: when i reaches to zero but excluding zero (i > 0) so we can say, it will be when the given number n reaches zero (if (n === 0)) in the recursive solution.
Different input: decrementing i value (i--) so for the recursion, it will be n - 1.

With the two parts, let’s write the recursive function.

Recursive solution

function countDownRecursive(n) {
  if (n === 0) {
    return;
  }

  console.log(n);
  countDownRecursive(n - 1);
}

countDownRecursive(5);

Let’s take a look at how it works. First let’s remove the code and only look at the recursive function.

function countDownRecursive(n) {
  countDownRecursive(n - 1);
}

countDownRecursive(5);

What is happening here? It’s basically calling itself infinitely. So when we call the countDownRecursive function (line 5), it will send the n value as 5 for the initial value (line1). And on line 2, it calls itself but with n - 1 which is basically countDownRecursive(5 - 1) which will be countDownRecursive(4). And when it is called, it will hit the line 2 again but this time with countDownRecursive(3). It will go on and on. So in the call stack, it will look something like:

Call stack (from bottom to top)

...
countDownRecursive(-1) // logged later
countDownRecursive(0)
countDownRecursive(1)
countDownRecursive(2)
countDownRecursive(3)
countDownRecursive(4)
countDownRecursive(5) // logged first

And this is how it looks like in the call stack from the DevTool:

But because we have no base case set yet, meaning the recursion is going to infinitely call itself which is causing the stack overflow and the browser will give us the RangeError.

Now let’s add the base case.

function countDownRecursive(n) {
  if (n === 0) {
    return;
  }

  countDownRecursive(n - 1);
}

countDownRecursive(5);

So now the recursion will meet the base case (line 2) when the n reaches zero. So when it hits the base case, it evaluated that entire chain of function calls. With the last call stack returns (line 3), the function will start to pop off the stack. The call stack will look like below, right before hitting the base case (the order is from bottom to top):

countDownRecursive(0) // last in the call stack
countDownRecursive(1)
countDownRecursive(2)
countDownRecursive(3)
countDownRecursive(4)
countDownRecursive(5) // first in the call stack

countDownRecursive(0) will return (line 3) so pop off the stack first and the next call stack will look like:

countDownRecursive(1)
countDownRecursive(2)
countDownRecursive(3)
countDownRecursive(4)
countDownRecursive(5) // first in the call stack

And then the next will pop off until the last call stack, countDownRecursive(5). Now let’s add the console.log(n) and see when this will get logged.

function countDownRecursive(n) {
  if (n === 0) {
    return;
  }

  console.log(n);
  countDownRecursive(n - 1);
}

countDownRecursive(5);

Because we are logging the n value before the different input (line 7), first it will log 5 and then call countDownRecursive(4). And it will log 4 and then call countDownRecursive(3). Once it meets the base case, it will pop off the function calls from the call stack.

This example doesn’t seem like quite useful because popping off the function calls from the call stack doesn’t actually do anything to get the result.

In the next example, let’s see how it would look like if we return the recursive calls instead of just logging the value.

2. SumRange example

Let’s write a function which takes an integer, n, as an argument and sums all the numbers in the range between zero and the given number.

For example, sumRange(10) should return 55. Let’s see the iterable solution first.

Iterable solution

function sumRange(num) {
  let sum = 0;

  for (let i = num; i > 0; i--) {
    sum += i;
  }

  return sum;
}

sumRange(10);

We are iterating from 10 until 1 (line 4) and for each iteration, we are summing up the i value.

Now let’s convert it to the recursive function. First, let’s find out the base case and different input.

Base case: when the num reaches 1, we will return 1 and from there, we will start popping off stacks and get the final num to return. We will go through each step below so if you are not sure what it means yet, don’t sweat it.
Different input: the sum value gets changed in each loop (line 5) and we are going to input this different value to each recursive function.

Recursive solution

function sumRange(num) {
  if (num === 1) return 1;

  return num + sumRange(num - 1);
}

sumRange(10);

Let’s start from 10. The first function call will be sumRange(10) and it will be added to the call stack.

Call stack

sumRange(10) // first in the call stack

Because the current num is 10 which is not 1, we will skip the base case (line 2) and return it with return 10 + sumRange(10 - 1) (line 4). So in the call stack, the second recursive function will be added but this time it will be 9 as an argument.

sumRange(9) // second in the call stack
sumRange(10) // first in the call stack

Now most of engineers get confused at this point. When we revisit the countdown example above, when we just console.log without return the recursive function, we get the updated value in each recursive function just like how the iteration works. But when we return the recursive function (which most recursion works this way), the recursive function calls need to wait until the later recursive function calls popping off from the stack. So right now, nothing has returned yet until it hits the base case which returns 1 without the recursive function call.

For the current call stack, let’s also look how the return would look like.

sumRange(9)  ==> return 9 + sumRange(8)
sumRange(10) ==> return 10 + sumRange(9)

Let’s move fast-forward right before hitting the base case.

sumRange(2)  ==> return 2 + sumRange(1)
sumRange(3)  ==> return 3 + sumRange(2)
sumRange(4)  ==> return 4 + sumRange(3)
sumRange(5)  ==> return 5 + sumRange(4)
sumRange(6)  ==> return 6 + sumRange(5)
sumRange(7)  ==> return 7 + sumRange(6)
sumRange(8)  ==> return 8 + sumRange(7)
sumRange(9)  ==> return 9 + sumRange(8)
sumRange(10) ==> return 10 + sumRange(9)

And for the next recursive function call, sumRange(1), it satisfies the base case as the num value is 1, and returns 1. Now let’s see what happens.

sumRange(2)  ==> return 2 + 1
sumRange(3)  ==> return 3 + sumRange(2)
sumRange(4)  ==> return 4 + sumRange(3)
sumRange(5)  ==> return 5 + sumRange(4)
sumRange(6)  ==> return 6 + sumRange(5)
sumRange(7)  ==> return 7 + sumRange(6)
sumRange(8)  ==> return 8 + sumRange(7)
sumRange(9)  ==> return 9 + sumRange(8)
sumRange(10) ==> return 10 + sumRange(9)

When we look at the sumRange(2) , now it returns 3 and pops off the stack.

sumRange(3)  ==> return 3 + 3
sumRange(4)  ==> return 4 + sumRange(3)
sumRange(5)  ==> return 5 + sumRange(4)
sumRange(6)  ==> return 6 + sumRange(5)
sumRange(7)  ==> return 7 + sumRange(6)
sumRange(8)  ==> return 8 + sumRange(7)
sumRange(9)  ==> return 9 + sumRange(8)
sumRange(10) ==> return 10 + sumRange(9)

And sumRange(3) returns 6 and pops off the stack and you can now guess what will happen till the end of the call stack. Let’s take a look at the last function call.

sumRange(9)  ==> return 9 + 36
sumRange(10) ==> return 10 + sumRange(9)

sumRange(9) will return 45, it will look like:

sumRange(10) ==> return 10 + 45

And sumRange(10) will finally return 55 as the result.

I hope it helps you visualise how the recursive function calls work.

Now let’s take a look at another similar problem. The next problem quite often appears in the technical interview, so it is going to be a good opportunity to learn how to solve it with recursion.

3. Factorial! example

Factorial is one of the best ways to explain the recursion and it’s almost identical to sumRange we show above except one part. Before we dive into the recursion code, in case you are not sure what factorial is, let’s quickly check what it is.

I got the definition from Britannica, and it say, “factorial in mathematics is the product of all positive integers less than or equal to a given positive integer and denoted by that integer and an exclamation point.” The formula is:

n! = n * (n - 1) * ... * 1

Therefore, factorial severn, 7!, means 7 * 6 * 5 * 4 * 3 * 2 * 1 and the result is 5040. If you wanted to find more about factorial, check out this great video by Eddie Woo.

Let’s write the recursive function. As mentioned, it will be almost same as the sumRange function but we are going to multiply all numbers instead of adding.

Recursive solution

function factorial(num) {
  if (num === 1) return 1;

  return num * factorial(num - 1);
}

factorial(7);

And it will return 5040.

4. String reverse example

So far, we had a look at the recursion examples with numbers. Now let’s take a look at some string examples and first let’s see how we can reverse the string.

The problem to solve is to return a reversed (order of) string from a given string. For example,

reverseString('frontendly');

should return

yldnetnorf

Before writing the recursive function, let’s quickly see 3 different ways to solve this problem such as reverse method, reduce and for loop.

4.1. reverse method

function reverseString(str) {
  return str.split('').reverse().join('');
}

In this approach, we will put the string into an array using split method and with reverse array method, we will reverse the array, and join all of the elements in the array back to a string.

4.2 reduce method

function reverseString(str) {
  return str.split('').reduce((acc, cur) => cur + acc, '');
}

With the reduce method, like the reverse method above, we first put the string into an array with the split method and creating the reversed string through the reduce method by combining the current character, cur, with the accumulated reversed string, acc.

4.3 for … of loop

function reverseString(str) {
  let reversed = '';

  for (let char of str) {
    reversed = char + reversed;
  }

  return reversed;
}

Now let’s take a look how we can solve it in the iterable solution and then find the base case and the different input we can use for the recursive solution.

First we will declare the reversed variable and assign an empty string (line 2). And in the for loop (line 4), we will keep adding each character to the front of the reversed variable.

In this iteration, let’s find the base case and different input.

base case: when there is no more character to iterate (line 4)
different input: this time, it will be opposite to the iteration. So instead of adding each character to the reversed variable (line 5), we will substring the given string.

Let’s see how it works in the recursion.

4.4 Recursion

function reverseString(str) {
    if (str.length <= 1) {
        return str;
    }
    
    return str.charAt(str.length - 1) + reverseString(str.substring(0, str.length - 1));
}

Let’s take a look at the returned value first (line 6). Just like the factorial example above, we will return two parts:

str.charAt(str.length - 1): the last character from the given str value in each recursion using the charAt string method.
reverseString(str.substring(0, str.length - 1)): the string which will substring the last character as an argument of the recursion function.

Let’s take a look at how those are creating the reversed string in each recursion call with reverseString('ryan').

y + reverseString('r') // 3rd
a + reverseString('ry') // 2nd
n + reverseString('rya') // 1st

Now in the 4th recursion call, because the length of the str equals 1, it hits the base case and return the given str which is r and it will start to pop off the stack.

r // base case
y + reverseString('r') // 3rd
a + reverseString('ry') // 2nd
n + reverseString('rya') // 1st

and

y + r // 3rd
a + reverseString('ry') // 2nd
n + reverseString('rya') // 1st

and

a + y + r // 2nd
n + reverseString('rya') // 1st

and

n + a + y + r // 1st

and finally it will return nayr.

The recursion for the string works quite similar to the number examples. Let’s see one more string example which appears in the algorithm interview quite often.

5. Printing staircase example

Let’s take a look at the Staircase challenge from the HackerRank. We need to write a function to create the staircase depending on the given n value. For example, staircase(4) should return as the screenshot below.

There are 3 solutions solving this challenge such as repeat method, iteration and recursion. Let’s first see how we can use the repeat method to solve this problem.

5.1 Repeat method

function staircase(n) {
  for (let i = 0; i < n; i++) {
    const stair = ' '.repeat(n - i) + '#'.repeat(i + 1);
    console.log(stair);
  }
}

staircase(4)

We are iterating from 0 till n (excluding n) (line 2). And we are storing the stair (line 3) and console.log it (line 4). Let’s talk more about the line 3.

For the first iteration, this one will look something like:

' '.repeat(4 - 1)  + '#'.repeat(0 + 1)

The repeat method returns a new string with the number of specified string. So the above line will return 3 empty string and then 1 #.

The second iteration will look like:

' '.repeat(4 - 2)  + '#'.repeat(0 + 2)

meaning 2 empty string and 2 #.

   # // 1st iteration
  ## // 2nd iteration

And I think you know where we are getting at and the final result will be:

   # // 1st iteration
  ## // 2nd iteration
 ### // 3rd iteration
#### // 4th iteration

5.2 Iteration

Before we talk about the iterable solution, let’s draw a diagram and see if we can find a pattern to construct the staircase.

If we put the final results in a matrix diagram, it looks like this.

	Row 3	Row 2	Row 1	Row 0
Col 0				#
Col 1			#	#
Col 2		#	#	#
Col 3	#	#	#	#

Can you find any pattern we can make a use of in order to create the staircase from the matrix diagram above?

When you look at the row and col number, I added Row 0 in the last cell so that you can visualise it easier although the iteration will start from Row 0 to Row 3.

To solve this challenge, we will have a nested loop, one for iterating the row as an outer loop and the other for iterating the column as an inner loop.

Let’s see the complete code first and explain how it works.

function staircase(n) {
  for (let row = 0; row < n; row++) {
    let stair = '';

    for (let col = 0; col < n; col++) {
      if (col <= row) {
        stair += '#';
      } else {
        stair = ' ' + stair;
      }
    }

    console.log(stair)
  }
}

staircase(4);

1️⃣ 1st outer loop: Row 0

We will start from iterating the row until the given number (line 2) and declare the stair variable with the empty string (line 3).

1st inner loop: Col 0

For Col 0, as col value which is 0 is same as row value which is 0, we will add # to the stair value (line 7).

2nd - 4th inner loop: Col 1 - Col 3

As col value is not smaller or equal to row value, we will add the empty space in front of the stair value (line 9).

2️⃣ 2nd outer loop: Row 1

As we start new row, we will declare stair with the empty string again (line 3).

1st - 2nd inner loop: Col 0 - Col 1

The col values of 0 and 1 are smaller or equal to the row value of 1, we will add two # to the stair value (line 7).

3rd - 4th inner loop: Col 2 - Col 3

The col values are bigger than the row value, we will add the empty space strings in front of the stair value.

And I think you know where we are getting at and believe you will find the remaining flow with the iteration.

5.3 Recursion

Now let’s convert it to recursion. Let’s find out the base case, conditional case and the different input.

Base case

It is when the value of n becomes same as row and stops the recursion. This prevents infinite loops and ensures when the staircase is complete.

Conditional case

The conditional case was not mentioned in the definition we saw above, but sometimes we need a conditional case for a recursion and the staircase is a great example we can practice with.

For this challenge, we will provide a conditional case which is triggered when the length of the current stair string equals n. This means that the current row of the staircase is complete.

It prints the current stair string, representing a row of the staircase. Then it makes a recursive call to staircase, incrementing row by 1 (moving to the next row) and resetting stair to an empty string. This shifts the function to construct the next row of the staircase.

Different input

We will keep adding either an empty space or # to the stair. If the length of stair is less than or equal to the current row number, it adds a hash. Otherwise, it adds a space. This logic creates the right-aligned staircase pattern.

Let’s see the complete code and go through it.

function staircase(n, row = 0, stair = '') {
  // base case
  if (n === row) {
    return;
  }

  // conditional case
  if (n === stair.length) {
    console.log(stair);
    return staircase(n, row + 1);
  }

  // different input
  const newStair = stair.length <= row ? '#' : ' ';

  staircase(n, row, newStair + stair);
}

staircase(4);

Let’s walk through the code.

As we are only sending the n value, the starting point of the arguments will be:

n = 4
row = 0
stair = ''

and when we invoke the staircase function, the function will get stored in the call stack.

staircase(4, 0, '') // initial function call

Initial function call - staircase(4, 0, '')

For the base case, n (4) is not equal to row (0), we will move to the conditional case.

For the conditional case, as n (4) is not equal to the length of the stair (0), we will move and call the recursive function with different input.

For the different input, we will create the newStair. For the newStair, we will add # because the length of the stair (0) equals to row (0) (line 14). And then we will prepend newStair to the stair and make the 1st recursive call (line 16). As nothing has returned yet, the first call will stay in the call stack.

current call stack

staircase(4, 0, '#') // 1st recursive call
staircase(4, 0, '') // initial function call

1st recursive call - staircase(4, 0, '#')

No base case and conditional case met, so we will directly go to line 14 and newStair will be an empty space so the recursive call this time will be (4, 0, ‘ #’).

current call stack

staircase(4, 0, ' #') // 2nd recursive call
staircase(4, 0, '#') // 1st recursive call
staircase(4, 0, '') // initial function call

4th recursive call - staircase(4, 0, ' #')

Let’s fast forward to the 4th recursive call and the call stack looks like below. Actually we don’t really need to care what’s in the call stack because we are printing the stair at the end of each row (line 9) but anyway it’s a good practice to see what’s going on in the call stack.

current call stack

staircase(4, 0, '   #') // 4th recursive call
staircase(4, 0, '  #') // 3rd recursive call
staircase(4, 0, ' #') // 2nd recursive call
staircase(4, 0, '#') // 1st recursive call
staircase(4, 0, '') // initial function call

It doesn’t meet the base case but it will go in the conditional case as the length of the stair, 4, is equal to n (line 8). In the conditional case, it will log the stair and return the staircase function to go to the next row with:

n = 4
row = 1
stair = none but it will be an empty string by default

Important note: In the conditional case, the return statement plays a crucial role in controlling the flow of the recursive calls. Let's analyze what happens with and without the return.

With return

When the condition if (n === stair.length) (line 8) is true, the function prints the current stair (line 9) and then immediately returns from the current call with staircase(n, row + 1) (line 10). This return ensures that after printing a row, the function does not continue to execute the remaining code in the current call (i.e., it doesn't add more characters to the current stair string). Instead, it starts building the next row.

Without return

Let's see what happens if we didn't return it.

If we remove the return, after printing the current row, the function will continue to execute the remaining code in the current call (line 14 and 16). This means it will keep adding characters to the stair string even though it should start a new row. This would disrupt the desired staircase pattern, as the function would attempt to add more characters to a row that is already complete. This would likely result in an incorrect staircase pattern or other unintended behaviour.

Now let’s fast-forward to the end of the row 2, and the call stack will look like:

staircase(4, 1, '  ##') // 9th recursive call
staircase(4, 1, ' ##') // 8th recursive call
staircase(4, 1, '##') // 7th recursive call
staircase(4, 1, '#') // 6th recursive call
staircase(4, 1, '') // 5th recursive call
staircase(4, 0, '   #') // 4th recursive call
staircase(4, 0, '  #') // 3rd recursive call
staircase(4, 0, ' #') // 2nd recursive call
staircase(4, 0, '#') // 1st recursive call
staircase(4, 0, '') // initial function call

and I think you can guess where we are going.

At the end when it hits the base case, it will start popping off from the call stack until the initial function call in the call stack. But as already mentioned, for this problem, we don’t really need to know what is going on in the call stack because we are immediately printing the stairs at the end of each row (line 9).

Why we need recursion?

We've explored various problems and their solutions, including both recursive and iterative approaches. You might wonder why choose recursion when iterative solutions can also solve the problem? This is an excellent point, and indeed, iteration is often a perfectly viable option. However, there are specific scenarios where recursion offers a more effective solution than iteration.

Two scenarios where recursion typically outshines iteration are:

For Clarity and Readability: In certain cases, recursion can be more straightforward and more readable than iterative approaches. An example of this is calculating node depth, a topic I plan to cover soon.
For Unknown Iteration Counts: When the number of iterations required isn't predetermined or clear, recursion can be more adept at handling such situations. An example is the reconstruction of Binary Search Trees (BST), which I will also dive into in upcoming articles.

These topics, Node Depth and Reconstructing BST, are common in interview questions. I'm going to discuss them more thoroughly in future articles, so stay tuned for those in-depth explorations!

Recursion with memoization (a common technical interview)

Sometimes the algorithm with the recursion could have a worse time complexity than the iteration. In such situations, memoization can be employed to enhance the recursion's performance.

Memoization is a programming optimisation technique that involves caching the results of previous computations. This strategy prevents the need to repeat costly calculations multiple times.

One of the most commonly asked interview questions checking if you understand the concept of memoization is Fibonacci Sequence.

Given the complexity of this topic, ~~I plan to dedicate a separate article to the Fibonacci Sequence, so watch for that~~ I've published an article on finding the Nth Fibonacci number here, covering iterative, recursive, and memoization solutions.

Summary

We have learnt what the recursion is and how it works with several examples. I hope this article helps you understand recursions better.

If you're interested in enhancing your knowledge of algorithms and data structures, as well as diving into various frontend technologies like JavaScript, React, and NextJS, from beginner to advanced and expert levels, consider subscribing to the newsletter to stay informed and up-to-date.