Greg Ewing writes:
> 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?
Yes --- an exercise. (It would be relevant if I were in a language that
gives me tail-call optimization. I'm preparing myself for when that
happens.)
> Note that Python doesn't optimise tail calls, so anything that
> can be done tail-recursively is probably better done iteratively.
I agree. By the way, I once read or watched an interview with Guido van
Rossum and and he was asked why not to tail-call optimize Python and the
answer he gave --- IIRC --- was that tail-call optimization makes it
harder for a beginner to understand a stack trace. I'm now interested
in discovering whether that was his sole reason. Do you (or does
anyone) know of any reference that I could look into? Thank you.
>> --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.
I think you're quite right and that was not clear until now. Here's my
iterative version of the procedure:
--8<---cut here---start->8---
def isam(b, e, m):
r = 1
while e > 0:
if is_even(e):
b = remainder(b * b, m)
e = e // 2
else:
r = remainder(r * b, m)
e = e - 1
return remainder(r, m)
--8<---cut here---end--->8---
So, indeed, it is asymmetric. When it's even, I change the base. When
it's odd, I change the /r/eturning value. Thank you so much.
(*) The remainder function
--8<---cut here---start->8---
def is_even(n):
return remainder(n, 2) == 0
def remainder(a, b):
return a % b
--8<---cut here---end--->8---
--
https://mail.python.org/mailman/listinfo/python-list
