Re: [aima-talk] Complex returns from recursive functions - tail recursion?
- On 29/01/06, Robert Futrelle <futrelle@...> wrote:
> This is more a straight Lisp question, but it relates to material inI can say that it's not tail recursive. I couldn't spot it at first
> the early chapters of PAIP. (Someone can direct me to a better list
> for this, I'm sure.)
> This function splits an even-length list into its even and odd
> (sequence) elements:
> (defun split-list (lst)
> (cond ((null lst) '(() ()))
> (t (let ((lst2 (split-list (rest (rest lst)))))
> (list (cons (first lst) (first lst2))
> (cons (second lst) (second lst2)))
> Point being, there's more to recursion than consing up a single list.
> 1 > (split-list '(b d i o g g))
> ((B I G) (D O G))
> I assume it's not tail-recursive.
because the simple form to look for is a recursive call embedded in an
argument position (I don't know the correct terminology), like "(cons
lst (split-list ...". However, the problem is that the result of the
recursive call is bound to lst2 and then there is more to do. It's
just that the lst2 is used twice so it's an optimisation.
> Can it be made so using multiple-value return?Not sure but I think not. Multiple return value is like an
optimisation for returning a tuple (a pair in this case). Using
mutiple return values might prevent consing of the pair and use of
registers for both return values. It doesn't mean change the fact that
this technique needs to do something (cons) with the results of a call
to split-list. What do you think?
> (this is not a quiz, just a question ;-)Seems like a quiz :)
Steven Shaw http://abstractsimplicity.co.uk/
- Here's version that's tail recursive though I don't think very
efficient because of my use of append and list perhaps were not
(defun split-list2 (list)
(let ((a (list)) (b (list)))
(split-list2-helper list a b)))
(defun split-list2-helper (list firsts seconds)
(cond ((null list) (list firsts seconds))
(rest (rest list))
(append firsts (list (first list)))
(append seconds (list (second list)))))))
Also, I forget the syntax for defining inner auxilary functions...
flet, labels, defun??...
- On 29/01/06, Peter Norvig <peter@...> wrote:
> How about this:Looks good. I could have done with nvreverse myself!