更简单的递归代码比同一事物的迭代版本运行得慢

Question

我编写了这个 python 代码，以递归和迭代的方式给出某个值 n 的谐波级数。下面是函数：

def H(n):
    if (n <= 0): raise ValueError("n must be bigger than 0.")
    if (n == 1): return 1
    else: return sum([1/x for x in range(1,n+1)])

def H_rec(n):
    if (n <= 0): raise ValueError("n must be bigger than 0.")
    if (n == 1): return 1
    else: return 1/n + H(n-1)

然后，当我为每个代码运行 10 次时，我得到以下时间：

RECURSIVE TIMES [22.755768060684204, 17.231882095336914, 14.965636014938354, 14.277509927749634, 14.0553719997406, 13.788002014160156, 13.338942766189575, 13.72638201713562, 14.690818071365356, 14.236813068389893] 
RECURSIVE MEAN: 15.30671260356903
ITERATIVE TIMES [15.093524932861328, 12.801156759262085, 13.350629091262817, 13.806081056594849, 13.29387378692627, 13.876484870910645, 12.934008121490479, 13.859009981155396, 13.350301027297974, 13.590226888656616] 
ITERATIVE MEAN: 13.595529651641845

代码应该找到H_rec(100000000)和H(100000000)，这是相当大的数字。

我不明白为什么递归定义需要更长的时间，因为它的定义方式似乎需要更少的计算。迭代的需要形成一个列表并找到它的总和，而递归的只是求和1/n + H(n-1)。

这个递归有什么误导性？为什么慢？

Answer 1

Python 解释器内执行的代码速度最快。Python 代码（编译为由虚拟机解释的 Python 字节代码）速度较慢。用户定义的函数调用是最慢的，因为虚拟机必须管理自己的调用堆栈来跟踪执行环境。

考虑以下代码：

def S1(n):
    return sum(range(1,n))

def S2(n):
    rv = 0
    for i in range(1,n):
        rv += i
    return rv

def S3(n):
    if n == 0:
        return 0
    else:
        return n + S3(n-1)

S1是最快的；尽可能多的工作被推给口译员。S2速度较慢，因为现在每个添加都是要解释的单独的 Python 指令。S3最慢，因为现在每次加法都涉及另一个函数调用来获取第二个操作数；如前所述，Python 中的函数调用速度很慢。

>>> print(timeit.timeit('S1(50)', globals=globals()))
1.2118524569996225
>>> print(timeit.timeit('S2(50)', globals=globals()))
3.262354401002085
>>> print(timeit.timeit('S3(50)', globals=globals()))
10.102635376999388