Tail recursive calls

I've typed in an BSTree example from "ANSI Common Lisp" by Paul Graham (page 72). It uses recursion to find place for node insertion and Lispworks 4.3.7 says that stack is full when I tried to push 10000 values in the tree.

I tried to compile it with all possible OPTIMIZE options but result was same.

(defun bst-insert (obj bst <)
(declare (optimize (speed 3)(debug 0)(safety 0)))
(do ((cur bst))
     ((null cur) (make-node :elt obj))
    (let ((elt (node-elt bst)))
      (if (eql obj elt)
          bst
          (if (funcall < obj elt)
              (make-node
               :elt elt
               :l (bst-insert obj (node-l bst) <)
               :r (node-r bst))
              (make-node
               :elt elt
               :r (bst-insert obj (node-r bst) <)
               :l (node-l bst)))
))))

Is optimization possible where ? I like recursive variant more that iterative.

Thanks

Lisper

Re: Tail recursive calls

On 8896 day of my life lisptracker@mail.ru wrote:
> (defun bst-insert (obj bst <)

....

>               (make-node
>                :elt elt
>                :l (bst-insert obj (node-l bst) <)
>                :r (node-r bst))
>               (make-node
>                :elt elt
>                :r (bst-insert obj (node-r bst) <)
>                :l (node-l bst)))
> ))))
>
> Is optimization possible where ? I like recursive variant more that
> iterative.

It is not tail recursion.  After returning from nested BST-INSERT
call, other action is performed: MAKE-NODE.

-- 
Ivan Boldyrev

                                        | recursion, n:
                                        |       See recursion

Re: Tail recursive calls

On 8896 day of my life lisptracker@mail.ru wrote:
> (defun bst-insert (obj bst <)
>   (declare (optimize (speed 3)(debug 0)(safety 0)))
>   (do ((cur bst))
>      ((null cur) (make-node :elt obj))
>     (let ((elt (node-elt bst)))
>       (if (eql obj elt)
>           bst
>           (if (funcall < obj elt)
>               (make-node
>                :elt elt
>                :l (bst-insert obj (node-l bst) <)
>                :r (node-r bst))
>               (make-node
>                :elt elt
>                :r (bst-insert obj (node-r bst) <)
>                :l (node-l bst)))
> ))))
>
> Is optimization possible where ? I like recursive variant more that
> iterative.

Do not call MAKE-NODE inside IF: these objects are just ignored.  DO
form evaluates statements inside but ignores results.  Then the
function will be tail-recursive.

I'd replace whole body of the loop with:

    (let ((elt (node-eld bst)))
       (if (eql obj elt)
          bst
          (bst-insert  obj
                       (if (funcall < obj elt)
                          (node-l bst)
                          (node-r bst))
                       <)))

-- 
Ivan Boldyrev

                        Today is the first day of the rest of your life.

Re: Tail recursive calls

On 8897 day of my life Ivan Boldyrev wrote:
> On 8896 day of my life lisptracker@mail.ru wrote:
>> (defun bst-insert (obj bst <)
>>   (declare (optimize (speed 3)(debug 0)(safety 0)))
>>   (do ((cur bst))

> Do not call MAKE-NODE inside IF: these objects are just ignored.  DO
> form evaluates statements inside but ignores results.  Then the
> function will be tail-recursive.

My mistake: it will never be tail-recursive because every recursive
call is inside DO loop.   You have to find another way to code it :)

-- 
Ivan Boldyrev