#!/usr/bin/python

# The usual recursion is too complex. So we use a dictionary to store
# already computed values

knownfibs = {0:0, 1:1}
def fib_1(n):
    if n < 0:
        raise NegativeArgument
    elif n in knownfibs:
        return knownfibs[n]
    else:
        res = fib_1(n-1) + fib_1(n-2)
        knownfibs[n] = res
        return res

print 'fib_1(35) = ', fib_1(35)
print 'fib_1(36) = ', fib_1(36)
print 'fib_1(37) = ', fib_1(37)
print 'fib_1(38) = ', fib_1(38)
print 'fib_1(39) = ', fib_1(39)
print 'fib_1(40) = ', fib_1(40)
print 'fib_1(41) = ', fib_1(41)
print 'fib_1(42) = ', fib_1(42)
print 'fib_1(43) = ', fib_1(43)
print 'fib_1(44) = ', fib_1(44)
print 'fib_1(45) = ', fib_1(45)
print 'fib_1(46) = ', fib_1(46)
print 'fib_1(47) = ', fib_1(47)
print 'fib_1(48) = ', fib_1(48)