Implementing Iterative Solutions in C++

Putting Iteration to Work

You already know that loops are C++'s tools for repetition. Now, let's move from theory to practice. We'll implement iterative solutions to a few classic programming problems, focusing on how to translate a repetitive process into clean, efficient code.

Calculating Factorials

A factorial is the product of all positive integers up to a given number. For example, the factorial of 5, written as $5!$ , is $5 \times 4 \times 3 \times 2 \times 1$ . It's a perfect candidate for iteration because it involves a clear, repetitive multiplication task.

n! = n \times (n-1) \times (n-2) \times \dots \times 1

To implement this iteratively, we can use a for loop that counts down from the number n to 1, multiplying the results at each step. We'll need a variable to accumulate the product, which should start at 1.

#include <iostream>

// Calculates the factorial of n using a for loop
long long factorial(int n) {
    // Start with 1, the multiplicative identity
    long long result = 1;

    // Handle the base case of 0! which is 1
    if (n < 0) return -1; // Factorial is not defined for negative numbers
    if (n == 0) return 1;

    // Loop from n down to 1
    for (int i = n; i >= 1; --i) {
        result *= i; // result = result * i
    }

    return result;
}

int main() {
    std::cout << "5! is " << factorial(5) << std::endl; // Outputs 120
    return 0;
}

Why initialize result to 1? Because 1 is the multiplicative identity. If we started with 0, the final result of any multiplication would always be 0.

The Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, and so on. It's another problem that lends itself well to an iterative solution, as we repeatedly apply the same rule to generate the next number in the sequence.

The key to an iterative approach is to keep track of the two previous numbers. In each step of our loop, we'll calculate the next number, then update our two tracking variables to prepare for the next iteration.

#include <iostream>

// Prints the first n Fibonacci numbers
void printFibonacci(int n) {
    if (n <= 0) return;

    long long a = 0, b = 1;

    std::cout << a << " ";
    if (n == 1) return;

    // We've already printed the first number, so loop n-1 times
    for (int i = 1; i < n; ++i) {
        std::cout << b << " ";
        
        long long next = a + b; // Calculate the next number
        a = b;                 // 'a' becomes the old 'b'
        b = next;              // 'b' becomes the new 'next'
    }
    std::cout << std::endl;
}

int main() {
    printFibonacci(10); // Outputs: 0 1 1 2 3 5 8 13 21 34 
    return 0;
}

The core of the logic is in these three lines inside the loop:

long long next = a + b; We calculate the new term.
a = b; The second-to-last number is now the former last number.
b = next; The last number is now our newly calculated term.

This effectively slides our two-number window one step down the sequence for the next calculation.

Traversing Arrays

One of the most common tasks in programming is processing each element in a collection of data, like an array. Iteration is the natural way to do this. The classic method is a for loop that uses an index to access each element.

#include <iostream>

int main() {
    int scores[] = {88, 92, 77, 95, 84};
    int size = sizeof(scores) / sizeof(scores[0]);

    // Classic index-based for loop
    for (int i = 0; i < size; ++i) {
        std::cout << "Score at index " << i << ": " << scores[i] << std::endl;
    }

    return 0;
}

This approach gives you full control. You have the index (i) and the value (scores[i]), which is useful if the position of the element matters. However, C++ offers a cleaner, more modern way to do this when you only need the value: the range-based for loop.

#include <iostream>

int main() {
    int scores[] = {88, 92, 77, 95, 84};

    // Modern range-based for loop
    for (int score : scores) {
        std::cout << "Score: " << score << std::endl;
    }

    return 0;
}

This version is less prone to errors. You don't have to manage an index variable or worry about getting the loop's boundary condition wrong, a common bug known as an "off-by-one error." The loop simply iterates over each element in the scores array, assigning its value to the score variable in each pass.

Best practice: Prefer range-based for loops for simple array traversal. Use index-based loops only when you need the element's position.

By understanding how to apply these iterative patterns, you can solve a wide range of problems methodically. The key is to identify the repetitive action and the state that needs to be updated in each step.

Iteration and Recursion in C++