# Computing the Nth Fibonacci Number

suggest changeThe 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(2N), 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.

Found a mistake? Have a question or improvement idea?
Let me know.

Table Of Contents