How can I convert this recursive solution into an iterative one?

I have the following recursive function in Lisp

(defun f (item tree)
  (when tree
    (if (equal item (car tree)) tree
      (if (and (listp (car tree))
           (equal item (caar tree)))
      (car tree)
    (if (cdr tree)
        (f item (cdr tree)))))))

This function receives a tree and an item to look for in its immediate leaves. If item is the car of any sublist, then it will return that sublist. That is,

(f 'c '(a b c)) => (c)
(f 'b '(a b c)) => (b c)
(f 'a '((a 1 2) b c)) => (a 1 2)

I've recently been informed that (Emacs Lisp) doesn't do tail recursion optimization, so I've been advised to turn this into a while loop. All of my training in Lisp has been in avoidance of loops like this. (I maintain that they are un-functional, but that's borderline pedantic.) I've made the following attempt for more conformative style:

(defun f (item tree)
  (let ((p tree))
    (while p
      (cond
       ((equal item (car p)) p)
       ((and (listp (car p))
             (equal item (caar p)))
        (car tree))
       (t (f item (cdr p))))
      (setq p (cdr p)))))

_{I've shortened the function name for brevity/clarity, but do have a look at where it is being used if you are a power-user of emacs.}

Solution

Your "iterative" solution is still recursing. It's also not returning the values found in the cond expression.

The following version sets a variable to the found result. Then the loop ends if a result has been found, so it can be returned.

(defun f (item tree)
  (let ((p tree)
        (result nil))
    (while (and p (null result))
      (cond ((equal item (car p)) (setq result p))
            ((and (listp (car p))
                  (equal item (caar p)))
             (setq result (car tree)))
            (t (setq p (cdr p)))))
    result))