我用 Python 编写了以下两个四分函数:
def recur_tet(b, n):
if n == 1:
return(b)
else:
return(b ** recur_tet(b, n - 1))
def iter_tet(b, n):
ans = 1
for i in range(n):
ans = b ** ans
return(ans)
而且,令人惊讶的是,递归版本稍微快一些:
python3> %timeit recur_tet(2,4)
1 µs ± 12.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
python3> %timeit iter_tet(2,4)
1.15 µs ± 14.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
我认为这可能与 Python 的解释方式有关,所以我做了一个 C 版本:
/* tetration.c */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int recur_tet(int b, int n){
if(n == 1){
return(b);
}
else{
return(pow(b, recur_tet(b, n - 1)));
}
}
int iter_tet(int b, int n){
int ans = 1;
int i;
for(i = 1; i <= n; i++){
ans = pow(b, ans);
}
return(ans);
}
int main(int argc, char *argv[]){
/* giving an argument of "1" will do a recursive tetration
while an argument of "2" will do an iterative one */
if(atoi(argv[1]) == 1){
recur_tet(2,4);
}
else if(atoi(argv[1]) == 2){
iter_tet(2,4);
}
return(0);
}
递归版本仍然更快:
> gcc tetration.c -o tet.o
> time(while ((n++ < 100000)); do ./tet.o 1; done)
real 4m24.226s
user 1m26.503s
sys 1m32.155s
> time(while ((n++ < 100000)); do ./tet.o 2; done)
real 4m40.998s
user 1m30.699s
sys 1m37.110s
所以这种差异似乎是真实的。汇编的 C 程序(由 gcc -S
返回)表示 recur_tet
为 42 条指令,而 iter_tet
为 39 条指令,因此看起来像递归应该更长吗?但我对汇编一无所知,所以谁知道呢。
无论如何,尽管有关于递归与迭代的常识,但有人知道为什么每个函数的递归版本更快吗?我是否以一种愚蠢的方式编写了我的迭代版本,并且没有看到一些低效率的情况?
最佳答案
Python 和 C 比较的问题在于递归和迭代算法并不真正等效(即使它们应该产生相同的结果)。
当n
为1
时,递归版本立即返回b
,而不执行求幂。但在这种情况下,迭代版本会进行求幂(Python 中的 b**1
和 C 中的 pow(b, 1)
)。这就是迭代版本速度较慢的原因。
因此,一般来说,迭代版本比递归版本多进行一次求幂调用。
为了进行公平比较,请更改递归版本以在 n
为 1
时进行求幂,或者更改迭代版本以避免这种情况。
关于python - 为什么 C 和 Python 中的递归 tetration 比迭代 tetration 更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61780692/