> On Jan 15, 2019, at 10:13 AM, 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.
It doesn’t optimize such calls, Racket implements them properly, that is, w/o
consumption of stack space.
[[ If your student’s curriculum is based on HtDP (your “natural recursion”
phrase suggests so), he is likely to use Beginning or Intermediate Student
language and the emphasis is on properly designing the function, not
performance details. Here the key is that good design calls for an auxiliary
accumulator-style function. As a teacher, I’d also be happier if the two were
factored into two explicit function definitions (let-loop defines a function
implicitly)
;; N -> [Listof N]
;; determine the factors of n
(define (factor n0)
(local (;; N N -> [Listof N]
;; accu statement: n0 … n is factor-free of 2 … d (which is quite
sophisticated for a high school student; good high school)
(define (factor/acc n d)
(cond
[(> d n) ‘()]
[else (if (= (modulo n d) 0) (cons d (factor/acc (quotient n
d) d)) (factor/acc n (add1 d)))])))
(factor/acc n0 2))
HtDP shows an alternative, simpler solutions for less talented college
students. ]]
— Matthias
--
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.
