[plt-scheme] Android; compiling to Java byte code; Clojure
Yes, I prefer counting down to counting up, too.
After examining your factorial-2 procedure, I believe
I have discovered a way to make it slightly more
efficient.
Your factorial-2 procedure uses tail recursion in
computing factorial while counting down to 0.
However, it is not necessary to count all the way down
to 0. Let's see the process when we call factorial-2
with n=5:
(factorial-2 5)
=> (fact-iter 1 5)
=> (fact-iter 5 4)
=> (fact-iter 20 3)
=> (fact-iter 60 2)
=> (fact-iter 120 1)
=> (fact-iter 120 0)
=> 120
The answer was already computable without any
additional recursive calls after calling (fact-iter
120 1), because 1 is the identity value for
multiplication. Therefore, I would rewrite your
factorial-2 procedure as follows:
(define (factorial-3 n)
(define (fact-iter product counter)
(if (or (= 1 counter) (zero? counter))
product
(fact-iter (* counter product)
(sub1 counter))))
(fact-iter 1 n))
This is the process when we call (factorial-3 5):
(factorial-2 5)
=> (fact-iter 1 5)
=> (fact-iter 5 4)
=> (fact-iter 20 3)
=> (fact-iter 60 2)
=> (fact-iter 120 1)
=> 120
This process is one recursive call shorter--not very
significant, but very slightly more efficient.
Benjamin L. Russell
--- Noel Welsh <noelwelsh at gmail.com> wrote:
> On Nov 22, 2007 6:01 AM, Benjamin L. Russell
> <dekudekuplex at yahoo.com> wrote:
> > It seems to me that recur and loop together allow
> a
> > more intuitive version of the equivalent of tail
> > recursion in this case than the regular tail
> recursion
> > in the equivalent SICP Scheme version.
>
> I don't like calling anything intuitive, as it seems
> what people mean
> by intuitive is really "similar to stuff I already
> knew". To me the
> recur function is *strange*. I don't really
> understand how recursion
> points are established. A recursion point is some
> kind of dynamically
> scoped variable? If so, that means I can really
> mess up programs if I
> add code between the establishment of a recursion
> point and the call
> to recur.
>
> FWIW, I'd rewrite a SICP's tail-recursive factorial
> as:
>
> (define (factorial n)
> (define (fact-iter product counter)
> (if (> counter n)
> product
> (fact-iter (* counter product)
> (+ counter 1))))
> (fact-iter 1 1))
>
> I'd probably also count down, so I can use zero?,
> and use sub1. This
> makes the code clearer in my opinion.
>
> (define (factorial-2 n)
> (define (fact-iter product counter)
> (if (zero? counter)
> product
> (fact-iter (* counter product)
> (sub1 counter))))
> (fact-iter 1 n))
>
> N.
>