Print Fibonacci Terms with Two Carried Values

Two carried values are enough to produce every next Fibonacci term

To print seven Fibonacci terms, you do not need to calculate each term from its earlier terms again. Carry the two values that describe your current position: remaining tells you how many terms still need printing, first is the next term to print, and second is the term after it. Starting with (7, 0, 1), each call prints first and passes the next state (remaining - 1, second, first + second).

void printFibonacci(int remaining, int first, int second) {
    if (remaining == 0) {
        return;
    }

    cout << first << " ";
    printFibonacci(remaining - 1, second, first + second);
}

The first call prints 0 and passes (6, 1, 1). That call prints 1 and passes (5, 1, 2). The repeated 1 is not a problem: one 1 is the current first value, and the other 1 is the next value used to form 2. Each call performs one addition and makes one recursive call, so no earlier term is recomputed.

Checking remaining before printing produces exactly seven terms

The base-case check must happen before the output statement. A state with remaining equal to zero has no terms left to print, so it returns immediately. The states with remaining values 7 through 1 each print once, while the final state (0, 13, 21) prints nothing.

There are seven states that print, so the output is 0 1 1 2 3 5 8. The eighth state exists because the last printing call still makes one recursive call, but it is only the stopping state. It confirms that all requested terms have been printed and contributes no extra output.

Each call preserves the next two terms the following call needs

The key invariant is that first is always the term to print in the current state, and second is the term immediately after it. In (7, 0, 1), the pair is 0 and 1. After printing 0, the next pair is (1, 1). After printing the first 1, the next pair is (1, 2). The repeated value 1 remains correct because consecutive Fibonacci terms can have the same value.

The complete sequence of carried pairs is (0, 1), (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), and finally (13, 21) in the non-printing state. Printing first and then making the recursive call sends values forward in output order. If the call happened before printing, the deepest call would print first and the output would arrive backwards unless you added another mechanism to delay the values.

if (__________) {
    return;
}

One recursive call per printed term makes the running time linear

Let T(r) be the time for a state with r remaining terms. For a positive r, the function prints one value, adds two integers, and makes one call with r - 1. That gives the recurrence T(r) = T(r - 1) + O(1), with T(0) = O(1). Expanding the recurrence gives one constant amount of work for each remaining value, so T(N) = O(N).

For N = 7, the active call chain contains the seven printing calls and the final base-case call, for a maximum of eight active calls. In general, the chain has N + 1 active calls, so the auxiliary space used by the call stack is O(N). The single-call structure is why the function avoids the repeated work that would arise from separately branching into earlier-term calculations.

T(r) = T(r - 1) + O(1)
T(0) = O(1)

For N = 7:
(7, 0, 1)
(6, 1, 1)
(5, 1, 2)
(4, 2, 3)
(3, 3, 5)
(2, 5, 8)
(1, 8, 13)
(0, 13, 21)

Time: O(N)
Auxiliary stack space: O(N)