Learning AI: csx72 » To iterate or recurse, that is the question.

To iterate or recurse, that is the question.

This is a Lisp page, written Fri Jan 18 10:11:32 PST 2008.

Let sum up the first 1,000 integers.

Solution 1: recursion with funky initializations in variable list:

(defun n1   (&optional (x 1000)) 
  (if (< x 0) 
      0
      (+ x (n1 (- x 1)))))

Solution 2: recursion but using helper function called by the main worker with defaults:

(defun n2 ()
  (labels 
      ((n0 (x)
	 (if (< x 0)
	     0
	     (+ x (n0 (- x 1))))))
    (n0 1000)))

Solution 3: no recursion:

(defun n3 ()
  (do* ((x   1000 (1- x))
	(sum x    (+ sum x)))
       ((< x 0) sum)))

Timings:

(defun ns ()
  (let ((r 100000)) 
      (print   t) (time (dotimes (i r) t)) 
      (print 'n1) (time (dotimes (i r) (n1))) 
      (print 'n2) (time (dotimes (i r) (n2))) 
      (print 'n3) (time (dotimes (i r) (n3)))))

Results:

CL-USER> (ns)

T 
Evaluation took:
  0.0 seconds of real time
  1.03e-4 seconds of user run time
  2.e-6 seconds of system run time

N1 
Evaluation took:
  3.167 seconds of real time
  3.154306 seconds of user run time
  0.002845 seconds of system run time

N2 
Evaluation took:
  2.818 seconds of real time
  2.812621 seconds of user run time
  0.001603 seconds of system run time

N3 
Evaluation took:
  0.705 seconds of real time
  0.703598 seconds of user run time
  5.08e-4 seconds of system run time

Conclusions:

Keyword tricks added little to the runtime (2.818 secs to 3.167 secs)

To iterate or recurse, that is the question.

cs472 / cs572