如何將此遞歸解決方案轉換爲迭代解決方案？

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

如何將此遞歸解決方案轉換爲迭代解決方案？

回答

相關問題