On 8/11/23 2:26 pm, Julieta Shem wrote:
For the first time I'm trying to write a tail-recursive
square-and-multiply and, even though it /seems/ to work, I'm not happy
with what I wrote and I don't seem to understand it so well.
Stepping back a bit, why do you feel the need to write this
tail-recursively? Is it just an exercise?
Note that Python doesn't optimise tail calls, so anything that
can be done tail-recursively is probably better done iteratively.
--8<---------------cut here---------------start------------->8---
def sam(b, e, m, acc = 1):
if e == 0:
return acc
if is_even(e):
return sam(remainder(b * b, m), e//2, m, acc)
else:
return sam(b, e - 1, m, remainder(b * acc, m))
--8<---------------cut here---------------end--------------->8---
You see, I tried to use an accumulator, but I'm only accumulating when
the exponent is odd. When it's even, I feel I'm forced to change the
base into b * b mod m and leave the accumulator alone. This feels so
unnatural to me. I feel I broke some symmetry there. I'm having to
think of two cases --- when I change the accumulator and when I change
the base. That seems too much for my small head. Can you help?
Well, there are inherently two cases, and they're different, so
I don't think you're doing anything wrong here. It was asymmetrical
to begin with. If you were doing it iteratively you would also be
leaving the accumulator alone when the exponent is even.
--
Greg
--
https://mail.python.org/mailman/listinfo/python-list
