LISP-提高遞歸尾遞歸在旋轉列表功能

我在LISP遞歸函數來旋轉列表向左或向右如下：LISP-提高遞歸尾遞歸在旋轉列表功能

（如果數字爲正性推到左側，如果是負 - 推到右）

> (rotate-n ‘(5 6 7 8 9) -3) 
    (7 8 9 5 6) 

> (rotate-n ‘(5 6 7 8 9) 3) 
    (8 9 5 6 7)

功能：

(defun rotate-n (L n) 
    (cond ((= n 0) L) 
     ((> n 0) (rotate-n (rotate-left L) (- n 1))) 
     ((< n 0) (rotate-n (rotate-right L) (+ n 1)))))

有沒有辦法使用尾遞歸來得到相同的結果？功能旋轉右旋和左旋轉工作正常。

編輯：我困惑。我上面寫的函數是tail-recursion。如果我沒看錯，這個功能是爲了同樣的目的常規遞歸：

(defun rotate-n-r (L n) 
    (cond ((= n 0) L) 
     ((> n 0) (rotate-left (rotate-n-r L (- n 1)))) 
     ((< n 0) (rotate-right (rotate-n-r L (+ n 1))))))

來源

2012-06-12 זאבי כהן

你有你的左旋轉和右漢字功能可用？因爲它們將不得不被修改/包含在rotate-n中以便尾遞歸工作。 –

當然，我寫了他們，他們的工作。你認爲有可能通過尾遞歸來解決它嗎？ –

是的，但我不知道這是一個好主意：效果是完全相同的兩種方式。這種方法非常像尾遞歸：在進行遞歸調用之前旋轉。 –

這裏是一個尾遞歸函數，你想要做什麼：

(defun rotate-list (list n) 
    (cond ((plusp n) 
     (rotate-list 
      (append (rest list) (list (first list))) 
      (1- n))) 
     ((minusp n) 
     (rotate-list 
      (append (last list) (butlast list)) 
      (1+ n))) 
     (t list)))

注意，它conses之外（即分配內存）很多：

(ext:time (rotate-list '(5 6 7 8 9) 30)) 
              Permanent   Temporary 
Class         instances bytes instances bytes 
-----         --------- --------- --------- --------- 
CONS           5  80  145  2320 
-----         --------- --------- --------- --------- 
Total           5  80  145  2320 
Real time: 3.2E-5 sec. 
Run time: 0.0 sec. 
Space: 2400 Bytes 
(5 6 7 8 9)

非consing版本：

(defun nrotate-list (list n) 
    (cond ((plusp n) 
     (nrotate-list 
      (nconc (rest list) (progn (setf (cdr list) nil) list)) 
      (1- n))) 
     ((minusp n) 
     (nrotate-list 
      (nconc (last list) (nbutlast list)) 
      (1+ n))) 
     (t list)))

同時仍然尾遞歸沒有分配任何東西：

(time (nrotate-list '(5 6 7 8 9) 30)) 
Real time: 2.3E-5 sec. 
Run time: 0.0 sec. 
Space: 0 Bytes 
(5 6 7 8 9)

注意，這兩個版本是相當愚蠢的性能代價（它們掃描列表兩次爲每個迭代，即其時間複雜度是O(n*length(list))）。

高效版將掃描只需在列表中一次（即時間複雜度O(length(list))），並會不是遞歸的。

來源

2013-01-01 18:14:44 sds

LISP-提高遞歸尾遞歸在旋轉列表功能

回答

相關問題