Fibonacci Numbers

Definition

Fibonacci numbers are a sequence of numbers named after Leonardo of Pisa (Fibonacci comes from the contraction of filius Bonaccio, son of Bonaccio). This sequence was already studied before Leonardo(late 12th- early 13th Century), most notably by the Ancient Indians(not Native Americans) as early as 200 BCE. The first two numbers in the sequence are both 1. Each subsequent number is the sum of the two numbers proceeding it.

Sequence

The first fifteen fibonacci numbers are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610.

Uses

The Fibonacci sequence was used by Leonardo of Pisa as an example of an idealized rabbit colony, in which the number represented the number of pairs of rabbits in the colony, starting from the first month. This is biologically unrealistic, because it does not take into effect other conditions of the colony. The Fibonacci sequence also has a close relation to the Golden Ratio(approximately 1.618).

Recursive Code

public int fibonacci(int n) {
  if(n == 1 || n == 2){
    return 1;
  }
  else{
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

Iterative Code

public static int fib(int n) {
    int prev1 = 1,
        prev2 = 1,
        temp;
 
    for(int i = 0; i < n; i++) {
        temp = prev1;
        prev1 = prev2;
        prev2 += temp;
    }
    return prev1;
}

Recursive vs. Iterative

Although a very simple recursion code, the Fibonacci code recursively can be extremely slow, with a runtime of O(2n).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License