This is the mail archive of the
guile@sourceware.cygnus.com
mailing list for the Guile project.
Recursive vs. tail-recursive functions
- To: Guile Mailing List <guile at sourceware dot cygnus dot com>
- Subject: Recursive vs. tail-recursive functions
- From: Andrew Ho <andrew at tellme dot com>
- Date: Wed, 7 Jun 2000 23:18:05 -0700 (PDT)
Hello,
William's post brought up a topic that most everybody programming Scheme
has probably run into, rewriting recursive functions to use tail
recursion. I know I have done this multiple times.
So the other day I wanted to empirically find out what time savings this
would have, so I wrote the following script to do some timing tests.
The strange result seems to be that the simple recursive case is
significantly faster than the tail-recursive case. What gives?
Is there some secret under-the-hood optimization I'm unaware of?
The results (this is on a Solaris x86 box with 1GB of memory):
(tail-factorial 5): 100000 iterations, 6s (16666.6666666667 operations/s)
(factorial 5): 100000 iterations, 6s (16666.6666666667 operations/s)
(tail-factorial 20): 100000 iterations, 22s (4545.45454545455 operations/s)
(factorial 20): 100000 iterations, 19s (5263.15789473684 operations/s)
(tail-factorial 100): 100000 iterations, 120s (833.333333333333 operations/s)
(factorial 100): 100000 iterations, 108s (925.925925925926 operations/s)
The script:
#!/usr/local/bin/guile -s
!#
;; ----------------------------------------------------------------------
;; recursive.scm - Timing tests on recursive vs. tail-recursive functions
;; Andrew Ho (andrew@tellme.com)
;;
;; Last modified June 7, 2000
;; ----------------------------------------------------------------------
(define (time label n fn . args)
"Time a function with optional args n times, display label in report"
(define TOTAL n)
(define (time-helper begin-time label n fn arglist)
(apply fn arglist)
(if (= n 0)
(let ( (total-seconds (- (car (gettimeofday)) begin-time)) )
(string label ": " (number->string TOTAL) " iterations, "
(number->string total-seconds) "s ("
(number->string (/ TOTAL total-seconds))
" operations/s)\n" ))
(time-helper begin-time label (- n 1) fn arglist) ))
(time-helper (car (gettimeofday)) label n fn args) )
;; ----------------------------------------------------------------------
(define (factorial n)
"Schoolbook recursive factorial"
(if (= n 0)
1
(* n (factorial (- n 1))) ))
(define (tail-factorial n)
"Tail-recursive factorial"
(define (tail-factorial-helper n a)
(if (= n 0)
a
(tail-factorial-helper (- n 1) (* n a)) ))
(tail-factorial-helper n 1) )
(define n 100000)
(display (time "(tail-factorial 5)" n tail-factorial 5))
(display (time "(factorial 5)" n factorial 5))
(newline)
(display (time "(tail-factorial 20)" n tail-factorial 20))
(display (time "(factorial 20)" n factorial 20))
(newline)
(display (time "(tail-factorial 100)" n tail-factorial 100))
(display (time "(factorial 100)" n factorial 100))
(newline)
;; ----------------------------------------------------------------------
Humbly,
Andrew
----------------------------------------------------------------------
Andrew Ho http://www.tellme.com/ andrew@tellme.com
Engineer info@tellme.com Voice 650-930-9062
Tellme Networks, Inc. Fax 650-930-9101
----------------------------------------------------------------------