# [plt-scheme] recursion and efficiency?!

 From: Manfred Lotz (manfred.lotz at web.de) Date: Tue Apr 20 14:23:09 EDT 2004 Previous message: [plt-scheme] The definition of a variable in a canvas Next message: [plt-scheme] recursion and efficiency?! Messages sorted by: [date] [thread] [subject] [author]

```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. Previous message: [plt-scheme] The definition of a variable in a canvas Next message: [plt-scheme] recursion and efficiency?! Messages sorted by: [date] [thread] [subject] [author]