Famous CS Algorithms: Recursion, Search, Sort, Pathfinding, and DP

Introduction

There are roughly six families of algorithm that every software engineer eventually meets — in a university course, a coding interview, or the moment a real production problem refuses to scale. Memorising line-for-line implementations is the wrong goal. Understanding how each family thinks, when it breaks, and what its big-O actually means is the goal that pays off.

This is a practical walkthrough of those six families: recursion, search, sorting, pathfinding, minimum spanning trees, and dynamic programming. Each section gives the mental model first, then the concrete examples (Fibonacci, binary search, merge sort, Dijkstra’s, Kruskal’s, minimum-sum subarray), and finally the time/space trade-offs that decide which one you reach for in production.

📚 Table of contents

🔁 Recursion

Recursion means a function that calls itself. Every recursive algorithm needs two ingredients: at least one base case (where the answer is already known) and at least one recursive case (where the function calls itself with a smaller problem). The trick is divide and conquer — break a hard problem into smaller versions of itself, solve those, combine.

Fibonacci, three ways

The Fibonacci progression is the canonical lesson: recursion is a thinking tool, memoization is the standard optimisation, and iteration usually wins on space. Most production code lives in the iterative column.

Binary tree traversals

Every binary-tree traversal is three lines of recursion plus a base case. node === null is the base case. The difference is when you visit the current node:

• In-order: left → node → right. Sorted output on a BST.
• Pre-order: node → left → right. Useful for copying or serialising a tree.
• Post-order: left → right → node. Useful for deleting a tree bottom-up.

Recursion as a creative tool

Even string reversal — trivially a for-loop — can be expressed recursively as reverse(rest of string) + first character. The structure shows up in parsing, traversal, backtracking, divide-and-conquer sorts, and graph search. Once the base case + recursive case shape is in your head, reading a new recursive algorithm becomes a translation exercise instead of a puzzle.

🔎 Searching: linear and binary

The simplest question: is x in this array?

A clean recursive implementation tracks start and end indexes instead of slicing the array:

• Base case: start > end → not found.
• Compute middle = floor((start + end) / 2).
• If arr[middle] === target → found.
• If arr[middle] > target → recurse on (start, middle - 1).
• Otherwise → recurse on (middle + 1, end).

👉 If you need to search a list repeatedly, sorting once (O(n log n)) and then doing many binary searches usually beats repeated linear scans.

🧭 DFS and BFS on a maze

Both depth-first search (DFS) and breadth-first search (BFS) explore every reachable cell — they just disagree about order. Use them to traverse trees, graphs, or grid mazes.

Implementation skeleton

1. Seed the stack/queue with the start position.
2. Keep a visited set to avoid cycles — serialise grid positions to strings (“y,x”) since arrays don’t deduplicate in JS sets.
3. Pop / shift; if it’s the goal, stop.
4. Otherwise compute valid neighbours (in bounds, not a wall, not visited) and push them.

Time complexity is O(W × H) for a grid — you can’t avoid visiting cells you need to visit. Watch out for BFS when the “queue” is just an array: array.shift() is O(n) in JavaScript and silently blows your complexity up to O((W × H)^2). Use a linked list or an index-based queue for real workloads.

🗂️ Sorting algorithms

Two properties matter when you compare sorts. Stability: elements with equal keys keep their original relative order. In-place: no extra array — sort by mutating the original. Now the algorithms split into two camps.

💡 Most languages ship one of the efficient sorts as the default. JavaScript’s Array.prototype.sort is typically Timsort under the hood — a hybrid of merge sort and insertion sort. Assume O(n log n) when reasoning about built-in sorts.

Merge sort, mechanically

Split the array in half recursively until each subarray has one element (sorted by definition). Then merge sibling subarrays back together by walking both and picking the smaller head into a new array. Each merge is linear; the recursion is log n deep; total O(n log n). Space is O(n) for the merge buffers.

🗺️ Pathfinding: Dijkstra’s and A*

BFS gives you shortest paths on unweighted graphs. The moment edges have weights — cost, distance, time — you need something smarter.

Dijkstra’s algorithm

• Initialise every node’s distance to infinity, except the start (distance 0).
• Push the start into a priority queue (min-heap).
• Pop the node with the smallest known distance. For each neighbour, relax its distance if going through the current node beats the existing value.
• Repeat until the queue empties or the target pops.

Runs in O((V + E) log V) with a binary heap. Requires non-negative weights — negative edges break the invariant.

A* — Dijkstra plus a heuristic

A* is the version most people actually ship for grid pathfinding. It adds a heuristic — a cheap-to-compute estimate of the remaining distance to the goal (Euclidean or Manhattan on a grid). The priority queue is keyed by current distance + heuristic, so the search biases toward the goal instead of expanding in every direction equally.

The win is real: in an open grid, A* will often touch a tiny fraction of the nodes Dijkstra would. In maze-heavy environments with obstacles, A* still has to backtrack, but the heuristic keeps it from wasting time on obviously-wrong directions.

🌲 Minimum spanning trees

A spanning tree of a connected graph is a set of edges that touches every vertex without forming a cycle. A minimum spanning tree is the spanning tree whose total edge weight is smallest. Useful for laying out networks, pipelines, circuits — anywhere you want full connectivity at minimum cost.

Kruskal’s algorithm

1. Sort all edges by weight, ascending.
2. Initialise each vertex in its own component (Union-Find / Disjoint Set).
3. Walk the sorted edge list. For each edge, if it connects two different components, add it to the MST and union the components.
4. Stop once the MST has V - 1 edges.

Time complexity is dominated by the edge sort: O(E log E). Union-Find with path compression and union by rank brings the union/find operations to effectively constant time per call.

👉 Prim’s algorithm is the alternative — it grows the MST one node at a time from a starting vertex, similar in spirit to Dijkstra. Kruskal tends to be easier to reason about when you already have the edge list; Prim is often faster on dense graphs.

🧱 Dynamic programming

Dynamic programming is what you reach for when a problem has overlapping subproblems — the same sub-questions keep coming up — and optimal substructure — the answer to the big problem is built from answers to small ones. Memoized recursion is one DP style; bottom-up tabulation is the other.

Worked example: minimum-sum contiguous subarray

Given an array, find the contiguous subarray with the smallest possible sum. The DP insight:

At each index i, the minimum sum of a subarray ending at i is either arr[i] alone, or arr[i] + (min-sum ending at i-1). Take the smaller.

Track the running “min sum ending here” and the global minimum as you scan. One pass, O(n) time. If you store every intermediate value, space is O(n) — but you only ever need the previous value, so the optimised version uses O(1) space. That space optimisation is the same trick that turned recursive Fibonacci into a two-variable loop.

When to suspect DP

• You wrote a naive recursive solution that times out, and the call tree visibly repeats work.
• The problem statement says “maximum”, “minimum”, “count the ways”, or asks for an optimal arrangement.
• Each decision depends only on a small, well-defined slice of earlier state — the previous element, the previous row, the last k items.

🚫 Common mistakes & pro tips

🎯 Conclusion

These six families — recursion, search, sorting, pathfinding, MST, and DP — show up over and over in interviews and in production. The honest goal isn’t to memorise every implementation, it’s to recognise the shape of each problem fast enough that you can pick the right family in minutes and adapt the canonical algorithm to the specifics in front of you.

Build the mental models, internalise the time and space complexities, and the implementation almost falls out of the description. The next time a coworker says “this is too slow,” you’ll catch yourself thinking which family of algorithm is this, and how do its trade-offs change the answer? — which is exactly the muscle worth building.

Explore More on DevShelf

• →
  AI Engineer Job Market 2026

  Data on which roles are growing — and which still require the algorithm fundamentals covered here for technical interviews.

• →
  Learn Agentic AI in 7 Steps

  Next step after algorithms — the structured path from LLM fundamentals to production AI agents.