2.8 bytecodehacks.tailr

This module contains make_tail_recursive a function that has a stab at making a function tail recursive.

It ain't very sophisticated, but it's enough to do that tricksy factorial function <wink>:

def _facr(n,c,p,_facr=_facr):
    if c > n:
        return p
    return _facr(n,c+1,c*p)

def facr(n,_facr=_facr):
    return _facr(n,1,1l)

_factr = make_tail_recursive(_facr)

def factr(n,_factr=_factr):
    return _factr(n,1,1l)

The speed up of factr over facr seems to largely come from the overhead of the former allocating lots and lots of stack frames, rather than the legendarily large Python function-call overhead. This could be because make_tail_recursive generates rather terrible code to save off some parameters while the others are being calculated. It wouldn't take much to improve this, but I don't have the stamina right now.

On my machine, for smallish values of n (which means less than a thousand) factr runs in about 90% of the time of facr. This gets (much) better as n increases, although this is very memory bound - and so not very predictable or consistent. Depends how much swapping has to be done.

For what it's worth an explicitly iterative version

def faci(n):
    p = 1l; c = 1;
    while c <= n:
        p = c*p
        c = c+1
    return p

runs a few percent faster than factr.