This is the mail archive of the guile@sourceware.cygnus.com mailing list for the Guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Recursive vs. tail-recursive functions


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
----------------------------------------------------------------------


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]