Re: Recursion and efficiency

From: <kanderso_at_BBN.COM>
Date: Tue, 07 Feb 95 08:55:14 -0500

The iterative and recursive versions of the function you gave do not do the
same thing. Specifically, the first recursive function crates a substring
stripping off one character on each call, while the iterative version does
the substing only at the end:

(define (delete-trailing-char-itr str c)
    (let ((pos (- (string-length str) 1)))
      (while (and (>= pos 0) (char=? (string-ref str pos) c))
        (set! pos (- pos 1)))
      (if (= pos -1) ""
          (substring str 0 (+ pos 1)))))

The following tail recursive version should have comparable performance.

(define (trim string char)
    (define (trim-1 end)
        (if (<= end 0) ""
            (let ((p (- end 1)))
              (if (char=? (string-ref string p) char)
                  (trim p)
                  (substring string start end)))))
  (trim-1 (string-length string)))

To see how tail recursion is the same as iteration, think of (trim p) as a
goto to the begining of the trim function, with the assigment of (set! end p).

I haven't tested this function. Let us know how the performance compares.

k
Received on Tue Feb 07 1995 - 15:05:49 CET