[plt-scheme] recursion and efficiency?!

From: Manfred Lotz (manfred.lotz at web.de)
Date: Tue Apr 20 14:23:09 EDT 2004

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


Posted on the users mailing list.