Taking ThePrimeagen’s Algorithms Course: recursion, quick sort, and doubly linked list

This is the second part of a mini-series where I publish my notes and observations while taking ThePrimeagen’s “The Last Algorithms Course You’ll Need” on Frontend Masters. For more details, have a look at the first post:

As always, the TypeScript implementations of the exercises are available here:

Recursion

Recursion

• recursion = a function that keeps calling itself until a “base case” is reached at which the problem is solved
• so the first step is always to define the base case
• important concepts for any function: return address (where does the function return its value to?), return value, arguments
• example:

function foo(n: number): number {
    // Base Case
    if (n === 1) {
        return 1;
    }

    // We shall Recurse!
    return n + foo(n - 1);
}

• so when you start a recursive function, the return address is whatever calls the function, but when the function calls itself, the return address becomes the first instance of the function and the return value is undecided; so you build a function stack until you hit the base case, and then you can go back up because all the values can be decided
• step one: building the stack of functions

function | return address | return value | arguments
foo(5)   | calling func   | 5 + ?        | 5
foo(4)   | foo(5)         | 4 + ?        | 4
foo(3)   | foo(4)         | 3 + ?        | 3
foo(2)   | foo(3)         | 2 + ?        | 2
foo(1)   | foo(2)         | 1            | null

• step two: determining the values (from the bottom up)

function | return address | return value | arguments
foo(1)   | foo(2)         | 1            | null
foo(2)   | foo(3)         | 2 + 1        | 2
foo(3)   | foo(4)         | 3 + 3        | 3
foo(4)   | foo(5)         | 4 + 6        | 4
foo(5)   | calling func   | 5 + 10       | 5

• recursion can be broken down into three steps: 1. pre: do something before you recurse (e.g. n+ ) 2. recurse: recursion itself (e.g. foo(n-1) ) 3. post: do something after the recursion

Path Finding: Base Case

• you need a good example to really get why you would need recursion, i.e. why recursion can solve problems that simple for-loop can’t
• “MazeSolver”, list of strings like this (# represents a wall) where you need to find the path from start (S) to end (E):

maze = [
    "##########E#",
    "##         #",
    "##S#########"
]

• base cases for current location: 1. off the map (invalid state) 2. we are on a wall (invalid state) 3. it’s the end (goal) 4. already visited this location

Path Finding: Recursive Case

• completely separate from base case
• check for each current location in four directions: up, right, down, left, and continue if you find a valid path
• an invalid path will return to the last valid path and then check the previously unchecked directions
• obviously keep track of visited locations and of the ultimate result, i.e. the path taken from start to end
• time complexity = O(n)

Quick Sort

Quick Sort

• “divide and conquer”-algorithm = split input into chunks, and solve the problem for a chunk to make it easier
• in quick sort we pick an element as a pivot and partition the given array around the picked pivot
• the target of partitions is, given an array and an element x of an array as the pivot, put x at its correct position in a sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x.
• this was the first one I really struggled with to understand: a very good, step-by-step illustration is available at this GeeksforGeeks page:

• time complexity = O(log n)best-case scenario, but O(n²) worst-case scenario!

Doubly Linked List

Linked List

• the correct order for operations = first attach the new node, next break the old links
• even though the concept of doubly linked list is, functionally, quite easy, it is complicated, or rather convoluted, to implement

Stay tuned for the next episode of my course notes, which will feature trees, tree search and heap.

Hi! 👋 I’m Tom. I’m a software engineer, a technical writer and IT burnout coach. If you want to get in touch, check out https://tomdeneire.github.io