1

I wrote the following two tetration functions in 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)

And, surprisingly, the recursive version was slightly faster:

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)

I thought it might have something to do with how Python was interpreting it, so I did a C version:

/* 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);
}

And the recursive version was still faster:

> 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

So this difference seems real. The assembled C program (as returned by gcc -S) represents recur_tet as 42 instructions, while iter_tet is 39 instructions, so it seems like the recursive one should be longer? but I don't really know anything about assembly so who knows.

Anyway, does anyone have insights about why the recursive version of each function is faster, despite the common wisdom about recursion vs. iteration? Am I writing my iterative version in a silly way with some inefficiency I'm not seeing?

David
  • 424
  • 3
  • 16
  • Try with `gcc -O2` or `gcc -O3`. Not sure which will be faster, but it's a better comparison. – Tom Karzes May 13 '20 at 17:22
  • In testing your Python code using an online repl using timeit with 1M iterations for each test, but running the tests several times my results show sometimes the recursive version is slightly faster, other times the iterative is slightly faster. – DarrylG May 13 '20 at 17:32
  • It is function call and return (perform n-1, copy pars to stack, jump and jump back with return value) vs. for-loop management (increment and comparison). I'm not sure on what is faster, but it sounds strange to me that the winner is recursion... – Roberto Caboni May 13 '20 at 17:37
  • strange! on my computer, the recursive one is reliably faster with 1M iterations – David May 13 '20 at 17:40

1 Answers1

4

The problem with both the Python and the C comparisons is that the recursive and iterative algorithms are not really equivalent (even though they should produce the same result).

When n is 1, the recursive versions are returning b immediately, with no exponentiation being performed. But the iterative versions are doing exponentiation in that case (b**1 in Python and pow(b, 1) in C). This accounts for the slower speed of the iterative versions.

So in general, the iterative versions are making one additional exponentiation call than the recursive versions.

To do a fair comparison, either change the recursive versions to do exponentiation when n is 1, or else change the iterative versions to avoid it.

Tom Karzes
  • 22,815
  • 2
  • 22
  • 41