Professor Java # Fibonacci Term Calculator

N=

Nth Fibonacci Number:

## Fibonacci

public static int fibonacci(int num){ //non-recursive fibonacci. returns the nth fibonacci number.
double phi= (1+Math.sqrt(5))/2;
return((int)((Math.pow(phi,num)-Math.pow(1-phi,num))/Math.sqrt(5))); //finding fibonnaci number using formula.
}
public static int fibonacciRec(int num){ //recurive fibonacci. Used to demonstrate fibonacci
if(num==1||num==2){ //stopping case. F(1)=1, F(2)=1 by definition.
return(1);
}
return(fibonacciRec(num-1)+fibonacciRec(num-2)); //definition of Fibonacci sequence: F(n)=F(n-1)+F(n-2)
}

More short code. Fairly useful, two methods used to find the nth term of the Fibonacci sequence, defined when F(1)=1, F(2)=1, and
F(N)=F(N-1)-F(N-2). The first program is short and utilizes the closed-form expression of the Fibonacci sequence, popularly known as Binet's formula.

This gives a very effective computer algorithm to find the nth Fibonacci term, because the speed of this algorithm is O(1) for all cases.
The second algorithm is the recursive way to find Fibonacci numbers, based on its definition. For example, with F(5), it returns
F(4)+F(3)=(F(3)+F(2))+(F(2)+F(1))=(F(2)+F(1)+1)+1+1=1+1+1+1+1=5. As you can see, this method is very slow, when num even gets slightly larger, and should NEVER be implemented. The first method given should ALWAYS be used as the running time is O(1), compared to the very slow recursive method.

Note that I did not use the other popular method for finding fibonacci numbers, which finds F(0) and F(1), stores these two values, finds F(2), replaces F(0) with F(2), and so on until reaching your desired number. I didn't find it useful as the algorithm is not particularly elegant and is also slower than the Binet implementaion, with speed O(1) while this method requires at least O(N). Javascript implementation above, not that it is done with the Binet implementaion. Provided by website-hit-counters.com site. 