Recursion, numerical sums, and repeatable simulations

A loop repeats a block within one function call. Recursion repeats work through another call to the same function. To understand either, identify what changes each time and what stops the repetition. Numerical sums add another question: is the result an exact quantity, a partial sum, or an approximation to a target?

A simulation uses a model to generate possible outcomes. Repeating it can produce useful evidence, but a repeatable run and a proof are different things. This article separates these ideas so their assumptions stay visible.

A smaller call and a stopping case #

A recursive function calls itself to solve a smaller version of a task. Its base case returns without making another recursive call. Its recursive step must move toward that case. Each invocation has its own parameters and local variables, even though all the invocations use the same source code.^[1]

#include <iostream>

double inverse_square_sum(int n) {
    // Precondition: 0 <= n <= 100 for this demonstration.
    if (n == 0) return 0.0;
    const double term = 1.0 / (static_cast<double>(n) * n);
    return inverse_square_sum(n - 1) + term;
}

int main() {
    std::cout << inverse_square_sum(2) << '\n';
}

The stated input contract is 0 <= n <= 100 for this demonstration. The function does not check this contract itself. Its caller must supply a value in that range. Begin with the actual call in main, where n is 2.

For the n-equal-to-2 invocation, the base-case test is false. The next line computes a term. static_cast<double>(n) gives the floating-point value 2.0; multiplying by n gives 4.0. Dividing 1.0 by that value produces 0.25. This invocation keeps its own term while it calls the function with n - 1, which is 1.

The n-equal-to-1 invocation also misses the base case. Its denominator is 1.0, so its term is 1.0. It calls the function with 0. That invocation meets the base case and immediately returns 0.0; it does not calculate a term, so it does not divide by zero.

Now follow the returns upward. The n-equal-to-1 invocation receives 0.0 from its smaller call, adds its own 1.0, and returns 1.0. The n-equal-to-2 invocation receives 1.0, adds its own 0.25, and returns 1.25 to main. The output is 1.25.

A useful paper trace has one row for each invocation: its n, its term if it calculates one, and the value it eventually returns. The calls move down toward zero; the completed sums return upward. The pending work is why recursion consumes storage for active calls. Large depth can exhaust available call-stack resources. A loop with an accumulator can compute this sum without retaining a chain of recursive calls.

Choose arithmetic before formatting #

An accumulator starts with the sum for no terms, 0.0. Each step adds the next term to the previous sum. Computing every earlier term again for each new candidate n repeats unnecessary work; updating the prior partial sum avoids that repetition.

The expression 1 / (n * n) does not reproduce the demonstration's floating-point calculation when all operands are integers. At n equal to 2, the numerator and denominator are integer 1 and 4, and integer division gives 0. The fractional part is discarded. Converting after that division cannot recover it. Also, for sufficiently large integers, n * n can overflow before a later conversion. Convert before the multiplication and division as the demonstration does, while still keeping a sensible input range.

The sum through n is a partial sum. It is not automatically the full value of an infinite series. Before calling it an approximation to a particular target, establish why the partial sums approach that target and how to assess the remaining difference.

Absolute error measures the magnitude of the difference from a target value. Relative error compares that difference to an appropriate scale, often the target's magnitude; a zero or very small target needs special care. The justified scale and stopping rule belong to the method. They cannot be inferred from the number of digits printed.

A tolerance is an allowed error or change under a stated rule. Display precision controls presentation. Printing six digits does not establish that six digits are accurate. If stopping compares consecutive sums, explain why that change is relevant; a small change alone is not a general proof of closeness to an unknown target.

Repeat a pseudorandom experiment #

A pseudorandom generator produces a deterministic sequence from its state. A seed selects an initial state. Keeping the seed fixed helps reproduce a test: with the same setup, the same sequence can be examined again. Choosing a varying seed changes runs but does not by itself establish good statistical behavior.

A generator supplies values; a distribution maps them into the kind of values the experiment needs. C++ provides generators and distributions in <random>.^[2] Choosing an appropriate supplied distribution is preferable to assuming that a homemade arithmetic mapping produces the intended probabilities.

For a real u in [0, 1), the expression low + int((high - low + 1) * u) maps into an inclusive integer range when the stated arithmetic and bounds are suitable. With low 2 and high 4, there are three integer choices. A u of 0 maps to 2, while a u of 0.5 maps to 3. Because u is below 1, the mapping does not reach 5. But a finite generator combined with this mapping can introduce bias: some choices can occur more often. std::uniform_int_distribution states the intended inclusive integer distribution directly.

Monte Carlo search samples candidate solutions, checks their validity, and records a score. Keep the best valid candidate seen so far, updating it only when a better valid score appears. A million samples still do not prove a global optimum. Describe the model, sampling method, seed policy, and observed best result so the evidence can be interpreted.

Practice with explained answers #

Replacing the recursive call's n - 1 with n makes no progress. With a positive starting n, every call repeats the same non-base input. Starting below zero also violates this function's contract and moves away from zero under n - 1. A contract is therefore part of the explanation, not an optional comment to ignore.

For an error limit of 0.01, test a result just above it, one just below it, and one equal to it. Decide whether the comparison accepts equality. Separating arithmetic, stopping rules, and repeatable tests extends the loop, function, debugging, and numerical reasoning used in CS2 Labs 1 and 4.