fibonacci.cover

       '''
       The famous Fibonacci sequence: 0, 1, 1, 2, 3, 5,...
       
       # counting the calls to line 14
       N   recursive   iterative   memoizing
       ==  =========   ==========  ===============
       5   19          15          5
       10  276         55          10
       15  3177        120         15
       20  35400       210         20
       25  392809      325         25
       30  4356586     465         30
           ~phi^N      ~n^phi      ~N
    1: '''
       
    1: import decorators
       
    1: @decorators.random_cache(maxsize=100)
       def nth(n):
           '''
           The n-th term in the Fibonacci sequence.
       
               0-th: 0
               1-th: 1
               n-th: (n-1)th + (n-2)th
           '''
       
 5057:     if n == 0:
    1:         return 0
 5056:     if n == 1:
    1:         return 1
 5055:     return nth(n-1) + nth(n-2)
       
       """
       def nth(n):
           '''
           all recursions can be rewritten as iterations'
           '''
           a, b = 0, 1
           for i in xrange(n):
               a, b = b, a + b
           return a
       """
       
    1: if __name__ == '__main__':
    1:     import sys
    1:     print sys.argv
    1:     try:
    1:         n = int(sys.argv[1])
           except (IndexError, ValueError):
               n = 10
 5001:     for i in range(n):
 5000:         print '{}-th:'.format(i), nth(i)