gpt4 book ai didi

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

转载 作者:太空狗 更新时间:2023-10-30 02:26:38 25 4
gpt4 key购买 nike

我编写了这段 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) 求和。

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

最佳答案

你的递归函数是调用else中的迭代函数:return 1/n + H(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_rec(n-1) #Fix this line

关于python - 更简单的递归代码比同一事物的迭代版本运行得更慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44336770/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com