Расхождение во времени выполнения двумя O (n) способами поиска максимального значения в массиве

Question

Следующие 2 алгоритма имеют сложность O (n), однако второй, использующий рекурсию, работает намного медленнее, чем первый подход, использующий «для l oop». Это потому что рекурсия дорогая в Python? В методе рекурсии я предполагаю O (n), потому что всего n / 2 + n / 4 + n / 8 ... = n сравнений. Я был бы признателен, если бы кто-то мог пролить больше света на то, как работает рекурсия в Python.

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

Answer 1

Нет такого факта, как рекурсия дорогая в python, но некоторые причины, по которым она появляется, заключаются в увеличении числа вызовов функций и увеличении размера стека вызовов функций (который отслеживает каждую вложенную функцию). вызов) приводит к увеличению количества взаимодействий ч / б процессора и памяти. Тем не менее, рекурсия является эффективным инструментом, но избегайте его, если итеративный и рекурсивный подходы имеют одинаковую сложность по времени.

Answer 2

Вызовы функций, как правило, дороже, чем итерация в большинстве языков. Python должен выделить новый кадр для вызова функции, а не оптимизирует рекурсию хвоста для итерации. Смотрите более общие c сроки:

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)