Greg Ewing <greg.ew...@canterbury.ac.nz> 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