Computational Thinking

The hardest part of programming is not the language. It is teaching yourself a particular way of thinking about problems. Computer scientists call this computational thinking, and it has four classic ingredients:

1. Decomposition — break a big problem into small pieces.
2. Pattern recognition — notice that two pieces are similar.
3. Abstraction — ignore irrelevant details and focus on what matters.
4. Algorithms — write a precise, step-by-step procedure.

Most beginner frustration comes from trying to write code before doing those four things. This chapter is mostly prose, with a few code blocks for illustration. The goal is to install a habit.

Why "computational" thinking?

Computers cannot guess. They cannot pick up on context. Anything that you do not spell out explicitly does not happen. If you forget to handle an empty list, the empty list will arrive and your program will misbehave. If you do not consider negative numbers, negative numbers will appear and ruin your day.

The job of a programmer is therefore to:

• Imagine every input the program might see.
• Decide exactly what should happen for each one.
• Write that down in a form the computer can execute.

That requires almost-paranoid precision. With practice it becomes a mostly enjoyable habit.

Decomposition: break the problem down

Suppose your task is "write a program that reads a list of student names and grades and prints the top three students." That sounds hard. Before writing a single line of C++, decompose it:

Each leaf of that tree is small enough that you could probably write it in 5–15 lines of C++. That is what you should code first — the leaves — not the whole thing at once.

Pattern recognition: spot the repetition

After decomposing, look for parts that are the same in shape. Two nearly-identical pieces of code is your cue to invent an abstraction.

Here is a pre-pattern-recognition version of a simple program:

Three lines look almost identical: take a value, subtract the average, drop the sign. That repetition is screaming for a function.

We named the pattern (deviation) and used it three times. The program got smaller, easier to read, and easier to change.

Abstraction: ignore what doesn't matter

Abstraction is the act of forgetting details that do not change the answer. When you say "the average of these grades," you do not care whether the grades are stored in an array, a vector, or a linked list. You only care that you can iterate over them and add them up.

C++ rewards abstraction: the standard library is full of generic algorithms that work on anything that behaves like a sequence.

std::accumulate does not know or care that the data lives in a vector. It just walks from a beginning iterator to an end iterator, accumulating. That is abstraction at work.

Algorithms: precise step-by-step procedures

An algorithm is a finite, unambiguous, terminating procedure for solving a problem. Every program is built out of algorithms, big and small. Before writing code, it is enormously useful to write the algorithm out in plain language (called pseudocode) first.

Here is the algorithm for "find the maximum element of a list":

1. If the list is empty, there is no maximum. Report an error.
2. Let `best` = the first element.
3. For each remaining element `x`:
       if x > best, set best = x.
4. After the loop ends, `best` holds the maximum. Return it.

Now the translation into C++ is almost mechanical:

If you ever feel stuck staring at a blank editor, drop down a level: write the algorithm in English first, then translate.

A worked example: FizzBuzz, deliberately

The classic warm-up problem: print the numbers 1 to 100, but for multiples of 3 print "Fizz", for multiples of 5 print "Buzz", and for multiples of both print "FizzBuzz".

Let's not leap into code. Walk through computational thinking first.

Decompose:

• A loop from 1 to 100.
• A decision at each number: print Fizz / Buzz / FizzBuzz / the number.

Pattern-recognize:

• "Is it a multiple of N?" appears twice (3 and 5). That is a reusable predicate: n % m == 0.

Abstract:

• The core idea is: classify each number into one of four categories.

Algorithm:

For i from 1 to 100:
    if i divisible by 15: print "FizzBuzz"
    else if i divisible by 3: print "Fizz"
    else if i divisible by 5: print "Buzz"
    else: print i

Now the C++ practically writes itself:

Notice that we thought through the order of the checks: the most specific case (multiples of 15) goes first, otherwise the multiples of 3 would always win. That kind of ordering bug is one of the most common reasons FizzBuzz interviews go wrong. Decomposition catches it for free.

Edge cases: the secret weapon

The strongest habit you can build is asking, after every algorithm, "what about the weird inputs?" For a function that takes a list:

• What if the list is empty?
• What if the list has exactly one element?
• What if all elements are equal?
• What if the elements are negative?
• What if the list is huge?
• What if the input has duplicates?

Most production bugs are edge cases the programmer forgot. Train yourself to enumerate them before you finish the code.

A challenge: practice computational thinking

Test your understanding

Next: variables and memory — what is a variable, really?