Fibonacci

The sequenceFnof Fibonacci numbers is defined by therecurrence relation:

{\displaystyle F_{n}=F_{n-1}+F_{n-2},}

withseed values[1][2]

{\displaystyle F_{1}=1,\;F_{2}=1}

or[5]

{\displaystyle F_{0}=0,\;F_{1}=1.}

Solution)

Iterative approach

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

Recursive approach

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

Tail recursion

public int fibt(int n, int a, int b) {
    if (n == 0) return a;
    if (n == 1) return b;
    return fibt(n, b, a+b);
}

public int fib(int n) {
    return fib(n, 0, 1);
}