Loops vs. Recursion

bs.py

def binary_search(l, item):
    low = 0
    high = len(l) - 1
    while (low <= high):
        mid = (low+high)//2
        if item < l[mid]:
            high = mid - 1
        elif item > l[mid]:
            low = mid + 1
        else:
            return mid
    return -1

def rec_binary_search(l,low,hi,v):
    if low == hi:
        if v == l[low]:
            return low
        return -1
    else:
        mid = (low+hi)//2
        if v == l[mid]:
            return mid
        elif v > l[mid]:
            return rec_binary_search(l, mid+1, hi, v)
        else:
            return rec_binary_search(l, low, mid-1, v)

metrics.py

from timeit import timeit
from random import randint
from sys import setrecursionlimit

setrecursionlimit(10**4)

all_ratio = []

for test in [100, 100, 10000]:
    print("Testing for {} items".format(test))
    print("-----")
    sample = [randint(1,1000) for _ in range(test)]
    t1 = timeit("binary_search(sample, sample[-1])", 
                number=10, 
                setup="from bs import binary_search; \
                       from __main__ import sample")
    print("Time Take by loop: {}".format(t1))

    t2 = timeit("rec_binary_search(sample, 0, len(sample)-1, sample[-1])", 
                number=10, 
                setup="from bs import rec_binary_search; \
                       from __main__ import sample")
    print("Time Take by recursion: {}".format(t2))

    all_ratio.append(t1/t2)

print("---")
print("Average t1/t2: {}".format(round(sum(all_ratio)/len(all_ratio),3)))

Output.txt

Testing for 100 items
-----
Time Take by loop: 8.668698137626052e-05
Time Take by recursion: 0.00011143798474222422
Testing for 100 items
-----
Time Take by loop: 8.37119878269732e-05
Time Take by recursion: 0.00011085800360888243
Testing for 10000 items
-----
Time Take by loop: 0.00017785700038075447
Time Take by recursion: 0.00023082000552676618
---
Average t1/t2: 0.768