JavaScript: What the **** is Recursion?
Tags: javascript, recursion, webdev, algorithms
Published: 2022-07-06 09:32:35

## 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

```js
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.

```js
 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/