01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def numFives1 (a, i=0):
  if len(a) == i: 
    return 0
  result = numFives1 (a, i+1)
  if (a[i] == 5.0):
    result += 1
  return result

def numFives2 (a):
  if len(a) == 0: 
    return 0
  result = numFives2 (a[1:])
  if (a[0] == 5.0):
    result += 1
  return result

import time
import sys
sys.setrecursionlimit(10**6)
for f in [numFives1, numFives2]:
  print ("testing " + f.__name__)
  assert 0 == (f ([ ]))
  assert 1 == (f ([ 5 ]))
  assert 0 == (f ([ 11 ]))
  assert 3 == (f ([ 5, 5, 5 ]))
  assert 0 == (f ([ 11, 21, 31, 41 ]))
  assert 1 == (f ([ 5, 11, 21, 31, 41 ]))
  assert 1 == (f ([ 11, 21, 31, 41, 5 ]))
  assert 1 == (f ([ 11, 21, 5, 31, 41 ]))
  assert 3 == (f ([ 11, 21, 5, 31, 5, 41, 5]))
  base = 2000
  for multiplier in [1, 2, 4, 8]:
    length = base * multiplier
    lst = [i for i in range(length)]        
    start = time.time()
    result = f (lst)
    end = time.time()
    print ("Duration of " + f.__name__ + "(" + str(len(lst)) + "): " + str(end - start))

print ("Finished tests")