PD4CS

The Fibonacci sequence  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, … is an infinite sequence defined recursively by

• Base cases: f(0)=0 and f(1)=1
• f(n) = f(n-1) + f(n-2) for n>1

The following program contains three functions for computing the n-th Fibonacci number.

• The recursive function calcFibRecur(n) uses the recursive definition and it re-computes previously computed values.
• Function calcFib(n) consists of a for loop and computes the next value by always remembering the previous two values.
• ImprovedFibRecur(n) is a recursive function which stores previously computied values  in a dictionary. If the value needed is in the dictionary, no call is made.

## Fibonacci.py
## Fibonacci numbers
## f(n) = f(n-1) + f(n-2), f(0)= 0 and f(1) = 1
## 0,1,1,2,3,5,8,13,21,34,55,89, ...

from __future__ import print_function
from timeit import Timer

##non-recursive version
def calcFib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else: #if n is greater than 1
        an_0 = 0 #term 0
        an_1 = 1 #term 1
        for i in range(1,n):
            temp = an_0
            an_0 = an_1
            an_1 = temp + an_1 #f(n) = f(n-1) + f(n-2)
        return an_1

##recursive version with recomutation
def calcFibRecur(n):
    if n == 0: #base case f(0)=0
        return 0
    elif n == 1: #base case f(1)=1
        return 1
    else: #if n is greater than 1, f(n) = f(n-1) + f(n-2)
        return calcFibRecur(n-1) + calcFibRecur(n-2)

##recursive version with no computation
##create a dictionary memo to keep all the returns in the recursion.
memo = {0:0, 1:1} ##the first two items in the dictionary are the base cases
def improvedFibRecur(n):
    if not n in memo:
        memo[n] = improvedFibRecur(n-1) + improvedFibRecur(n-2)
    return memo[n]

##compare the performance of function calcFib() and calcFibRecur()
##the unit of time is second
##each function will be executed by 3 times
##you can change the variable execute_times to set executed times for each function
execute_times = 3

print("{:<5} | {:<14} | {:<10} |  {:<10}".format("N", "calcFibRecur()", "calcFib()", "Percent"))
for i in range(30):
    #time the recursion version
    stmt = "calcFibRecur(" + str(i) +")"
    t1 = Timer(stmt,"from __main__ import calcFibRecur")
    time1 = t1.timeit(execute_times)

    #time the non-recursion version
    stmt = "calcFib(" + str(i) +")"
    t2 = Timer(stmt,"from __main__ import calcFib")
    time2 = t2.timeit(execute_times)

    print("n={:2}  |  {:7f}      |  {:7f}  |  {:7f}".format(i, time1, time2, time1/time2))

print()

##compare the performance of function calcFib() and improvedFibRecur()
print("{:<5} | {:<14} | {:<10} |  {:<10}".format("N", "improvedFibRecur()", "calcFib()", "Percent"))
for i in range(30):
    #time the recursion version
    stmt = "improvedFibRecur(" + str(i) +")"
    t1 = Timer(stmt,"from __main__ import improvedFibRecur")
    time1 = t1.timeit(execute_times)

    #time the non-recursion version
    stmt = "calcFib(" + str(i) +")"
    t2 = Timer(stmt,"from __main__ import calcFib")
    time2 = t2.timeit(execute_times)

    print("n={:2}  |  {:7f}          |  {:7f}  |  {:7f}".format(i, time1, time2, time1/time2))

The program contains code for running the three functions and recording times (in seconds). It is interesting to take a careful look at the running times:

• Function calcFibRecur(n) is by far the slowest.  Looking at its running times, one sees that the time needed to compute f(n+1)  is roughly double that needed for computing f(n). This doubling results in a very fast growth and thus a slow function.  Try computing f(50)!
• The other two functions are fast, with ImprovedFibRecur(n) being slightly faster. It is more common in simple problems for an iterative version to be faster than the recursive one. The main reason ImprovedFibRecur(n) is faster lies in the fact that dictionaries in Python have a fast implementation.