| Geoffrey 2007-05-05, 7:04 pm |
| On May 4, 4:20 pm, "Xcriber51" <Ken <ken-t...@mail.info>> wrote:
> Hi --
>
> I wrote this function for converting numbers in base-N to decimal.
>
> (defun in-decimal-base (n base)
>
> [snip]
>
> Not being a LISP guru, can't think of a "tail recursive" version
> immediately--assuming it'd be any better in this case. Still, it feels
> so... imperative and inelegant -- those stacked "setfs" look awful.
> (Please, no wisecracks like "what makes you think 'imperative =>
> inelegant'?" etc.)
>
> Any suggestions for improvement?
>
> -- Ken
Tail recursion isn't terribly difficult to do: in fact, you don't even
need to understand the problem in order to translate code into that
form. The above is a perfectly acceptable imperative approach (though
certainly not optimized). Higher order constructs have already been
mentioned, and fold/unfold is a very attractive method for doing this.
So I'll just offer a very direct translation into a tail-recursive
call.
(defun in-decimal-base (n base)
(labels ((recurser (result i n)
(if (> n 0)
(let ((tmp (mod n (expt 10 (1+ i)))))
(recurser (+ result (* (/ tmp (expt 10 i)) (expt
base i))) (1+ i) (- n tmp)))
result)))
(recurser 0 0 n)))
What this does is define a recurser function. The trick is that
everything required for the next step of the computation is passed as
a parameter to this function. The variable "digit" vanished, because
it was only an intermediate step in calculating the next result: it's
computation has been inserted directly into the code for result. "tmp"
remains only because it's computation would have to be performed twice
without.
It doesn't actually require an understanding of how the algorithm
works in order to translate most imperative loops into tail-recursive
constructs: just take every value needed for the next stage of the
computation and make it a parameter to the recurser.
I hope this explanation helps.
|