algorithm - 如何将这种递归解决方案转换为迭代解决方案？

Question

我在 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)))))))

此函数接收一棵树和一个项以在其直接叶子中查找。如果 item 是任何子列表的汽车，那么它将返回该子列表。也就是说，

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

我最近被告知 (Emacs Lisp) 不进行尾递归优化，因此建议我将其转换为 while 循环。我所有的 Lisp 训练都是为了避免这样的循环。 (我认为它们没有功能，但这是近乎迂腐的。)我做了以下尝试以实现更一致的风格:

(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)))))

_{为了简洁/清晰，我缩短了函数名称，但请查看 where it is being used如果您是 emacs 的高级用户。}

Answer 1

您的“迭代”解决方案仍在递归。它也不会返回 cond 表达式中找到的值。

以下版本将变量设置为找到的结果。如果找到结果，则循环结束，因此可以返回结果。

(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))