# fibonaci algorithm, using recursion and using dynamic programming.
# A global 'count' shows amount of recursive calls.
# Usage: python fib.py <n>
# NvdM, 2010

# Compare 3 implementations w.r.t. runtime and max value of n

import sys

def fib (n):
    global count
    count = count + 1
    if n == 0 or n == 1: return n
    else: return (fib (n-1) + fib (n-2))

f = {0: 0, 1: 1}
def dynfib (n):
    global count
    count = count + 1
    if n not in f: f[n] = dynfib (n-1) + dynfib (n-2)
    # print f # uncomment this line to show evolution of map.
    return f[n]

def bot_up (n):
    if n == 0 or n == 1: return n
    prev, fib = 0, 1
    for i in range (2, n+1):
        prev, fib = fib, prev + fib
    return fib

def main ():
    global count
    count=0
    n = eval(sys.argv[1])
    print "  dynamic algorithm, fib (%d) = %10d, %12d calls" % \
        (n, dynfib (n), count)
    count=0
    print "recursive algorithm, fib (%d) = %10d, %12d calls" % \
        (n, fib (n), count)
    print "bottom up algorithm, bot_up (%d) = %10d" % \
        (n, bot_up (n))

main ()