20
Recursion
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.
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)) // FalseThe 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.
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]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)) // 30const 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)) // falseconst 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
}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]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]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)) // 15Recursion 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.
20