The Fibonacci sequence begins with two initial values and each subsequent term equals the sum of the previous two. For this treatment, the sequence starts 1, 1, 2, 3, 5, 8, ....

Iterative Approach

An iterative method computes the desired term by updating two running values across a loop.

long iter_fib(int pos) {
    if (pos == 1 || pos == 2) return 1;
    int prev_prev = 1;
    int prev = 1;
    int current = 0;
    for (int step = 3; step <= pos; ++step) {
        current = prev_prev + prev;
        prev_prev = prev;
        prev = current;
    }
    return current;
}

Two seed values prev_prev and prev represent F(n-2) and F(n-1). In each iteration, their sum becomes the new current, then both track forward. After pos - 2 iterations, current holds F(pos).

Direct Recursion

A straightforward recursive formulation mirrors the mathematical definition directly.

int direct_recur_fib(int pos) {
    if (pos == 1 || pos == 2) return 1;
    return direct_recur_fib(pos - 1) + direct_recur_fib(pos - 2);
}

Base cases return 1 for positions 1 and 2. Otherwise, the function calls itself for the two preceding positions and adds results. This approach recomputes overlapping subproblems, leading to exponential call growth.

Tail Recursion

Tail recursion rewrites the computation sothat recursive calls are the final operation, enabling potential compiler optimization into iteration.

int tail_helper(int remaining, int prev_prev, int prev) {
    if (remaining == 1) return prev;
    return tail_helper(remaining - 1, prev, prev_prev + prev);
}

int tail_fib(int pos) {
    if (pos == 1 || pos == 2) return 1;
    return tail_helper(pos - 1, 1, 1);
}

The helper receives the count of steps left (remaining) and the last two computed terms. Each call reduces remaining by one and shifts the window forward: prev_prev becomes the old prev, and prev becomes their sum. When remaining reaches 1, prev is the target term.

Example for pos = 5:

• Initial: tail_helper(4, 1, 1)
• Step 1: tail_helper(3, 1, 2)
• Step 2: tail_helper(2, 2, 3)
• Step 3: tail_helper(1, 3, 5) → returns 5