LISP- Improve recursion to tail recursion in rotate list function

Question

I have a recursive function in LISP to rotate list to right or left as following:

(If the number is positive- push to the left, if it's negative - push to the right)

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

The function:

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

Is there a way to get the same result using tail-recursion? The functions rotate-right and rotate-left work fine.

EDIT: I confused. The function I wrote above was tail-recursion. If I am not wrong, this function is regular recursion for the same purpose:

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

Do you have your rotate-left and -right functions available? Because they'll have to be modified/included in rotate-n for tail recursion to work. — Nathaniel Ford
– Nathaniel Ford, Commented Jun 12, 2012 at 20:14
Sure, I wrote them and they work. Do you think it is possible to solve it with tail-recursion? — zcohen
– zcohen, Commented Jun 12, 2012 at 20:15
Yes, but I'm not sure it is a good idea: the effect is exactly the same either way. This method is pretty much tail recursion: you rotate before you make the recursive call. — Nathaniel Ford
– Nathaniel Ford, Commented Jun 12, 2012 at 20:18
Why you think current implementation isn't tail recursive? Last call in cond is rotate-n — paul
– paul, Commented Jun 12, 2012 at 20:18
@paul has the right of it here. Unless you mean you want your rotate-left and -right functions to be tail recursive, which may or may not already be the case. — Nathaniel Ford
– Nathaniel Ford, Commented Jun 12, 2012 at 20:19

sds · Accepted Answer · 2013-01-01 18:14:44Z

Here is a tail-recursive function which does what you want:

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

Note that it conses (i.e., allocates memory) a lot:

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

A non-consing version:

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

does not allocate anything while still being tail-recursive:

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

Note that both versions are pretty stupid performance-wise (they scan the list twice for each iteration, i.e., their time complexity is O(n*length(list))).

The efficient version would scan the list just once (i.e., time complexity O(length(list))) and will not be recursive.

Collectives™ on Stack Overflow

LISP- Improve recursion to tail recursion in rotate list function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related