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.
