Fibonacci Series in C and C++: Loops, Recursion, Memoization and Limits

Computing F(40) with the textbook recursive function makes 331,160,281 function calls. Computing it with a loop makes 40 additions. Both print 102334155, and on the machine used for this article one took 0.28 seconds and the other 28 nanoseconds — a difference of roughly ten million times, from code that looks equally reasonable on the page.

This guide covers the four ways to generate the Fibonacci series in C and C++ — iterative, recursive, memoized and matrix exponentiation — what each one actually costs when you count the operations rather than reason about them, and a limit that usually goes unexplained: the exact term at which each integer type stops telling the truth. Every program below was compiled and run for this article on Ubuntu 24.04 with GCC 13.3, using gcc -std=c11 -Wall -Wextra and g++ -std=c++17 -Wall -Wextra with zero warnings, plus a run under -fsanitize=signed-integer-overflow. Call counts and overflow boundaries come from instrumented runs checked against arbitrary-precision reference values, and every output block is captured verbatim.

Table of Contents

• The Short Answer
• What Is the Fibonacci Series?
• The Iterative Method: What You Should Actually Use
• The Recursive Method and What It Actually Costs
• Memoization: The One-Line Fix
• Matrix Exponentiation: O(log n)
• How Far Can You Count? Integer Overflow by Type
• Binet's Formula, and Why It Fails Earlier Than You Would Guess
• Fibonacci in C++
• Comparing the Four Methods
• Key Takeaways
• Frequently Asked Questions
• Conclusion

The Short Answer

How do I generate the Fibonacci series in C? Use a loop with two running variables. It is O(n), needs no array, and is the default choice for generating the sequence or computing ordinary-sized values.

Is the recursive version wrong? Not incorrect, just exponentially expensive — it recomputes the same subproblems. It is worth writing once to understand recursion, then replacing.

How far can I go before the numbers break? With unsigned long long (64-bit), F(93) is the last exact value. With a 32-bit int — which is what long is on Windows — you break at F(47), far earlier than most introductory examples account for.

What Is the Fibonacci Series?

The Fibonacci series is a sequence of numbers where each term is the sum of the two before it, starting from 0 and 1: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. Formally, F(0) = 0, F(1) = 1, and F(n) = F(n−1) + F(n−2) for n ≥ 2. It is named after Leonardo of Pisa, known as Fibonacci, who used it in 1202 to model rabbit population growth, though the sequence appears in Indian mathematics several centuries earlier.

The sequence is catalogued as A000045 in the On-Line Encyclopedia of Integer Sequences, and Fibonacci himself introduced it to European mathematics in Liber Abaci.

One detail causes more confusion than any other: where the sequence starts. The modern convention begins at F(0) = 0. Many older programming tutorials begin at 1, 1, 2, 3 — which is the same sequence shifted by one position. Neither is wrong, but mixing them is: if your loop prints 1, 1, 2, 3 while your explanation says the series starts at 0, your tenth term is somebody else’s eleventh. Every example in this article uses F(0) = 0 and says so explicitly.

The Iterative Method: What You Should Actually Use

Two variables, one loop, no array. Each step overwrites the older of the two values.

#include <stdio.h>

/* Prints the first n Fibonacci numbers, F(0) through F(n-1).
   unsigned long long is at least 64 bits, so this is exact up to F(93). */
int main(void) {
    int n;

    printf("How many Fibonacci numbers? (0-94): ");
    if (scanf("%d", &n) != 1) {          /* a failed scanf leaves n indeterminate */
        printf("That was not a number.\n");
        return 1;
    }
    if (n < 0 || n > 94) {
        printf("Please enter a value between 0 and 94.\n");
        return 1;
    }

    unsigned long long prev = 0, curr = 1;
    for (int i = 0; i < n; i++) {
        printf("F(%d) = %llu\n", i, prev);
        unsigned long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return 0;
}

Output (input 10):

How many Fibonacci numbers? (0-94): F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34

Three details are doing real work here. The scanf return value is checked — scanf returns the number of items successfully converted, and if it returns 0 then n was never written to, so reading it is undefined behaviour. Most Fibonacci tutorials skip this. The type is unsigned long long, which the C standard guarantees is at least 64 bits, giving the widest exact range available without extensions. The loop prints prev before advancing, which is what makes the first printed value F(0) = 0 rather than F(1) = 1.

The Recursive Method and What It Actually Costs

The recursive definition transcribes the mathematics directly, which is exactly why it is taught — and exactly why it is slow.

unsigned long long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

The problem is not the recursion. It is that nothing remembers anything. Computing fib(5) computes fib(3) twice, fib(2) three times and fib(1) five times, because the two branches never learn from each other.

Adding a counter to the function turns that intuition into a number:

static unsigned long long calls = 0;

unsigned long long fib(int n) {
    calls++;
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

Output:

  n   F(n)          calls made
----------------------------------
  5   5             15
 10   55            177
 15   610           1973
 20   6765          21891
 25   75025         242785
 30   832040        2692537
 35   9227465       29860703
 40   102334155     331160281

Those call counts are not arbitrary. The number of calls needed to compute F(n) is exactly 2·F(n+1) − 1, which holds for every row in the table above. For F(40): 2 × 165,580,141 − 1 = 331,160,281, matching the measured count precisely.

That identity is the whole problem in one line. The cost of computing a Fibonacci number recursively is itself a Fibonacci number — the work grows at the same rate as the answer. Every term you add multiplies the effort by roughly 1.618. That growth rate is Θ(φⁿ), where φ ≈ 1.618. Introductory courses usually simplify it to O(2ⁿ), which is a correct upper bound and a looser one. Counting operations rather than reasoning about them is the same discipline our quicksort walkthrough uses to expose its own worst case.

Memoization: The One-Line Fix

Store each result the first time you compute it, and return the stored value afterwards.

#include <stdio.h>
#include <string.h>

#define MAXN 94
static unsigned long long memo[MAXN + 1];
static int    known[MAXN + 1];
static unsigned long long calls = 0;

unsigned long long fib_memo(int n) {
    calls++;
    if (n < 2) return n;
    if (known[n]) return memo[n];       /* already computed: return, do not recurse */
    known[n] = 1;
    return memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
}

Output:

  n   F(n)                  calls made
------------------------------------------
 10   55                    19
 30   832040                59
 50   12586269025           99
 70   190392490709135       139
 90   2880067194370816120   179

The call count is now 2n − 1 — linear, not exponential. At n = 40 that is 79 calls against 331,160,281, a reduction of 4,191,902 times for one array and one branch.

Memoization is the entry point to dynamic programming, and the same technique drives our longest common subsequence implementation.

Note the separate known[] array rather than testing memo[n] != 0. F(0) is legitimately 0, so a zero value cannot distinguish “not yet computed” from “computed and the answer is zero” — a small bug that hides easily because it only misfires at the base case.

Matrix Exponentiation: O(log n)

Memoization gets you to linear. Getting below linear needs a different idea. The recurrence can be written as a matrix:

[F(n+1)  F(n) ]     [1  1]^n
[F(n)   F(n-1)]  =  [1  0]

Raising a matrix to the nth power by repeated squaring costs O(log n) multiplications rather than n additions.

typedef struct { unsigned long long a, b, c, d; } Mat2;

static Mat2 mat_mul(Mat2 x, Mat2 y) {
    Mat2 r;
    r.a = x.a * y.a + x.b * y.c;
    r.b = x.a * y.b + x.b * y.d;
    r.c = x.c * y.a + x.d * y.c;
    r.d = x.c * y.b + x.d * y.d;
    return r;
}

unsigned long long fib_matrix(int n) {
    if (n == 0) return 0;
    Mat2 result = {1, 0, 0, 1};          /* identity */
    Mat2 base   = {1, 1, 1, 0};
    int e = n;
    while (e > 0) {
        if (e & 1) result = mat_mul(result, base);
        base = mat_mul(base, base);
        e >>= 1;
    }
    return result.b;                      /* F(n) */
}

Output (multiplications counted by instrumenting mat_mul):

  n   F(n)                  matrix multiplications
---------------------------------------------------
 10   55                    6
 30   832040                9
 50   12586269025           9
 70   190392490709135       10
 90   2880067194370816120   11

F(90) sits nine times farther along the sequence than F(10) and needs only five more matrix multiplications — eleven in total. Be honest about when this matters, though: on the machine tested and within the range a 64-bit integer can hold, the iterative loop is already fast enough that the O(log n) version offered no practical advantage. Matrix exponentiation earns its keep when n is large and you are working modulo something — competitive programming problems asking for F(10^18) mod 10^9+7, for instance — not when you are printing the first fifty terms.

How Far Can You Count? Integer Overflow by Type

This is the part most often left out, and it is the one that produces wrong answers silently.

Fibonacci numbers grow by a factor of roughly 1.618 each step, so they exhaust an integer type quickly. The C standard specifies only minimum widths for each type — the arithmetic types reference gives the guarantees — so the exact boundary depends on your platform. Every figure below was computed in arbitrary precision and cross-checked against the C programs:

For the rest of C’s numeric surface, our math.h function reference covers the library side.

long is the trap. On Linux and macOS long is 64 bits, so a program using it reaches F(92). On Windows long is 32 bits, so the same source code breaks at F(47). The C standard fixes only minimum widths; the actual width follows the platform’s data model. The code does not change. The platform does.

Here is what that failure looks like. This models the 32-bit case and runs under GCC’s signed-overflow sanitizer:

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main(void) {
    int32_t current = 1, next = 1, twoaway;
    for (int i = 1; i <= 50; i++) {
        printf("%2d  %" PRId32 "\n", i, current);
        twoaway = current + next;   /* signed overflow when computing F(47) */
        current = next;
        next = twoaway;
    }
    return 0;
}

Compiled with gcc -std=c11 -Wall -Wextra -fsanitize=signed-integer-overflow, the sanitizer reports the exact moment it goes wrong:

overflow_demo.c:11:17: runtime error: signed integer overflow: 1134903170 + 1836311903 cannot be represented in type 'int'

And the printed values from term 47 onward:

46  1836311903
47  -1323752223
48  512559680
49  -811192543
50  -298632863

Term 47 should be 2,971,215,073. It prints −1,323,752,223 — which is exactly 2,971,215,073 − 2³², the two’s-complement wraparound. Without the sanitizer there is no error, no warning and no crash. The program runs to completion and prints negative Fibonacci numbers. Those particular values come from two’s-complement wraparound in this build — but because signed overflow is undefined behaviour, the exact output is not something to rely on. A different compiler, target or optimisation level may produce something else.

Signed integer overflow is undefined behaviour in both C and C++, so the compiler is entitled to assume it never happens. Unsigned overflow is defined to wrap, which is why unsigned long long is the better choice here even though it only buys you one extra term over long long.

Binet’s Formula, and Why It Fails Earlier Than You Would Guess

There is a closed form. F(n) can be computed directly, with no loop and no recursion:

F(n) = (φⁿ − ψⁿ) / √5, where φ = (1 + √5) / 2 and ψ = (1 − √5) / 2

In exact arithmetic this is precise. In double precision it is not, and the interesting question is exactly when it stops being right.

#include <stdio.h>
#include <math.h>

unsigned long long fib_binet(int n) {
    const double sqrt5 = sqrt(5.0);
    const double phi   = (1.0 + sqrt5) / 2.0;
    const double psi   = (1.0 - sqrt5) / 2.0;
    return (unsigned long long)llround((pow(phi, n) - pow(psi, n)) / sqrt5);
}

The obvious prediction is that it fails once F(n) exceeds 2⁵³ = 9,007,199,254,740,992, the largest integer a double represents exactly. That would be F(79).

The measurement disagrees. Comparing Binet’s formula against exact integer arithmetic for every n up to 93:

First n where Binet disagrees with exact integer arithmetic: 71

  n   exact                 Binet (double)        difference
--------------------------------------------------------------
 69   117669030460994       117669030460994       +0
 70   190392490709135       190392490709135       +0
 71   308061521170129       308061521170130       +1
 72   498454011879264       498454011879265       +1
 73   806515533049393       806515533049395       +2
 74   1304969544928657      1304969544928660      +3

This implementation first disagreed with exact integer arithmetic at n = 71 — eight indices earlier than the magnitude argument predicts, and at a value roughly thirty times smaller than 2⁵³. That boundary held across -O0 through -O3, under -ffast-math, and under g++ on the same machine, so it is not an optimisation artifact. It is a property of the precision used: recompiling the same source with long double moved the first disagreement to n = 90.

The dominant source is not representing the result — it is φ itself. φ is irrational and gets rounded to 53 bits, giving a relative error near 1.1 × 10⁻¹⁶. Raising it to the 71st power compounds that error about 71-fold, to roughly 7.9 × 10⁻¹⁵. Multiplied by F(71) ≈ 3.08 × 10¹⁴, that predicts an absolute error around 2.4 — and the measured error is 1, the same order of magnitude. The full error also depends on how sqrt, pow, the subtraction and the rounding are each evaluated, so treat this as the leading term rather than the whole story.

Binet’s formula is elegant and useful for estimating magnitude or deriving properties. It is not a way to compute exact Fibonacci numbers in floating point, and the point at which it quietly stops being exact is well inside the range people actually use.

Fibonacci in C++

The C code above compiles as C++ unchanged, but C++ adds something the C11 build cannot do: evaluating the calculation during compilation, so the Fibonacci work itself costs nothing at run time. C23 introduced constexpr too, but only for objects — C still has no constexpr functions, so a loop like the one below remains C++ only.

#include <array>
#include <cstdint>
#include <iostream>

// constexpr: the compiler evaluates this during compilation when the
// argument is a constant expression, so the calculation costs nothing at run time.
constexpr std::uint64_t fib_ct(int n) {
    std::uint64_t prev = 0, curr = 1;
    for (int i = 0; i < n; ++i) {
        std::uint64_t next = prev + curr;
        prev = curr;
        curr = next;
    }
    return prev;
}

// Proven at compile time. If these were wrong the program would not build.
static_assert(fib_ct(10) == 55ULL);
static_assert(fib_ct(50) == 12586269025ULL);
static_assert(fib_ct(93) == 12200160415121876738ULL);

int main() {
    constexpr std::array<std::uint64_t, 11> table = [] {
        std::array<std::uint64_t, 11> t{};
        for (int i = 0; i < 11; ++i) t[i] = fib_ct(i);
        return t;
    }();

    for (std::uint64_t v : table) std::cout << v << ' ';
    std::cout << '\n';
    return 0;
}

Output:

0 1 1 2 3 5 8 13 21 34 55

Two pieces of evidence that this really happens at compile time rather than at run time. First, deliberately breaking one of the assertions makes the compiler print the value it computed:

constexpr_proof.cpp:7:26: error: static assertion failed
    7 | static_assert(fib_ct(93) == 12200160415121876739ULL);  // deliberately off by one
      |               ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
constexpr_proof.cpp:7:26: note: the comparison reduces to '(12200160415121876738 == 12200160415121876739)'

Second, the generated assembly for a function returning fib_ct(93), compiled with -O2, contains no loop at all:

_Z3getv:
	movabsq	$-6246583658587674878, %rax

That constant is F(93) reinterpreted as a signed 64-bit value. The entire loop collapsed into a single instruction loading a number the compiler had already worked out.

For values beyond F(93), GCC and Clang offer __int128, which reaches F(184). It is a compiler extension rather than standard C++ — MSVC has no equivalent — and it has no printf support or stream operator, so printing it requires a manual digit loop.

Comparing the Four Methods

Fibonacci is one of the standard set worth knowing properly — see top 10 algorithms every programmer should know for the neighbours.

These four trace the progression from direct recurrence to dynamic programming to logarithmic time; they are not the complete set. Fast doubling reaches the same O(log n) using Fibonacci-specific identities instead of a matrix, with fewer multiplications and no matrix type to carry around — it is the usual choice in competitive programming.

Measured wall-clock time for F(40) on the machine described in the introduction, comparing the two extremes: naive recursion took 0.2819 seconds; the iterative loop took 28 nanoseconds as a mean over 10,000,000 repetitions. Both produced 102334155. That ratio, about ten million, is broadly consistent with the difference in operation counts, which is a useful cross-check on the measurement rather than a confirmation of it.

These figures come from a single-core container, timed with clock_gettime(CLOCK_MONOTONIC), reporting a mean with no median, percentile or standard deviation captured, and with n supplied at runtime so the optimizer could not fold the calls away. The operation counts in the table are exact and machine-independent; the timings are not, and would differ on your hardware. At this scale the absolute figure should be read as a property of this environment rather than a portable statement of how long one Fibonacci calculation takes.

Key Takeaways

• Use the iterative loop. Two variables, O(n) time, O(1) space. It is the right default for generating the sequence and for ordinary-sized values; very large n and modular arithmetic are where the other methods earn their place.
• Naive recursion costs 2·F(n+1) − 1 calls — a measured identity, exact for every value tested. Computing F(40) takes 331,160,281 calls to produce a nine-digit answer.
• Memoization reduces that to 2n − 1 calls, from 331 million to 79 at n = 40, using one array and one branch.
• unsigned long long reaches F(93) and no further. A 32-bit int — which is what long is on Windows — breaks at F(47), and does so silently.
• Signed overflow produces no warning and no crash, just negative Fibonacci numbers. -fsanitize=signed-integer-overflow is what makes it visible.
• In this implementation Binet’s formula first disagreed at n = 71, eight indices earlier than the 2⁵³ argument predicts, because the dominant rounding error is in φⁿ rather than in the result. Compiled with long double, the first disagreement moved to n = 90.
• C++ constexpr moves the whole computation to compile time. In the GCC 13.3 x86-64 build tested, the loop reduced to a single movabsq instruction — the language guarantees constant evaluation, not any particular instruction.

Frequently Asked Questions

Conclusion

Fibonacci is the first algorithm most programmers meet twice — once as a loop, and later as the example that explains why exponential complexity is not an abstraction. What makes it worth returning to is that both lessons are measurable in a few lines of instrumented C. The call counts are not estimates or asymptotic hand-waving; they are exact, reproducible, and they match a closed form you can check on paper.

The overflow boundary is the part that transfers furthest. Every fixed-width integer type has a point where it stops representing reality, and Fibonacci reaches that point quickly enough to see it in a short program — F(47) on a 32-bit type, F(93) on a 64-bit one, with nothing in the output to announce it. That is a habit worth carrying into code where the numbers matter more: know the range of your type, and know what your platform actually means by long. Our algorithms section covers the neighbouring ground.