为什么递归四分体在 C 和 Python 中比迭代四分法更快?

Question

我用Python编写了以下两个tetration函数：

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 条指令，所以递归程序似乎应该更长？但我真的对组装一无所知，所以谁知道呢。

无论如何，有没有人知道为什么每个函数的递归版本更快，尽管关于递归与迭代的普遍智慧？ 我是否以一种愚蠢的方式编写我的迭代版本，并且没有看到一些低效率？

Answer 1

Python 和C 比较的问题在于递归算法和迭代算法并不是真正等价的(即使它们应该产生相同的结果(。

当n1时，递归版本会立即返回b，而不执行幂运算。 但是在这种情况下，迭代版本正在做指数(在Python中b**1，在C中pow(b, 1)(。 这解释了迭代版本的速度较慢的原因。

因此，一般来说，迭代版本比递归版本进行一个额外的幂调用。

为了进行公平的比较，要么更改递归版本以在1n时进行幂运算，要么更改迭代版本以避免它。