DEV Community 👩‍💻👨‍💻

Cover image for JavaScript: What the **** is Recursion?
Adam O'Reilly
Adam O'Reilly

Posted on

JavaScript: What the **** is Recursion?

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.

  1. Identify the base case, this will avoid “Stack Overflow” (explained below)
  2. Identify the recursive cases
  3. Return where appropriate
  4. 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
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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 (11)

Collapse
 
katafrakt profile image
Paweł Świątkowski • Edited on

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.

Collapse
 
tracygjg profile image
TGJ Gilmore • Edited on

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.

Collapse
 
miketalbot profile image
Mike Talbot

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.

Collapse
 
katafrakt profile image
Paweł Świątkowski

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

Thread Thread
 
miketalbot profile image
Mike Talbot

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.

Thread Thread
 
peerreynders profile image
peerreynders

The quick and dirty trick I use:

  • Use an index i to track your working position in the array
  • Just push any "to be processed later" items onto the array
  • advance i on each iteration
  • done when i >= array.length

JSFiddle
Explanation

Thread Thread
 
nstvnsn profile image
Nathan Stevenson

Just for the sake of semantics, but arrays in JS are mutable by design!

Collapse
 
610470416 profile image
NotFound404

It is definitely wrong.
But recursion can always be implemented by a stack.
Because functions are implemented by stacks.

Collapse
 
link2twenty profile image
Andrew Bone • Edited on

This is the true meaning of recursion link

Collapse
 
nstvnsn profile image
Nathan Stevenson

I feel like that link brings us right back to this comment....

I wasn't wrong 😂

Collapse
 
lukeshiru profile image
Luke Shiru

You can simplify your fibonacci function even further if you just use an arrow function:

const fibonacci = n => (n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2));
Enter fullscreen mode Exit fullscreen mode

Cheers!

Visualizing Promises and Async/Await 🤯

async await

☝️ Check out this all-time classic DEV post