Fibonacci numbers in Python and Java

Fibonacci numbers,  introduced by Leonardo Pisano Bigollo nearly a thousand years ago, were used to solve a fascinating puzzle about the growth of an idealised rabbit population. Below are the first 11 Fibonacci numbers F_n where n=0, 1, 2,..., 10:

sequence	F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10
number	0	1	1	2	3	5	8	13	21	34	55

or we can describe the Fibonacci numbers as

Fn = Fn-1 + Fn-2 (when n>=2)

To write a program to return a Fibonacci number given a sequence, there are many possible implementations. I shall present 2 solutions implemented in both Python and Java, where the first one is using recursion, and the second one is using a while loop, however, the performances of these 2 solutions are drastically different when the sequence is bigger.
Below are the results when running a Python test script. The recursion way is already showing very poor performance comparing to the while loop way.

> python test_fib.py 
.Working out Fibonacci(40)=102334155 recursively took 67.310534 seconds
.Working out Fibonacci(40)=102334155 with while loop took 1.8e-05 seconds
Working out Fibonacci(50)=12586269025 with while loop took 1.6e-05 seconds
Working out Fibonacci(60)=1548008755920 with while loop took 1.8e-05 seconds
..
----------------------------------------------------------------------
Ran 4 tests in 67.312s

OK

If we look at the results when running a similar timed test in Java, the same recursion is not as bad as in Python, though still far poorer than the while loop implementation.

> /somewhere/jdk1.6.0_33/bin/java -classpath ".:" fun.Fib
Working out Fibonacci(40)=102334155 recursively took 408 ms
Working out Fibonacci(40)=102334155 with while loop took 2033 ns
Working out Fibonacci(50)=12586269025 with while loop took 2115 ns
Working out Fibonacci(60)=1548008755920 with while loop took 2368 ns

The reason why recursion is slow in this case is because there are a lot of duplicated operations as the sequence grows. For example, to solve F(5), we need to solve F(4) once, F(3) twice, F(2) three times, and F(1) twice, as shown below

or the number of recursion required given a sequence n is

[1+(n-2)]*(n-2)/2 + (n-3) or n2/2-n/2-2  (when n>=4)

The complexity of using recursion is then actually O(n²), where, on the other hand, the while loop is O(n).
Below are the source code that are used in the test.
fib.py

import datetime


class Fib:
    def recursively(self, n):
        if n == 0:
            return 0
        elif n <= 2:
            return 1
        else:
            return self.recursively(n - 1) + self.recursively(n - 2)

    def whileLoop(self, n):
        if n == 0:
            return 0
        previous, fib, currentIndex = 0, 1, 1
        while currentIndex < n:
            previous, fib = fib, previous + fib
            currentIndex += 1

        return fib

    def timedRecursively(self, n):
        start = datetime.datetime.now()
        result = self.recursively(n)
        end = datetime.datetime.now()
        elapsed = end - start
        print "Working out Fibonacci({})={} recursively took {} seconds".format(str(n), str(result), str(elapsed.total_seconds()))
        return result

    def timedWhileLoop(self, n):
        start = datetime.datetime.now()
        result = self.whileLoop(n)
        end = datetime.datetime.now()
        elapsed = end - start
        print "Working out Fibonacci({})={} with while loop took {} seconds".format(str(n), str(result), str(elapsed.total_seconds()))
        return result

test_fib.py

import unittest
from fib import Fib


class TestFib(unittest.TestCase):
    def setUp(self):
        self.fib = Fib()

    def test_recursively(self):
        self.assertEqual(self.fib.recursively(0), 0)
        self.assertEqual(self.fib.recursively(1), 1)
        self.assertEqual(self.fib.recursively(2), 1)
        self.assertEqual(self.fib.recursively(3), 2)
        self.assertEqual(self.fib.recursively(4), 3)
        self.assertEqual(self.fib.recursively(5), 5)
        self.assertEqual(self.fib.recursively(6), 8)
        self.assertEqual(self.fib.recursively(7), 13)
        self.assertEqual(self.fib.recursively(8), 21)
        self.assertEqual(self.fib.recursively(9), 34)
        self.assertEqual(self.fib.recursively(10), 55)

    def test_whileLoop(self):
        self.assertEqual(self.fib.whileLoop(0), 0)
        self.assertEqual(self.fib.whileLoop(1), 1)
        self.assertEqual(self.fib.whileLoop(2), 1)
        self.assertEqual(self.fib.whileLoop(3), 2)
        self.assertEqual(self.fib.whileLoop(4), 3)
        self.assertEqual(self.fib.whileLoop(5), 5)
        self.assertEqual(self.fib.whileLoop(6), 8)
        self.assertEqual(self.fib.whileLoop(7), 13)
        self.assertEqual(self.fib.whileLoop(8), 21)
        self.assertEqual(self.fib.whileLoop(9), 34)
        self.assertEqual(self.fib.whileLoop(10), 55)

    def test_timedRecursively(self):
        self.assertEqual(self.fib.timedRecursively(40), 102334155)

    def test_timedWhileLoop(self):
        self.assertEqual(self.fib.timedWhileLoop(40), 102334155)
        self.assertEqual(self.fib.timedWhileLoop(50), 12586269025)
        self.assertEqual(self.fib.timedWhileLoop(60), 1548008755920)

unittest.main()

Fib.java

package fun;

public class Fib {


    public static void main(String[] args) {
        recursively(1);
        whileLoop(1);

        long start = System.nanoTime();

        long result = recursively(40);
        long elapsed = (System.nanoTime() - start) / 1000000;
        System.out.println(String.format("Working out Fibonacci(%s)=%s recursively took %s ms", 40, result, elapsed));

        start = System.nanoTime();
        result = whileLoop(40);
        elapsed = (System.nanoTime() - start);
        System.out.println(String.format("Working out Fibonacci(%s)=%s with while loop took %s ns", 40, result, elapsed));

        start = System.nanoTime();
        result = whileLoop(50);
        elapsed = (System.nanoTime() - start);
        System.out.println(String.format("Working out Fibonacci(%s)=%s with while loop took %s ns", 50, result, elapsed));

        start = System.nanoTime();
        result = whileLoop(60);
        elapsed = (System.nanoTime() - start);
        System.out.println(String.format("Working out Fibonacci(%s)=%s with while loop took %s ns", 60, result, elapsed));
    }

    static long recursively(long i) {
        if (i == 0) return 0;
        if (i <= 2) return 1;
        else return recursively(i - 1) + recursively(i - 2);
    }

    static long whileLoop(long i) {
        long previous = 0, fib = 1, currentIndex = 1;
        while (currentIndex < i) {
            long newFib = previous + fib;
            previous = fib;
            fib = newFib;
            currentIndex++;
        }
        return fib;
    }
}