Searching, Sorting and Recursion | IT Foundations for Beginners

In this chapter

We'll learn the two jobs every program does constantly — finding things and putting them in order — with linear and binary search, sorting, iteration, and recursion (a function that calls itself), explained with names in a pile, a dictionary and Russian nesting dolls.

14–16 min

The Problem in Real Life

The new seat map needs two small features. First: "Find my seat" — a fan types "N2-C-14" and the map zooms to it. Second: "Sort by price" — show the cheapest available seats first.

And to count the free seats in each stand, Anna has to walk down the stadium tree from the stand to every section, row and seat. She writes a loop inside a loop inside a loop, and gets lost in her own code. John looks over her shoulder: "There's a neater way. Have you ever opened a set of Russian dolls?"

Finding, sorting, counting — it feels like every feature needs the same few tricks.

Anna

Checking Everything vs. Searching Smartly

Finding takes time

Looking through items one by one is simple, but slow when there are thousands.

Order makes finding faster

If items are sorted, you can skip huge parts of the list — like a dictionary.

Trees need a different walk

Going through things inside things is easiest with a function that calls itself.

Searching, Sorting, Iteration and Recursion

Searching — two ways to find a name: imagine a pile of 1,000 unsorted registration cards, and you need Zoë's. The only way is to pick up the first card, check it, then the next, and so on until you find it. That's linear search: check each item in turn. On average you look at half the pile, and in the worst case all of it.

Now imagine the same 1,000 names in a dictionary, sorted alphabetically. You open near the middle — M. Zoë comes after M, so you ignore the whole first half and open the middle of the second half — T. Still after. Open the middle of what's left — W. Then Y. Then Z. Each look throws away half of what's left. That's binary search. For 1,000 names it takes at most about 10 looks. For a million names, about 20. The catch: it only works if the data is sorted first.

Sorting — putting things in order: think of sorting a hand of playing cards. Most people pick up one card at a time and slide it into the right place among the cards they already hold. That's a real sorting method (insertion sort). Computers have faster methods for big lists, like merge sort: split the pile in half again and again until each pile has one card, then merge the small sorted piles back together. You will almost never write a sorting method yourself — every language has a fast, tested built-in sort. What you need to know is why you sort: to show things in order (cheapest first), and to make fast searching possible.

Iteration — doing it again and again with a loop: iteration means repeating steps with a loop, like the for loops from Act 07. Linear search is iteration: for each card, check it. Most everyday code uses iteration.
Recursion — Russian nesting dolls: you open a doll and find a smaller doll inside. You open that one, and find a smaller one. You keep going until you reach the tiny solid doll that doesn't open. Recursion is a function that solves a problem by calling itself on a smaller piece of the same problem, until it reaches a piece so small the answer is obvious.
The two parts of every recursive function: the base case is the tiny solid doll — the simplest situation, answered directly without calling itself again. The recursive case is "open this doll" — handle one layer and call the same function on the smaller doll inside. Without a base case, the function calls itself forever, the call stack (a stack of plates, from chapter 2) piles up until it runs out of room, and the program crashes with a stack overflow.
Recursion fits trees perfectly: counting free seats in a stand is the same question at every level. To count free seats in anything: if it's a single seat (base case), the answer is 1 if it's free, 0 if not. Otherwise (recursive case), count the free seats in each of its children and add them up. The same short function works for the whole stadium, one stand, one section or one row.

Table — Linear vs. binary search

Items	Linear search (worst case)	Binary search (worst case)
10	10 looks	4 looks
1,000	1,000 looks	10 looks
1,000,000	1,000,000 looks	20 looks

Binary search only works on sorted data.

Table — Recursion as Russian dolls: counting free seats

Doll	Recursion	In countFree
Open a doll, find a smaller one inside	Recursive case: call yourself on a smaller piece	Count each child, add them up
The tiny solid doll	Base case: answer directly	A single seat: 1 if free, 0 if not
A doll that never ends	No base case → stack overflow	Program crashes

Binary search: finding "Zoë" in 1,000 sorted names

Look at the middle: M

Zoë comes later → drop the first half (500 left)

half thrown away

Middle of the rest: T

later again → 250 left

half thrown away

Middle again: W

later → 125 left

... a few more halvings ...

62 → 31 → 15 → 7 → 3 → 1

Found Zoë

about 10 looks instead of up to 1,000

Counting free seats with recursion

function countFree(place) {
  // Base case: a single seat — the tiny doll
  if (place.type === "seat") {
    return place.state === "FREE" ? 1 : 0;
  }
  // Recursive case: count each child (section, row...) and add them up
  let total = 0;
  for (const child of place.children) {
    total += countFree(child);
  }
  return total;
}

countFree(stadium);       // every free seat in the stadium
countFree(northStand);    // just one stand — same function

// Sorting with the built-in sort: cheapest first
freeSeats.sort((a, b) => a.priceCents - b.priceCents);

The same five-line function works at every level of the tree, because every level asks the same question.

Iteration or recursion? Anything recursion can do, a loop can also do, and the other way round. Use whichever makes the code clearer. Recursion is often clearer for trees and nested data (folders inside folders, sections inside stands). Loops are clearer for simple lists.

Anna replaces her three nested loops with a five-line recursive countFree function. For "Find my seat" she uses the hash table from chapter 2 — even faster than binary search for an exact ID. For "Sort by price" she uses the built-in sort. Three features, three different tools.

Key Takeaway

Linear search checks every item; binary search keeps halving a sorted list, so it needs about 20 looks for a million items — but only if the data is sorted. Sorting puts data in order for display and fast searching; use the built-in sort. Iteration repeats with a loop; recursion solves a problem by calling itself on a smaller piece until it reaches a base case — ideal for trees.

Why This Matters

Searching and sorting are behind almost every screen you use: search boxes, "sort by price," "most recent first," autocomplete. Knowing that sorted data can be searched in a handful of steps — and that hash tables can do even better for exact keys — is exactly the kind of thinking that turns slow features into fast ones. Recursion will come back whenever you work with nested data, including folders, menus and web pages.

Anna has the right tools for every part of the seat map. Now John wants her to see why the old code was so slow — with numbers — using an idea every developer uses to predict performance before it becomes a problem.