| 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 OKIf 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 nsThe 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(n2), 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;
}
}
