Recursion

Table Of Contents

Introduction

Examples

Factorial
Search
Quick sort
Tree traversal

Recreating higher order functions

Every
Some
Map
Filter
Reduce

Summery

Introduction

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.

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

With recursion it looks like this.

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

Factorial

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

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

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.

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

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

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

Every

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

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

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

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

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