如何将此递归解决方案转换为迭代解决方案？

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

以下递归函数此函数接收树和项目来寻找它的直接的叶子。如果项目是任何子列表的汽车，那么它将返回该子列表。也就是说，

(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的所有培训都避免了这样的循环。（我认为，他们是未官能的，但是这是迂腐边缘）。我做了以下尝试更多的风格conformative：

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

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

来源

2014-11-02 Sean Allred

除非您的树可以嵌套数百个级别，否则不需要避免递归。默认递归限制为400. – Barmar 2014-11-02 04:42:52

您的重写版本在'（t（f item（cdr p））））'行上递归。 – Barmar 2014-11-02 04:53:23

@Barmar我知道'while''解''目前是递归的。就我所知，它甚至不起作用;我还没有测试 - 这只是我正在努力的一个尝试，以便这不是一个gimmeh-teh-codez Q. – 2014-11-02 13:46:08

您的“迭代”解决方案仍在递归。它也不会返回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))

来源

2014-11-02 05:04:07 Barmar

如何将此递归解决方案转换为迭代解决方案？

回答

相关问题