How to improve this functional python fast exponentiation routine? I have the following python functions for exponentiation by squaring :

def rep_square(b,exp):
        return reduce(lambda sq,i: sq + [sq[-1]*sq[-1]],xrange(len(radix(exp,2))),[b])

def exponentiate(b,exp):
        return reduce(lambda res,(sq,p): res*sq if p == 1 else res,zip(rep_square(b,exp),radix(exp,2)),1)


They work. Calling print exponentiate(2,10), exponentiate(3,37) yields :

1024 450283905890997363


as is proper. But I am not happy with them because they need to calculate a list of squares. This seems to be a problem that could be resolved by functional programming because : 


Each item in the list only depends on the previous one
Repeated squaring is recursive


Despite people mentioning that recursion is a good thing to employ in functional programming, and that lists are not good friends -- I am not sure how to turn this recursive list of squares into a recursive generator of the values that would avoid a list. I know I could use a stateful generator with yield but I like something that can be written in one line. 

Is there a way to do this with tail recursion? Is there a way to make this into a generator expression? 

The only thing I have thought of is this particularly ugly and also broken recursive generator : 

def rep_square(n,times):
    if times &lt;= 0:
        yield n,n*n
    yield n*n,list(rep_square(n*n,times-1))


It never returns.
You haven't said anything against itertools, so here's how I'd do it with generators:

from itertools import compress
from operator import mul

def radix(b) :
    while b :
        yield b &amp; 1
        b &gt;&gt;= 1

def squares(b) :
    while True :
        yield b
        b *= b

def fast_exp(b, exp) :
    return reduce(mul, compress(squares(b), radix(exp)), 1)