2

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

有没有办法使用尾递归获得相同的结果？向右旋转和向左旋转功能可以正常工作。

编辑：我很困惑。我上面写的函数是尾递归。如果我没记错的话，这个函数是出于相同目的的常规递归：

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

1 回答 1

1

这是一个尾递归函数，可以满足您的要求：

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

请注意，它消耗（即分配内存）很多：

(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-01T18:14:44.177 回答