## DEV Community π©βπ»π¨βπ» is a community of 963,673 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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
}
``````

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:

• DRY

Cons:

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

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.

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.

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.

PaweΕ ΕwiΔtkowski

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

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.

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`

Nathan Stevenson

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

NotFound404

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

Andrew Bone • Edited on

This is the true meaning of recursion link

Nathan Stevenson

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

I wasn't wrong π

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));
``````

Cheers!

## Visualizing Promises and Async/Await π€―

βοΈ Check out this all-time classic DEV post