Also note that that there's something called "tail recursion modulo cons" (https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons), though as I understand, Racket didn't implement it.
On Tuesday, January 15, 2019 at 7:29:28 AM UTC-8, Sorawee Porncharoenwase wrote: > > Yes, Racket recognizes the distinction and "optimize" those calls that can > be optimized. Though people might not be happy with the word "optimize". To > quote Shriram: > > It is not an "optimization". An optimization is an optional >> thing; you can't rely on it being done. When you program functionally, >> you are implicitly expecting/relying on "tail" behavior. So [proper tail >> recursion] is a >> *semantic* feature of the language that you take into account as a >> programmer and rely on if its there. (If it's not there, you better >> have CPSed your code or something.) >> > > Read more about tail position at > https://docs.racket-lang.org/reference/eval-model.html#%28part._.Tail_.Position%29 > > and https://people.csail.mit.edu/jaffer/r5rs/Proper-tail-recursion.html > > On Tuesday, January 15, 2019 at 7:13:48 AM UTC-8, Will Jukes wrote: >> >> Hi everyone, >> >> I was helping a student the other day with a problem where they were to >> write a recursive function that uses trial division to return a list of the >> prime factors of an integer (no fancy optimizations, these are high school >> kids who don't have a lot of number theory). It looked something like this: >> >> (define (factor n) >> (let loop ([k n] [d 2]) >> (cond [(> d k) '()] >> [(zero? (modulo k d)) (cons d (loop (quotient k d) d))] >> [else (loop k (add1 d))]))) >> >> >> >> The purpose of this lesson was to illustrate the difference between >> proper tail recursion and regular recursion (our course calls it natural >> recursion), but it occurred to me that this function is actually tail >> recursive in the else clause but not in the second clause. This struck me >> as highly desirable behavior in this case (and possibly others), since even >> those numbers with relatively many prime factors wouldn't create a very >> deep stack -- most recursive calls would go to the third clause. I wanted >> to double check though that Racket (or other Scheme compilers) would >> recognize the distinction and optimize those calls that can be optimized. >> My understanding is that they almost certainly would be, but I'm still >> learning about low-level programming and the implementation is a bit of a >> black box to me. >> > -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
