JavaScript: What the **** is Recursion?

#javascript #recursion #webdev #algorithms

Introduction

JavaScript functions are one of the fundamental building blocks to JavaScript programming. A function is simply defined as a block of code designed to perform a certain task. Generally speaking, a function normally takes in an input and returns an output. One type of function is a recursive function.

So what exactly is recursion?

In computer science, recursion is the process of a function that calls itself from within its own code. This concept is used throughout many programming languages including JavaScript. We can think of this as an alternative to iterating (for/while loops). General rule of thumb is that we use recursion to make our code more readable however, it can sometimes be less efficient than iterating. An example as to where recursion can be helpful is that it can be used for searching and sorting algorithms such as traversing through a binary search tree

The 4 steps of recursion:

A recursive function is made up of 4 steps.

Identify the base case, this will avoid “Stack Overflow” (explained below)
Identify the recursive cases
Return where appropriate
Write procedures for each case that bring you closer to your base case

function recursiveFunc(n) {
  if(n === 3) { // Base Case
    return n // Return when base case has been met
  }
  console.log(n)
  return recursiveFunc(n + 1) // Recrusive Case
}

Each time a recursive function is called, the function itself is added to the call stack. These functions will then be popped off the call stack when the base case has been met. If we do not implement a base case, our recursive functions will infinitely be called and these functions will continue to be added to our call stack until our memory limit has been reached and our application crashes. This is known as “Stack overflow”.

Why use it?

Sometimes we encounter a problem that is too complex to solve directly. We use recursion by breaking up the problem in to smaller, repetitive pieces. We can solve these smaller pieces and then build back up a solution to the entire problem.

For example, when working with tree data structures, it can be useful to use recursion to traverse when you are unsure of how deep the tree is and how many loops you will need to traverse throughout it.

Recursion vs iteratively(looping)

As I explained above, recursion can be used as an alternative to looping. Recursion can always be implemented as a loop but in some situations, it is simpler to use recursion. A big benefit of using recursion is that it is more elegant than using a for loop making it easier to read and debug. It is important to note that iterating is faster and recursion can be a worse option to use if space complexity is important to you.

As shown in the example below, we are implementing a function for a Fibonacci sequence using both a for loop and a recursive method. From these examples, we can see why a recursion function is a better approach to take as it is less cluttered and easier to read.

 function fibonacciIterative(n) {
  let array = [0, 1]
  for (let i =2; i < n +1; i++) {
    array.push(array[i - 1] + array[i - 2])
  }
  return array[n]
}

function fibonacciRecursive(n) {
  if(n < 2) {
    return n
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)
}

Conclusion:

Recursion itself can be a bit of a pain to wrap your head around but take the time to research and get comfortable with it as it really has some amazing benefits to using it.

Pros:

Readability
DRY

Cons:

Space complexity
Risk of stack overflow
Confusing concept to new developers, may cause issues if using it in your code base

Links

linkedIn — https://linkedin.com/in/adam-o-reilly-js
portfolio - https://www.adamoreilly.com/

Top comments (10)

Paweł Świątkowski • Jul 6 '22 • Edited

Recursion can always be implemented as a loop

I'm not sure this is true, especially for tree-like structures. For example: find the first file named "treasure.js" in directory "projects" and all it's subdirectories.

Tracy Gilmore • Jul 7 '22 • Edited

I agree with Pawel, there are problems loops cannot solve and where recursion is a more efficient strategy. In your example Adam, you only make one recursive call from the function but there are also use case where a function might call itself more than once per cycle. The graphical flood fill algorithm is a good example.

Mike Talbot ⭐ • Jul 6 '22

Not sure about all cases, but you can definitely do your example without the need for a stack, but using a loop to create an array of folders to search etc. I just did a similar thing creating a tree that needed an final unrolled array rather than a recursive structure.

Paweł Świątkowski • Jul 6 '22

So like with a while and current_directory variable and directories mutable array?

Mike Talbot ⭐ • Jul 6 '22

Yeah, probably no need for the directories array to be mutable though, you'd just replace it on each iteration with all of the next level down directories.