Java Language Tutorial => Computing the Nth Fibonacci Number

Example

The following method computes the Nth Fibonacci number using recursion.

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

The method implements a base case (n <= 2) and a recursive case (n>2). This illustrates the use of recursion to compute a recursive relation.

However, while this example is illustrative, it is also inefficient: each single instance of the method will call the function itself twice, leading to an exponential growth in the number of times the function is called as N increases. The above function is O(2^N), but an equivalent iterative solution has complexity O(N). In addition, there is a "closed form" expression that can be evaluated in O(N) floating-point multiplications.

PDF - Download Java Language for free

Previous Next

Java Language

Fastest Entity Framework Extensions

Example

Got any Java Language Question?

Java Language

Java Language Recursion Computing the Nth Fibonacci Number

Fastest Entity Framework Extensions

Example

Got any Java Language Question?