类似的递归函数在运行时存在巨大差异.为什么

Question

我在研究递归，需要编写一个递归函数来计算给定列表中的最大整数。

首先我尝试了这个：

def find_max(L):
if len(L) == 1: return L[0]
mx = L[0]
return mx if mx > find_max(L[1:]) else find_max(L[1:])

然后我找到了另一种方法：

def find_max2(L):
if len(L) == 1: return L[0]
rest = find_max(L[1:])
if rest > L[0]: return rest
else: return L[0]

我想检查差异，所以我导入了Numpy并创建了一个由随机整数组成的列表

import numpy as np
np.random.seed()
nums = np.random.randint(10000,size=(25,1))
import time
#FIRST APPROACH
s = time.perf_counter_ns()
print(find_max(nums))
e = time.perf_counter_ns()
print("Elapsed time for the find_max:",e-s,"ns")
#SECOND APPROACH
s = time.perf_counter_ns()
print(find_max2(nums))
e = time.perf_counter_ns()
print("Elapsed time for the find_max2:",e-s,"ns")

我意识到第一个比第二个慢2倍。

D:CodesPython
λ python recursion.py
[9726]
Elapsed time for the find_max: 735373900 ns
[9726]
Elapsed time for the find_max2: 362327100 ns
D:CodesPython
λ python recursion.py
[9939]
Elapsed time for the find_max: 4889083400 ns
[9939]
Elapsed time for the find_max2: 2200926700 ns
D:CodesPython
λ python recursion.py
[9913]
Elapsed time for the find_max: 5955406900 ns
[9913]
Elapsed time for the find_max2: 3069119000 ns

我试着弄清楚为什么会这样。但是我不能。。。如果有人能告诉我为什么会这样，我会很感激的！

Answer 1

这里发生了两件事：首先，在第一个函数的最后一行递归调用find_max两次，这意味着每次递归一级，活动调用的数量就会增加一倍。第二件事是在函数find_max2中递归地调用find_max，而不是find_max2。在修复了这个问题的情况下运行find_max2应该会让你的运行时间更快：

def find_max2(L):
if len(L) == 1: return L[0]
rest = find_max2(L[1:])
if rest > L[0]: return rest
else: return L[0]

Answer 2

我假设在find_max2中调用的是find_max2，而不是第一个函数。

这可能需要两倍的时间，因为在第一个实现中，每当当前值不较大时，您都会调用find_max两次，而在第二个实施中，无论当前数字大小，您都只调用它一次

Answer 3

第二个只递归调用find_max一次。

当您还没有找到最大值时，第一个调用find_max两次，这将是平均一半的时间，假设数组中的数字随机分布。

因此，第一个基本上是做两倍的工作，因此它慢两倍是有道理的。