Print n-th Term of Fibonacci Series in C, C++, and Java

The n-th Fibonacci number can be returned in O(n) time using just two variables and a counted loop, and that is the answer interviewers expect for this question.

The sections below give the full code in C, C++, and Java for four methods: the iterative loop, textbook recursion, dynamic programming, and matrix exponentiation. A short note on integer type is included too. Fibonacci grows fast enough that the type matters before the algorithm does.

The n-th term, defined precisely

The Fibonacci sequence is defined by the recurrence F(n) = F(n-1) + F(n-2) with the two base cases F(0) = 0 and F(1) = 1. Full background lives at the Wikipedia entry on Fibonacci numbers; the sequence is indexed as OEIS A000045.

Using the 0-indexed convention throughout this article:

• 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
• F(10) = 55

A small but persistent source of confusion: some textbooks 1-index the sequence so that F(1) = 0, F(2) = 1, F(3) = 1, and so on. The arithmetic is identical; every label shifts by one. Pick a convention, state it, and stick to it for the whole interview answer. This article uses 0-indexed.

The “n-th Fibonacci number” problem returns one value: F(n). It is distinct from the related question that prints every term whose value is at most n, which is covered in print every term up to a value limit. Confusing the two costs marks in coding rounds.

Iterative method: O(n) time, O(1) space

Two variables hold the previous two terms. On each iteration, sum them, shift the pair forward, and repeat until you reach the n-th term. No array, no recursion, no stack risk for large n.

Trace for n = 10:

• Start: a = 0, b = 1
• i = 2: c = 1, a = 1, b = 1
• i = 3: c = 2, a = 1, b = 2
• i = 4: c = 3, a = 2, b = 3
• i = 5: c = 5, a = 3, b = 5
• i = 6: c = 8, a = 5, b = 8
• i = 7: c = 13, a = 8, b = 13
• i = 8: c = 21, a = 13, b = 21
• i = 9: c = 34, a = 21, b = 34
• i = 10: c = 55, return 55

C

#include <stdio.h>

long long nth_fib(int n) {
    if (n < 2) return n;
    long long a = 0, b = 1, c = 0;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);
    printf("F(%d) = %lld\n", n, nth_fib(n));
    return 0;
}

C++

#include <iostream>
using namespace std;

long long nth_fib(int n) {
    if (n < 2) return n;
    long long a = 0, b = 1, c = 0;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

int main() {
    int n;
    cout << "Enter n: ";
    cin >> n;
    cout << "F(" << n << ") = " << nth_fib(n) << endl;
    return 0;
}

Java

import java.util.Scanner;

public class FibonacciNth {
    static long nthFib(int n) {
        if (n < 2) return n;
        long a = 0, b = 1, c = 0;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n: ");
        int n = sc.nextInt();
        System.out.println("F(" + n + ") = " + nthFib(n));
    }
}

The base case n < 2 returns n directly so the function handles F(0) = 0 and F(1) = 1 without a special branch.

Recursive method: O(2^n) and the call-tree problem

The textbook recursion follows the mathematical recurrence directly. The base cases are F(0) = 0 and F(1) = 1; for any larger k, return fib(k-1) + fib(k-2).

It is elegant and it is slow. Every call spawns two more calls, and those each spawn two more. The total call count grows roughly as 2 to the power n. Computing fib(30) is fine; fib(40) takes a few seconds on a laptop; fib(50) is impractical.

The reason interviewers still ask for it is the follow-up. Once you have written the recursive version, the next question is almost always “now optimise it”, which is where memoization (covered below) comes in. The pair tests both your ability to translate math into code and your ability to spot redundant computation.

C

#include <stdio.h>

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

int main() {
    int n;
    scanf("%d", &n);
    printf("F(%d) = %lld\n", n, fib(n));
    return 0;
}

C++

#include <iostream>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    cout << "F(" << n << ") = " << fib(n) << endl;
    return 0;
}

Java

import java.util.Scanner;

public class FibonacciRecursive {
    static long fib(int n) {
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println("F(" + n + ") = " + fib(n));
    }
}

Cost in concrete numbers, computed from the recurrence T(n) = T(n-1) + T(n-2) + 1 with T(0) = T(1) = 1:

• Naive recursive fib(40): 331,160,281 function calls.
• Iterative loop for F(40): 39 additions.
• Memoized recursion for F(40): 39 effective calls (the rest are cache hits).

The dynamic-programming version below brings the recursive structure back to linear cost without losing the recursive form.

Dynamic programming: memoization and tabulation

Memoization is top-down DP. Keep a cache. The first time fib(k) is called, compute it normally and store the result; the next time, return the cached value. The recursive structure stays intact; the work drops from O(2^n) to O(n).

Tabulation is bottom-up DP. Build an array fib[0..n] from F(0) upward, each cell being the sum of the previous two. The same O(n) work, no recursion, but using O(n) extra space for the array. The iterative method shown earlier is tabulation with the array compressed down to two variables.

Memoization in C

#include <stdio.h>
#include <string.h>
#define MAXN 100

long long memo[MAXN];

long long fib_memo(int n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

int main() {
    int n;
    memset(memo, -1, sizeof(memo));
    scanf("%d", &n);
    printf("F(%d) = %lld\n", n, fib_memo(n));
    return 0;
}

Memoization in C++

#include <iostream>
#include <vector>
using namespace std;

vector<long long> memo(100, -1);

long long fib_memo(int n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

int main() {
    int n;
    cin >> n;
    cout << "F(" << n << ") = " << fib_memo(n) << endl;
    return 0;
}

Tabulation in Java

import java.util.Scanner;

public class FibonacciDP {
    static long fib_tab(int n) {
        if (n < 2) return n;
        long[] table = new long[n + 1];
        table[0] = 0;
        table[1] = 1;
        for (int i = 2; i <= n; i++) {
            table[i] = table[i - 1] + table[i - 2];
        }
        return table[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println("F(" + n + ") = " + fib_tab(n));
    }
}

In an interview, naming the technique matters more than the code. “I’ll memoize the recursion to avoid recomputing the same sub-problems” earns the same credit as the iterative loop and shows you can recognise overlapping sub-problems, which is the headline pattern of dynamic programming.

Matrix exponentiation: O(log n) for very large n

The Fibonacci recurrence can be written as a matrix multiplication:

| F(n+1) |   | 1  1 |^n   | 1 |
|        | = |      |   * |   |
| F(n)   |   | 1  0 |     | 0 |

Raising the 2x2 matrix to the n-th power gives F(n) directly. Matrix exponentiation by squaring runs in O(log n) multiplications, so even F(10^9) is computable in microseconds (assuming the result is taken modulo some prime, since the actual value has hundreds of millions of digits).

This is the right tool when n is huge. It is also a competitive-programming staple. For service-tier placement tests, the iterative loop is enough. For product-tier and ICPC-style rounds, knowing the matrix form is worth the practice.

C++ sketch

#include <iostream>
using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

void multiply(ll F[2][2], ll M[2][2]) {
    ll x = (F[0][0]*M[0][0] + F[0][1]*M[1][0]) % MOD;
    ll y = (F[0][0]*M[0][1] + F[0][1]*M[1][1]) % MOD;
    ll z = (F[1][0]*M[0][0] + F[1][1]*M[1][0]) % MOD;
    ll w = (F[1][0]*M[0][1] + F[1][1]*M[1][1]) % MOD;
    F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w;
}

void matpow(ll F[2][2], int n) {
    if (n == 0 || n == 1) return;
    ll M[2][2] = {{1,1},{1,0}};
    matpow(F, n / 2);
    multiply(F, F);
    if (n % 2 != 0) multiply(F, M);
}

ll nth_fib(int n) {
    if (n == 0) return 0;
    ll F[2][2] = {{1,1},{1,0}};
    matpow(F, n - 1);
    return F[0][0];
}

int main() {
    int n;
    cin >> n;
    cout << "F(" << n << ") mod 10^9+7 = " << nth_fib(n) << endl;
    return 0;
}

The modulo operation is included because for n above roughly 90 the actual value no longer fits in a long long. Most competitive-programming judges ask for the answer modulo 10^9 + 7 for this reason.

Pick the data type before you pick the algorithm

Fibonacci grows fast. Faster than a 32-bit int can hold for surprisingly small n. Run the iterative loop on the wrong type and the answer silently wraps around, returning a negative number or wrong positive without any error.

Concrete overflow points, both 0-indexed:

• int (32-bit signed, max 2,147,483,647): F(46) = 1,836,311,903 fits; F(47) = 2,971,215,073 overflows.
• long long (64-bit signed, max 9,223,372,036,854,775,807): F(92) = 7,540,113,804,746,346,429 fits; F(93) overflows.
• For F(n) where n exceeds 92 and you need the exact value, use Java BigInteger, Python’s native int (arbitrary precision), or C++ __int128 / a big-int library.

The C and C++ examples above use long long. The Java examples use long, which is also 64-bit. If the interviewer asks for F(100), say “BigInteger” out loud before you start typing.

Comparing the four methods

Method	Time complexity	Space complexity	When to use
Iterative loop	O(n)	O(1)	Default. Service-tier interviews, production code, any memory constraint.
Plain recursion	O(2^n)	O(n) call stack	Only as the first step before the “now optimise” follow-up.
Memoization (top-down DP)	O(n)	O(n)	When the recursive form is required by the question.
Tabulation (bottom-up DP)	O(n)	O(n), or O(1) compressed	Same as iterative when compressed; full table when you need every prior term.
Matrix exponentiation	O(log n)	O(1)	n above 10^6, competitive programming, product-tier rounds.

For the typical engineering placement test (TCS NQT, Infosys SP, Cognizant GenC), the iterative loop is the expected answer. Walking through it without a syntax error in the language of your choice is what scores marks.

For broader interview prep, the iteration pattern in this article generalises to other classic single-function multi-language problems: see find the smallest and largest element in an array and check whether a string is a palindrome or not for the same template applied to different problems. The full DSA-interview list is at 20 most asked data structures interview questions.

The memoization step above is dynamic programming in miniature: solve each sub-problem once, cache it, never recompute. The same caching idea sits at the core of how a language model reuses key-value attention state across tokens during inference, the difference between answering in 200 ms and 2 seconds. If you want to see DP-style caching in a working LLM context, TinkerLLM lets you run prompts in a ₹299 sandbox and watch how the model handles repeated patterns. The 0-to-F(40) leap from 331 million calls to 39 is small. The same compression at scale is what makes a chatbot feel instant.