Loops That Finish and Functions You Can Trust

By FreePare Team · Fri Jul 31 2026 · 11 min read

Loops That Finish and Functions You Can Trust

Invariants, contracts, recursion, and the finite call stack

Code does not become correct because it looks elegant.

A loop needs a reason to stop. A function needs a precise promise. A recursive call needs to move toward a base case. If any of those pieces is missing, the program may become a very expensive space heater.

This article treats control flow as something we can explain and test, not a collection of lucky if statements.

What this article covers

1. Correct code starts with a claim

Suppose a function searches a sorted array.

Its contract might be:

Preconditions

Postconditions

That is more useful than:

"This function does binary search."

The second sentence names an algorithm. The first set of statements tells us how to verify it.

2. Preconditions should match the failure policy

C: return an explicit status

#include <stdbool.h>
#include <stddef.h>

typedef enum {
    SEARCH_FOUND,
    SEARCH_NOT_FOUND,
    SEARCH_INVALID_ARGUMENT
} SearchStatus;

SearchStatus binary_search(
    const int *values,
    size_t length,
    int target,
    size_t *found_index
) {
    if ((values == NULL && length != 0) || found_index == NULL) {
        return SEARCH_INVALID_ARGUMENT;
    }

    size_t low = 0;
    size_t high = length;

    /* Search interval is [low, high). */
    while (low < high) {
        size_t middle = low + (high - low) / 2;

        if (values[middle] < target) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }

    if (low < length && values[low] == target) {
        *found_index = low;
        return SEARCH_FOUND;
    }

    return SEARCH_NOT_FOUND;
}

Using the half-open interval [low, high) removes the need to represent -1 in an unsigned index. It also makes empty input natural: both endpoints are zero.

assert() is useful for programmer invariants during development, but it can disappear when NDEBUG is defined. Do not use it as the only validation for untrusted input.

Java: reject invalid input explicitly

import java.util.Objects;

public final class BinarySearch {
    public static int firstIndexOf(int[] values, int target) {
        Objects.requireNonNull(values, "values");

        int low = 0;
        int high = values.length;

        while (low < high) {
            int middle = low + (high - low) / 2;

            if (values[middle] < target) {
                low = middle + 1;
            } else {
                high = middle;
            }
        }

        return low < values.length && values[low] == target
            ? low
            : -1;
    }

    private BinarySearch() {}
}

This contract still depends on sorted input. Checking sortedness inside every call would turn an \(O(\log n)\) search into an \(O(n)\) operation. The design must decide whether sortedness is guaranteed by the caller, validated at a boundary, or represented by a dedicated type.

Python: type hints plus runtime validation

from collections.abc import Sequence


def first_index_of(values: Sequence[int], target: int) -> int | None:
    low = 0
    high = len(values)

    while low < high:
        middle = low + (high - low) // 2

        if values[middle] < target:
            low = middle + 1
        else:
            high = middle

    if low < len(values) and values[low] == target:
        return low

    return None

The type hint helps tools and readers. Python does not automatically enforce it at runtime.

3. The loop invariant is the plot summary

For the half-open binary search, a useful invariant is:

If the target can still be the first matching value, its candidate position is in [low, high).

At every iteration:

1. middle lies inside [low, high).

2. If values[middle] < target, no position through middle can be the first match.

3. Otherwise, middle remains a candidate and becomes the new upper boundary.

The interval becomes smaller each time.

That final sentence is the termination proof.

A termination measure

Define a termination measure M = high - low.

Before every iteration, M is a non-negative integer. Every branch strictly reduces it. Therefore, the loop cannot continue forever.

This style is useful beyond binary search:

If you cannot name the decreasing measure, the loop deserves suspicion.

4. Midpoint arithmetic still needs a contract

The failure this section guards against is an arithmetic one, and Integer Boundaries is where the arithmetic is: what the sum does when it leaves the type's range, and why the answer differs in C, Java and Python.

This expression is famous:

(low + high) / 2

For fixed-width signed integers, low + high may overflow even when the final midpoint would fit.

Prefer:

low + (high - low) / 2

But this is not magic dust. It relies on:

An arithmetic trick cannot repair a broken invariant.

5. A function signature is only part of the contract

Consider:

User loadUser(String id)

The signature does not answer:

A technically strong function documents the behavior that its type system cannot express.

Prefer contracts that fit in a few sentences

This function has too many responsibilities:

Result importUsersAndSendEmailsAndUpdateDashboard(File file)

A clearer design separates:

ParsedUsers parseUsers(File file);
ValidationReport validateUsers(ParsedUsers users);
ImportResult importUsers(ValidatedUsers users);
NotificationResult notifyImportedUsers(ImportResult result);

This is not about producing the maximum possible number of tiny methods. It is about keeping each unit cohesive enough to:

6. Side effects are extra return values

def calculate_total(items: list[int]) -> int:
    global calculations
    calculations += 1
    return sum(items)

The function returns a total, but it also changes global state. That mutation is an additional observable output.

Common side effects include:

Side effects are not automatically bad. Hidden side effects are difficult to reason about.

Name them, isolate them, and test them.

7. Error handling is part of the public contract

C

C commonly uses:

Do not overload one value with multiple meanings unless the contract makes the distinction possible.

Java

Java uses checked and unchecked exceptions:

Do not catch Exception merely to print and continue. Either recover with a defined policy, add context and rethrow, or let the appropriate layer handle it.

Python

Python exceptions are unchecked. Any call may propagate a documented or implementation-originated exception.

Catch narrowly:

try:
    configuration = load_configuration(path)
except FileNotFoundError:
    configuration = default_configuration()

This has a recovery policy. except Exception: pass has a disappearing-problem policy.

8. Recursion needs a domain, not just a base case

Here is a safe factorial contract for C using unsigned long long:

#include <stdbool.h>

bool factorial(unsigned int number, unsigned long long *out) {
    if (out == NULL || number > 20) {
        return false;
    }

    if (number <= 1) {
        *out = 1;
        return true;
    }

    unsigned long long previous;
    if (!factorial(number - 1, &previous)) {
        return false;
    }

    *out = number * previous;
    return true;
}

Why cap the input at 20? Because 20! fits in a 64-bit unsigned integer and 21! does not.

Compare that with:

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

factorial(-1) does not recurse forever. It immediately returns 1, which is still a bug because the domain was not validated.

The correct lesson is:

A reachable base case does not guarantee a correct domain model.

9. The call stack is finite, but there is no universal depth

Each function call requires implementation-managed state. Depending on the language and runtime, that may include:

You cannot honestly claim:

The limit depends on the program, ABI, compiler optimization, OS stack setting, JVM options, runtime, and function body.

Python exposes a recursion limit through sys.getrecursionlimit(), but that is a guard, not a promise that every program can safely reach exactly that depth.

import sys

print(sys.getrecursionlimit())

Do not raise the limit casually. A higher Python guard does not create an infinite native stack.

10. Recursive and iterative graph traversal

Stacks, Queues, Deques, Backtracking & Trees takes the same pair of traversals further — an explicit stack, a queue frontier, and the tests that separate a skewed structure from a balanced one.

Consider a graph rather than a tree. Without a visited set, a cycle can recurse forever:

graph = {
    "A": ["B"],
    "B": ["C"],
    "C": ["A"],
}

Recursive DFS

def depth_first_recursive(
    graph: dict[str, list[str]],
    start: str,
) -> list[str]:
    visited: set[str] = set()
    order: list[str] = []

    def visit(node: str) -> None:
        if node in visited:
            return

        visited.add(node)
        order.append(node)

        for neighbour in graph.get(node, []):
            visit(neighbour)

    visit(start)
    return order

Iterative DFS

def depth_first_iterative(
    graph: dict[str, list[str]],
    start: str,
) -> list[str]:
    visited: set[str] = set()
    order: list[str] = []
    stack = [start]

while stack:

        node = stack.pop()

        if node in visited:
            continue

        visited.add(node)
        order.append(node)
        stack.extend(reversed(graph.get(node, [])))

    return order

Both versions are \(O(V + E)\) for a graph represented by adjacency lists.

The iterative version moves traversal state into an explicit heap-managed container. It does not make memory usage disappear; it makes the state visible and avoids dependence on call-stack depth.

11. Real filesystem traversal has more than a stack problem

A publishable filesystem crawler must consider:

A recursive three-line example can teach recursion, but it should not be presented as production-ready filesystem code.

12. Tail recursion is not a portability strategy

Some compilers can reuse a frame for a tail call. That does not mean every language implementation must do so.

If input depth is unbounded and stack safety matters, use an iterative design or a runtime with a documented mechanism that meets the requirement.

13. Test the contract, not just the example

For binary search, test:

For recursion, test:

A property is stronger than a pile of anecdotes:

If the function returns index i, then 0 <= i < len(values) and values[i] == target.

Try it yourself

1. Instrument binary search to print [low, high) after every iteration.

2. Write the termination measure beside the loop and verify that every branch reduces it.

3. Add a sortedness check outside the timed search and explain where it belongs in a real API.

4. Run both DFS versions on a chain of increasing depth.

5. Extend the traversal to report errors instead of silently skipping inaccessible nodes.

Exit test

You understand control-flow contracts when you can answer:

1. What must be true before the operation?

2. What remains true through every iteration?

3. What strictly moves the algorithm toward termination?

4. What is guaranteed after success?

5. How are invalid input, resource exhaustion, and operational failure represented?

Final return

A loop is a promise that progress will happen. A function is a promise about inputs, outputs, and effects. Recursion is a promise that every call gets closer to home.

Make those promises explicit, and your code becomes easier to test, review, and trust.

Tags: coding-fundamentals, programming-fundamentals, computer-science-fundamentals, coding-interview-tips, coding-practice, career-growth-skills, student-learning-guide, study-tips-for-students