Sitemap
Kevin Lai

Kevin Lai

Javascript: Recursion Basics

4 min readApr 13, 2020

--

What is recursion?

Recursion is when a function calls itself.

Recursion could look like this:

Press enter or click to view image in full size

BUT…we run into an issue:

Press enter or click to view image in full size

The function is calling itself over and over again but we haven’t written a way to stop the function from calling itself. In a recursive function there are three main components that when put together stop the function from looping infinitely:

  1. The Terminal condition

The terminal condition is the fail safe. This condition is usually there to catch any bad inputs. Our example now does not take in any arguments but in a later example we will see an example of a terminal condition used to stop bad inputs.

2. The Base Case

The base case is a conditional usually written within an if statement that tells the function has completed it’s goal. It is similar to the terminal case in that both conditions stop the function from running any further, however the purpose of the terminal case is to catch any bad inputs whereas a base case tells us when the function has completed it’s intended purpose. In our example above, we want our recursion to stop when we’ve looped 5 times. We can do this by creating a count variable and incrementing this variable by 1 each loop, we can also write an if statement within our function to check the count variable.

Press enter or click to view image in full size
Press enter or click to view image in full size

3. The Recursion

This is the recursion itself, in our example it is the return statement that returns the function invocation.

Now with this in mind lets look at a common recursion problem, factorial. We want to write a function that takes in an argument, an integer. Our function will find the factorial of that argument. The factorial of a number can be found by multiplying the number by itself -1 until it reaches the number 1.

Example 1: The factorial of 4 (4!) is 4*3*2*1 = 24

Get Kevin Lai’s stories in your inbox

Join Medium for free to get updates from this writer.

Example 2: The factorial of 10 (10!) is 10*9*8*7*6*5*4*3*2*1 = 3628800

Press enter or click to view image in full size
Press enter or click to view image in full size

We see here that our code works lets break down whats happening.

  1. We invoke our function on line 12 with the argument of 4.
  2. 4 is greater than 0 and 4 !== 0 so it fails both our terminal and base case.
  3. Our return looks like this: return 4 * factorial(4-1)
  4. There is no value assigned yet to factorial(3) so we go through the function again
  5. 3 is greater than 0 and 3 !== 0 so it fails both conditions again.
  6. Our return looks like this: return 3 * factorial(3-1 ) so we go through the function again…
  7. 2 is greater than 0 and 2 !== 0 so it fails both conditions
  8. Our return looks like this: return 2 * factorial(2-1), we can’t evaluate this so we have to invoke function(1)
  9. 1 is greater than 0 and 1 !== 0 so it fails our cases again
  10. Our return looks like this: return 1 * factorial(1–1), we invoke factorial(0)
  11. Now our base condition is finally hit! 0 === 0 so we immediately return 1
  12. Since our function has return a value that does not need to be evaluated, the recursion ‘unwinds’, since recursion is just a group of nested function calls the inner most functions are returned first:

factorial(0) returns 1

factorial(1) returns 1 * factorial(0), or 1 * 1

factorial(2) return 2 * factorial(1), or 2 * 1 * 1

factorial(3) returns 3 * factorial(2), or 3*2*1*1

factorial(4) returns 4 * factorial(3), or 4*3*2*1*1 // 24

--

--