I have been reading a book on algorithms lately, and I thought I would do a review of the algorithms the book covers. The book, “Grokking Algorithms, Second Edition” by Aditya Bhargava, is well worth a read if you haven’t studied algorithms or if you would like a refresher. In Part 1 of this series, I wrote about the binary search algorithm. In Part 2a>, I wrote about the selection sort algorithm. Today, I write about recursion and one of the algorithms that employs it as a strategy, quicksort.

Recursion

If you are a working programmer, you are more than likely very familiar with recursion already. I wrote my first recursive functions as a professional recursing through folders on a server to read files for a browser-based text file editor in the mid-90s. The original code was written in Perl and converted to CFML. In JavaScript, using NodeJS, it looks something like this:

import * as fs from 'fs'
import * as path from 'path'

const basepath = '/somePath/'
async function readFolder(thePath) {
    const folder = { path: thePath, childFolders: [], files: [] }
    const files = await fs.promises.readdir(thePath)

    for (const file of files) {
        const fullPath = path.join(thePath, file)
        const stats = await fs.promises.stat(fullPath)

        if (stats.isDirectory() && file !== '.' && file !== '..') {
            folder.childFolders.push(await readFolder(fullPath))
        } else {
            folder.files.push(file)
        }
    }
    return folder
}

// Usage:
readFolder(basepath)
    .then((myfolders) => console.dir(myfolders))
    .catch(console.error)

This code reads a directory, loops over its contents, recursively reads any child directories, and packages up the whole thing into a nested array. Recursion is a very powerful way to deal with this class of problems. I like to use the nested folder example because everyone understands how nested folder structures work.

Quicksort

The quicksort algorithm uses recursion to sort values. In the case of this example, the algorithm sorts numeric values in an array. The algorithm uses a strategy called divide and conquer by partitioning the given array into values less than and greater than an arbitrary value in the array, in this case the first element of the array. It then uses recursion to break the array down into smaller and smaller partitioned arrays until each recursion hits the base case.