Recursion

Introduction

When coding, one of the things we can often use is recursion. I’ve mentioned before fibonacci numbers, but there are quite a few algorithms that require recursion. One of them is QuickSort, but we’ll find a bunch of them in here.

What is Recursion

Recursion means defining a problem in terms of itself. Now, if you’re like me, you probably have no idea what that means.

So, let’s use an example to explore it:

const recursion = () => recursion();
recursion();

If you’d run to above program, you’ll get an error saying

Uncaught RangeError: Maximum call stack size exceeded

But that’s okay! Because it’s pretty much the same as calling an infinite loop, except individual calls are added onto Call Stack.

At some point, the computer decides that this is getting anywhere and it’s wasting resources, so it’s gonna kill the program. That’s not exactly what happens, as call stack has a limit and it’s reached, but this is enough explanation to give an idea.

To deal with this, we’d need to define a so-called base case.

Base case in recursion is the point when your code hits the bottom. Consider the following code:

const fib = (n) => {
    return fib(n - 1) + fib(n - 2)
}

In the above fibonacci calculator, there is no base case. There is no point when we say “Hey, stop right here, this is enough”. Without base case, our program would keep running until we received the error above. So, let’s fix that!

We know that for the 0th and 1st fibonacci number, we need to return the number 1. So, let’s do that!

const fib = (n) => {
    if (n === 0 || n === 1) return 1;
    return fib(n - 1) + fib(n - 2)
}

The first line of code inside the function is the base case. It is the point where you no longer call recursion. If you don’t define base case, you’ll kill your program.

So, with that in our mind, we can now use recursion. Some every day example could be flattening an array:

const flatten = (arr: number[], result = []) => {
  for (let i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) flatten(arr[i], result);
    else result.push(arr[i]);
  }
  return result;
};

const arr = [1, 2, 3, [4, 5, 6], 7, 8, 9, [10, [11, [12], 13, [14, 15]], 16]];
const result = []
flatten(arr, result)
console.log(result) // [1,2,3,4,5,...,16]

With the above code, we’re able to flatten an array using recursion! The base case is when Array.isArray == false. If the element is not an array, we’ll not call the flatten function and just perform the operations.

Using recursion

One thing to note is that we can use recursion everywhere. Is it a good idea? Probably not. But it certainly is an idea.

This section is mostly to understand that we can do that. Consider that you have a task to get a sum of letters in an array. Well, what you’d probably do is:

const arr = ['ab', 'c', 'def', 'ghij'] 
const getNumberOfChars = (arr) => arr.reduce((x,y) => x + y.length, 0)
console.log(getNumberOfChars(arr)) // 10

Now, how would we do that with recursion? Well, we need to work with the strings from the inside!

const getNumberOfChars = (stringOrArray) => {
    if (stringOrArray.length === 0) return 0;
    return stringOrArray[0].length + one(stringOrArray.slice(1))
}

Is it simpler than above? No. But we can use it. The benefit of this is that sometimes, it’s easier to write recursive code for algorithms, sometimes it is not, but you can use it for almost anything.

To showcase one where it’s actually way easier to use recursion, let’s consider the following setup:

Have a grid of rows and columns Write a function that accepts number of rows and number of columns Function calculates the number of paths from top-left to bottom-right The only permitted moves are left and right

Now, to write this code without recursion, let’s do just that:

Create matrix
Find path from top-left to bottom-right
Allow only moving left and right
Get number of paths followed

But when you think about it a little more, you’ll find that the “have a grid” means nothing. It’s actually just a clever wordplay. You’d probably end up with something like:

function getPaths(cols,rows,result = 0) {
    const arr = Array.from({ length: cols }, _ => Array.from({ length: rows}).fill(false));
    if (cols == 1 && rows == 1) {
        result++ // increment when bottom case is it
        return results;
    }
    if (cols > 1) result = five(cols - 1, rows, result);
    if (rows > 1) result = five(cols, rows - 1, result);
    return result;
}

The reason why the array doesn’t make sense there is:

it is unused in the code
we’re working with “abstract” grid. We don’t ever need to create it. We can cleverly work with indices only

Eventually, after inspecting it, you’ll find out 2 things:

Whenever I hit the end, I increment by 1
From the parent tree, I just want to account for this addition
I don’t need to pass the result down the tree because I’m always overwriting it

So, you’d get somewhere like:

function getPaths(cols,rows,) {
    let res = 0;
    if (cols == 1 && rows == 1) {
        return 1;
    }
    if (cols > 1) res += five(cols - 1, rows);
    if (rows > 1) res += five(cols, rows - 1);
    return res;
}

So that looks better. But now we’ll notice a strange thing! Because the moment you hit an edge (col = 1 OR row = 1), it’s the same as if both hit the edge (you got bottom right). Why? Well, because at that point, there’s only one way forward

If you’ve hit bottom, the only way is right -> there’s only 1 way to finish it
If you’ve hit right, the only way is down -> there’s only 1 way to finish it

So, finally, the initial condition will be cols == 1 || rows == 1. Which is the opposite of the next 2 checks. So, we’ll simplify it to:

function getPaths(cols, rows) {
  let res = 0;
  if (cols == 1 || rows == 1) {
    return 1;
  }
  res += five(cols - 1, rows);
  res += five(cols, rows - 1);
  return res;
}

And finally, now we can see what’s up. We can completely remove the res.

function getPaths(cols, rows) {
  if (rows === 1 || cols === 1) return 1;
  return five2(rows - 1, cols) + five2(rows, cols - 1);
}

function getPaths(cols,rows) {
    if (rows === 1 || cols === 1) return 1;
    return five2(rows - 1, cols) + five2(rows, cols - 1)
}

Now, go back up and see what changed. Instead of a long function, we’ve managed to simplify it to 2 lines of code by throwing away the unneeded stuff.

And this is where recursion especially shines. Either traversing or clever play with indices.

Memoization

So, we’ve seen a bunch of examples. Recursion can be really useful and potentially fast. But let’s rewind a bit.

I’ve mentioned fibonacci sequence before. Let’s revisit that code:

const fib = (n) => {
    if (n === 0 || n === 1) return 1;
    return fib(n - 1) + fib(n - 2)
}

A simple function that adds two numbers, right? Now, let’s look at the complexity. Consider you pass the number 5 to it.

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 1

Great. We got it. But let’s try to put it into a single line!

fib(5) = fib(4) + fib(3)
fib(5) = fib(3) + fib(2) + fib(3)
fib(5) = fib(2) + fib(1) + fib(1) + fib(0) + fib(2) + fib(1)
…

You get the idea. Upon inspection, we’ll find that we are calling a lot of unnecessary functions - or at least those we’ve already called.

To make this faster, we’ll use a technique called memoization. Basically, it’s caching already calculated results. Consider the following:

const cache = {};
const fib = (n) => {
    if (cache[n]) return cache[n];
    if (n === 0 || n === 1) {
        cache[n] = 1
        return 1;
    }
    cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]
}

Then to simplify it:

const cache = {};
const fib = (n) => {
    if (n === 0 || n === 1) return 1
    if (cache[n]) return cache[n]
    return cache[n] = fib(n - 1) + fib(n - 2)
}

Now, here we’ve actually used 2 things so far! A hash map and recursion! And we’ve sped it up a lot! Because now, once it’s already calculated any fibonacci number below, it’ll be cached and all subsequent calls will be fast!

Speeding up with recursion

So, we understand recursion now. We also understand memoization. Now, let’s try to speed some things up!

In this part, we’ll go through 2 parts:

So, let’s get started with it!

I’m going to start with Quickselect, because it’s easier. Now, why would we need it?

We’ve already talked about sorted and unsorted arrays. Imagine you need to retrieve the 7th lowest number in an array. Well, that’s easy!

Sorted array ascending - select element on 6th index
Unsorted array - sort and perform previous line
…Or do you?

Now, let me first establish some terminology, because this is not searching for 7th lowest element, but rather selecting 7th lowest element.

Searching - Search for a truthy condition
Selecting - Search Nth element based on condition

You could argue that selecting is a form of search. That would be true with indexes. To give another example:

I’m looking for 7th lowest element in an array of 2000 items (who happens to have the number 200)
I’m searching for a number 200 in an array

Now, in this case, they’d both be doing the same thing, but only because the item is same.

I can’t select number 200
I can’t search for 7th lowest element

If that wasn’t sufficient, I invite you to read through this SO post

And without further ado, let’s get to it.

As mentioned, we want to select nth element from an array. To do so, we’ll be using 2 things:

partition (or pivot index)
selection

The partition part will be used also in quicksort, so do try to keep up! In the simplest terms, it does the following:

pull element at pivot index from array
put smaller elements on the left
put larget elements on the right
replace pivot elements (in 1st step, it was removed, so we put it back into the array)

Now, once you’ve done that, you should have the element on its position within the array. So, if the first element you pull is the 14th lowest element, then it will be on the 14th position. If it’s 100th lowest element, it will be on 100th position.

And since you know that the lower elements are on the left and larger on the right, you know which way to go. So, you then perform the same code

If you pulled 14th element and you’re looking for 7th element, you look on the subarray of 0 to 13
If you pulled 14th element and you’re looking for 20th element, you look on the subarray 14 to length

So this is kinda similar with binary search in a way. So, if we reiterate on the 2 steps before:

partition (move smaller to left, larger to right)
selection (partition on smaller array using binary search ideas)

But how do we put smaller elements on the left and larger on the right?

Any element can be taken as pivot index, but the last element in array is usually used
This element is compared to the rest of the array, swapped if needed.

Now, consider that we have an array [7,10,4,2,3,20,15] and we’re looking for the 2nd smallest element

In there, if we pivot around the number 15, we’ll find that:

7 is smaller
10 is smaller
4 is smaller
3 is smaller
20 is larger -> SWAP THEM

Now, that’s good, we got 15 to its correct position. But we had to swap only 2 numbers. Now, let’s do it again:

We have array [7,10,4,2,3,15,20]
We know the 2nd smallest element is on the left side
We pivot around number 3 the same way as before, we’re gonna swap 7 and 3. But then we’d have to swap 3 and 2. And we’d get nowhere
Instead, we will:
- create a pivot index at 0
- keep in mind that 3 is our pivot number
- compare if element on index going from start is smaller than our pivot number
  - if it is smaller, move it to pivot index (0) and increment the index
  - if not, keep as is

So, let’s apply it:

pivot around number 3
7 is NOT smaller than our pivot number -> continue
10 is NOT smaller than our pivot number -> continue
4 is NOT smaller than our pivot number -> continue
2 IS smaller than our pivot number -> SWAP with 7 (because 7 is on 0th index)
- Increment pivot index
3 is our pivot number -> swap with whatever is on pivot index (1)

After doing that, we’re left with 2, 3, 4, 7, 10. The entire array now is 2,3,4,7,10,15,20.

So, a little recap in here:

It doesn’t matter if you pivot from right or left. You have to go through the entire array going TO that index
You have to run the code as many times as the number you’re trying to select.
- The complexity for 8th smallest number is O(8N) -> O(N)
- It may seem like the complexity to find the largest number is O(N^2) since it’s O(N*N).
- But not really, because we always halve the array. We’ll always know the half where to look.

So, let’s write code for the partitioning!

function partition(arr, leftPointer = 0, rightPointer = arr.length - 1) {
    const pivot = arr[rightPointer];
    let pivotIndex = leftPointer;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] <= pivot) {
            console.log(i)
            console.log(arr)
            swapArrayElements(arr, pivotIndex, i)
            pivotIndex++
        }
    }
    return pivotIndex
}

In the above code, we’ve done the following:

We defined a function which takes an array, leftPointer and rightPointer
- leftPointer is 0 - the starting index of array
- rightPointer is the length of the array
We go through the array
- If the item on current position is smaller or equal than the pivot number, swap the elements
- smaller than because we want to move all smaller elements first
- equals so we can move it one last time for the pivot number itself
Finally, we return the pivotIndex. That is the position.

If we run the function once for [7,10,4,2,3], the result will be 2.

After running it, the result will be 2, 3, 4, 7, 10
The result is the position in array, not the index!
- The number 3 is on the 2nd position (= index 1)

So, how do we combine this with the selection part? Well, we need to do it multiple times. So let’s do that!

const quickSelect = (arr, nthLowestNumber, leftPointer = 0, rightPointer = arr.length - 1) => {
    if (leftPointer === rightPointer) return arr[leftPointer];
    const pivotIndex = partition(arr, leftPointer, rightPointer)
    if (pivotIndex === nthLowestNumber) return nthLowestNumber;
    if (nthLowestNumber > pivotIndex) return quickSelect(arr, nthLowestNumber, pivotIndex + 1, rightPointer)
    if (nthLowestNumber < pivotIndex) return quickSelect(arr, nthLowestNumber, leftPointer, pivotIndex - 1)
    return arr[pivotIndex];
}

function partition(arr, leftPointer, rightPointer) {
    const pivot = arr[rightPointer];
    let pivotIndex = leftPointer;
    for (let i = leftPointer; i < arr.length; i++) {
        if (arr[i] <= pivot) {
            swapArrayElements(arr, pivotIndex, i)
            pivotIndex++
        }
    }
    return pivotIndex - 1 // <--- NOTE THIS
}

In the quickselect now, we basically do:

if pointers are identical, then the value was found - return current position
partition the array
if the number we’re searching for is larger, that means it’s on the right, that means we start from pivotIndex + 1 until end
if the number we’re searching for is smaller, that means it’s on the left, that means we start from start to pivotIndex - 1

Note that I’ve mentioned before the pivotIndex in partition was the position. To retrieve the index, we’ll remove it once again

if we’d like the pivotIndex to really be index, we can make a couple adjustments inside the for loop:

// previously
if (arr[i] <= pivot) {
    swapArrayElements(arr, pivotIndex, i)
    pivotIndex++
}
// later
if (arr[i] <= pivot) {
    swapArrayElements(arr, pivotIndex, i)
}
if (arr[i] < pivot) {
    pivotIndex++
}

And that’s it! That’s basically partition and quick select!

As I mentioned, both quicksort and quickselect use partitions. If you understood quickselect, you’ll surely understand quicksort. Because the only difference where you call it.

In quickselect, we’re always moving towards the smaller/bigger numbers
In quicksort, we want to do the operation on both sides

So, quicksort would use exactly the same code as quickselect, except the “selecting” function would be sort:

function quickSort(array, leftPointer, rightPointer) {
    if (rightPointer - leftPointer <= 0) return
    const pivotIndex = partition(array, 0, rightPointer);
    quickSort(array, leftPointer, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, rightPointer);
}

And that’s it! You’ve now learned quicksort and quickselect! Congratulations!

Summary

That was a wild ride! In this case, I’ve gone through a sorting and selecting algorithm.

While sorting is a lot done under the hood by the languages we use, it’s still nice to take a look at how it’s actually done. It gives us more knowledge about train of thought and how we can leverage it.