Почему обратная рекурсия выполняется быстрее, чем прямая рекурсия в python

Я сделал алгоритм в Python для подсчета количества способов получения суммы денег с разными номиналами монет:

@measure
def countChange(n, coin_list):
    maxIndex = len(coin_list)
    def count(n, current_index):        
        if n>0 and maxIndex>current_index:
            c = 0
            current = coin_list[current_index]
            max_coeff = int(n/current)      
            for coeff in range(max_coeff+1):
                c+=count(n-coeff*current, current_index+1)
        elif n==0: return 1
        else: return 0
        return c
    return count(n, 0)

Мой алгоритм использует индекс, чтобы получить номинал монеты, и, как вы можете видеть, мой индекс увеличивается в каждом кадре стека, в который я вхожу. Я понял, что алгоритм также можно записать следующим образом:

@measure
def countChange2(n, coin_list):
    maxIndex = len(coin_list)
    def count(n, current_index):        
        if n>0 and 0<=current_index:
            c = 0
            current = coin_list[current_index]
            max_coeff = int(n/current)      
            for coeff in range(max_coeff+1):
                c+=count(n-coeff*current, current_index-1)
        elif n==0: return 1
        else: return 0
        return c
    return count(n, maxIndex-1)

На этот раз индекс уменьшает каждый кадр стека, в который я вхожу. Я сравнивал время выполнения функций, и я получил очень примечательную разницу:

print(countChange(30, range(1, 31)))
print(countChange2(30, range(1, 31)))

>> Call to countChange took 0.9956174254208345 secods.
>> Call to countChange2 took 0.037631815734429974 secods.

Почему существует большая разница во времени выполнения алгоритмов, если я даже не кеширую результаты? Почему возрастающий порядок индекса влияет на это время выполнения?

Ответы

print(countChange(30, list(reversed(range(1, 31)))))
print(countChange2(30, list(reversed(range(1, 31)))))