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 450283905890997363as 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 oneRepeated squaring is recursiveDespite 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 <= 0:        yield n,n*n    yield n*n,list(rep_square(n*n,times-1))It never returns. 
How to improve this functional python fast exponentiation routine?
python;functional programming;recursion
You haven't said anything against itertools, so here's how I'd do it with generators:from itertools import compressfrom operator import muldef radix(b) :    while b :        yield b & 1        b >>= 1def squares(b) :    while True :        yield b        b *= bdef fast_exp(b, exp) :    return reduce(mul, compress(squares(b), radix(exp)), 1)