Execution time discrepancy in two O(n) ways of finding maximum value in array

Question

Following 2 algorithms both have O(n) complexity, however the second one using recursion runs much much slower than the first approach which uses a "for loop". Is it because recursion is expensive in Python? In the recursion method I assume O(n) because there are n/2 + n/4 + n/8 ... = n comparisons performed in total. I would appreciate if someone could shed more light on how recursion in Python works.

def findmax1(array):
    curr = array[0]
    for i in range(1,len(array)): 
        if array[i] > curr:
            curr = array[i]
    return curr

def findmax2_aux(left, right):
    if left > right:
        return left
    else:
        return right

def findmax2(array):
    if len(array) <= 1:
        return array
    mid = len(array)//2
    left, right = array[:mid], array[mid:]
    left = findmax2(left)
    right = findmax2(right)
    return findmax2_aux(left, right)

from random import randint
test_array = [randint(1,1000) for x in range(1000000)]

t1 = time.time()
findmax1(test_array)
print(time.time()-t1)
# 0.08

t2 = time.time()
findmax2(test_array)
print(time.time()-t2)
# 1.05

In short, recursion is slow in Python because each recursive call requires a creation of a new stack frame. Does [this](https://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping) help? — Jake Tae, May 01 '20 at 13:51
Given that `array` is a `list`, there's also the overhead in `findmax2` of the shallow copies created by `array[:mid]` and `array[mid:]`. — chepner, May 01 '20 at 13:55
A consequence of the observation of @chepner is that the recursive method is O(n log n) and not linear. — Paul Hankin, May 01 '20 at 16:51

RafalS · Accepted Answer · 2020-05-01T14:02:35.957

Function calls are generally more expensive than iteration in most languages. Python has to allocate new frame for a function call, and doesn't optimize tail reursion to iteration. See the more generic timings:

In [2]: def recursive(n): 
   ...:     if n > 0: 
   ...:         return f(n-1) 
   ...:                                                                                                                                                                                               

In [3]: def iterative(n): 
   ...:     for _ in range(n): 
   ...:         pass 
   ...:                                                                                                                                                                                               

In [4]: %timeit recursive(1000)                                                                                                                                                                       
114 µs ± 6.1 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [5]: %timeit iterative(1000)                                                                                                                                                                       
19.2 µs ± 1.5 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

score 1 · Answer 2 · answered May 01 '20 at 13:55

There is no such fact as recursion being expensive in python but some reasons as to why it appears is because there is increase in number of function invokes and increase in size of function call stack (which keeps track of each nested function call) leading to increased number of interactions b/w processor and memory . Still recursion is an effective tool but avoid it if iterative and recursive approaches have same time complexity.

Execution time discrepancy in two O(n) ways of finding maximum value in array

2 Answers2