Recursion
Tags: javascript, functional
Published: 2021-07-27 15:47:56

## Table Of Contents
* [Introduction](#intro)
* [Examples](#example)
 * [Factorial](#fac)
 * [Search](#search)
 * [Quick sort](#qs)
 * [Tree traversal](#ts)
* [Recreating higher order functions](#hoc)
 * [Every](#every)
 * [Some](#some)
 * [Map](#map)
 * [Filter](#filter)
 * [Reduce](#reduce)
* [Summery](#sum)

## Introduction <a name="intro"></a>

Recursion is a interesting topic but it can be hard to understand.

We will start of by looking at some common recursive functions and compare them with a equivalent solution using a For loop. We will then take it a step further and look at sorting, Tree traversal and also recreate some higher order functions.

A recursive function is basically a function that calls itself until it doesn't. Sounds weird, right? Lets go over that again.

> A function that calls itself until it doesn't.

What does that even means?

Well it means that a recursive function must have a condition to stop calling itself. Otherwise, the function will call itself indefinitely and we will reach a stack overflow.

Everything you can do with a loop you can do with a recursive function and vice versa. JavaScript is not a functional language even tho you can use a functional approach, so we have access to all different kinds of loops. But some languages that are purely functional, like Haskell, Closure, Elixir relies solely on recursive functions for iterations.

Lets start with a simple example, a countDown function that takes a number as a argument and count down to 0 from it.

Using a For loop the function would look like this.

```javascript
const countDownLoop = (count) => {
  for (let i = count; i >= 0; i--) {
    console.log(i)
  }
}
```

With recursion it looks like this.

```javascript
const countDownRecurse = (count) => {
  if (count === 0) {
    return 0
  }

  console.log(count)
  return countDownRecurse (count - 1)
}
```
Like any recursive function we need to have a stop condition and that's the first if statement. `if (count === 0) return 0`. Whitout this condition the function would call itself until it crashes. If the count is not zero the function will continue, first by logging count to the console. The it returns itself with count - 1.


## Examples <a name="example"></a>

### Factorial <a name="fac"></a>

The Factorial is a classic example of a recursive function.
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5! = 5 x 4 x 3 x 2 x 1 = 120

```javascript
const factorial = (num) => {
  if (num === 1) {
    return 1
  }

  return num * factorial(num - 1)
}
```

When we call this function with the number 5. As long as the number is not equal to 1 it will keep calling itself and each call will be placed in the call stack.

5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)

Then it will unwind the return values
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120 as the final result

### Search <a name="search"></a>

Lets look at a search function that takes a list as an argument and a key. We start of by destructuring the head and tail from the list. 

```javascript
const list = [1, 2, 3, 4, 5]

const search = ([head, ...tail], key) => {
  /* if the head is undefined it means that
     the key is not in the array and we return false */
  if (typeof head === "undefined") {
    return false
  }

  /* If the head is equal to the key we turn true
     otherwise we call search again with the tail. */
  return head === key ? true : search(tail, key)
}

console.log(search(list, 11)) // False
```
The first time this function is run the first element in the list will be the head and the tail we be the rest.

```
head = 1
tail = [2, 3, 4, 5]
```

We check if head is equal to the key, which its not `1 === 11 // false` so we call search again, this time we pass in the tail as the list argument.

```
head = 2
tail = [3, 4 ,5]
```

This loop will continue until we find a match or the head is undefined, meaning no elements in the list matched the key.

### Quick sort<a name="qs"></a>

```javascript
const list = [2, 1, 5, 4, 3]

const quickSort = ([head, ...tail]) => {
  // Stopping condition
  if (typeof head === 'undefined') {
    return []
  }
  /* We split the tail in to two seperate list.
     One that is smaller then the pivot (head)
     and one that is larger or equal to head */
  const smaller = tail.filter((num) => num < head)
  const largerOrEqual = tail.filter((num) => num >= head)

  return [...quickSort(smaller), head, ...quickSort(largerOrEqual)]
}

console.log(quickSort(list)) // [1, 2, 3, 4, 5]
```

### Tree traversal <a name="ts"></a>

```javascript
const tree = {
  value: 5,
  left: null,
  right: {
    value: 8,
    left: {
      value: 6,
      left: null,
      right: null
    },
    right: {
      value: 11,
      left: null,
      right: null
    }
  }
}

const sumElements = (tree) => {
  if (tree === null) {
    return 0
  }
    
  return tree.value + sumElements(tree.left) + sumElements(tree.right)
}

console.log(sumElements(tree)) // 30
```
### Recreating higher order functions <a name="hoc"></a>

#### [Every](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/every)<a name="every"></a>

```javascript
const list = [2, 1, 1]
const checkFn = (x) => x === 1

const every = ([head, ...tail], fn) => {
  /* if the head is undefiend it means that all 
    calls to fn(head) returned true or the list is empty */
  if (typeof head === "undefined") {
    return true
  }
  /* As long as fn(head) returns true we call the function again. 
    If fn(head) returns false the
    function returns false instead of itself */
  return fn(head) ? every(tail, fn) : false
}

console.log(every(list, checkFn)) // false
```

#### [Some](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/some)<a name="some"></a>

```javascript
const some = ([head, ...tail], fn) => {
  /* if the head is undefiend it means that
    all calls to fn(head) returned false
    or it was called on a empty list. */
  if (typeof head === "undefined") {
    return false
  }

  /* if fn(head) returns false it means it didn't fulfilled
     the test function and we call some() again with a new head.
     If any entry (head) in the list fulfills the
     test function provided we return true */
  return !fn(head) ? some(tail, fn) : true
}
```

#### [Map](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map)<a name="map"></a>

```javascript
const list = [1, 2, 3, 4, 5]
const dubble = (x) => x * 2

const map = ([head, ...tail], fn) => {
  if (typeof head === 'undefined') {
    return []
  }

  return [fn(head), ...map(tail, fn)]
}

console.log(map(list, dubble)) // [2, 4, 6, 8, 10]
```

#### [Filter](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/filter)<a name="filter"></a>

```javascript
const list = [1, 2, 3, 4, 5]
const evenNumbers = (num) => num % 2 === 0

const filter = ([head, ...tail], predicate) => {
  if (typeof head === 'undefined') {
    return []
  }

  return predicate(head) ? [head, ...filter(tail, predicate)] : filter(tail, predicate)
}

console.log(filter(list, evenNumbers)) // [2, 4]

```

#### [Reduce](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce)<a name="reduce"></a>

```javascript
const list = [1, 2, 3, 4, 5]
const sum = (x, y) => x + y

const reduce = ([head, ...tail], fn, acc) => {
  if (typeof head === 'undefined') {
    return acc
  }

  return reduce(tail, fn, fn(acc, head))
}

console.log(reduce(list, sum, 0)) // 15

```

## Summary <a name="summary "></a>

* Recursion is when a function calls itself until some condition stops it.

* It can be used instead of a loop.

* If there's no condition to stop the function, it'll recurse forever and crash your program so make sure to add it.