[plt-scheme] recursion and efficiency?!

See HtDP  
(http://www.htdp.org/2003-09-26/Book/curriculum-Z-H 
-39.html#node_sec_31.3).

Nutshell: (1) Tail-call optimizations are about saving space not time.  
(2) Converting
from plain recursion to tail-call optimizations often reverses the  
order of operations
for beginners. In your case, big num arithmetic immediately dominates  
the calculations.
And then there might be Jens's effect. Small benchmarks often pollute  
caches and things
with garbage.

-- Matthias


On Apr 20, 2004, at 2:23 PM, Manfred Lotz wrote:

>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> Hi folks,
> I'm a newbie to both scheme and to the paradigm of functional
> programming.
>
> I built three versions of fact:
>
> ;; recursion
> (define (fact1 x)
>   (cond ((= x 0) 1)
>         (else
>          (* x (fact1 (- x 1))))))
>
> ;; tail recursion from n to 1
> (define (fact2 n)
>      (define (iterate n acc)
>        (if (<= n 1)
>            acc
>            (iterate (- n 1)
>                     (* n acc))))
>      (iterate n 1))
>
> ;; tail recursion from 1 to n
> (define (fact3 n)
>      (define (iterate i acc)
>        (if (> i n)
>            acc
>            (iterate (+ i 1)
>                     (* i acc))))
>      (iterate 1 1))
>
> I assumed fact2 and fact3 being superior from a timing perspective.
> However fact1 is the fastest.
>
> (fact1 20000)
> 	cpu time: 2046 real time: 2202 gc time: 996
> 	2,31s user 0,05s system 92% cpu 2,544 total
>
> (fact2 20000)
> 	cpu time: 6287 real time: 7194 gc time: 5199
> 	6,52s user 0,07s system 87% cpu 7,528 total
>
> (fact3 20000)
> 	cpu time: 5677 real time: 6128 gc time: 4711
> 	5,95s user 0,04s system 92% cpu 6,453 total
>
> Can anybody explain to me why the recursive version is the fastest?
> (This is all under FreeBSD 4.10 BETA)
>
> -- 
> Thanks,
> Manfred