Javascript: Recursion Basics
What is recursion?
Recursion is when a function calls itself.
Recursion could look like this:
BUT…we run into an issue:
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:
- 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.
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
We see here that our code works lets break down whats happening.
- We invoke our function on line 12 with the argument of 4.
- 4 is greater than 0 and 4 !== 0 so it fails both our terminal and base case.
- Our return looks like this: return 4 * factorial(4-1)
- There is no value assigned yet to factorial(3) so we go through the function again
- 3 is greater than 0 and 3 !== 0 so it fails both conditions again.
- Our return looks like this: return 3 * factorial(3-1 ) so we go through the function again…
- 2 is greater than 0 and 2 !== 0 so it fails both conditions
- Our return looks like this: return 2 * factorial(2-1), we can’t evaluate this so we have to invoke function(1)
- 1 is greater than 0 and 1 !== 0 so it fails our cases again
- Our return looks like this: return 1 * factorial(1–1), we invoke factorial(0)
- Now our base condition is finally hit! 0 === 0 so we immediately return 1
- 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










