[plt-scheme] recursion and efficiency?!
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