CODEWITHSUNDEEP
recursionsplitlispcommon-lisp
Ash
Ash

Reputation: 261

Lisp recursion for split-list

(defun split-list (L) 
    (if (endp L)
    '(nil nil)  
     (let ((x (split-list (cdr L)))) 
         (list (cons (car L) (cadr x))(car X))
         )))

This is the code which I have. It works fine:

(split-list '(1 2 3 4 5 6))
((1 3 5) (2 4 6))

But I need an explanation on the recursion part.

When we call the function (split-list (cdr L)) I am sure that it goes from 123456 to 23456. (car L) is 1 and (cadr X) is 3 but how did 5 came there ?

when function did (split-list (cdr L)) didn't the x became 3456 and (cadr x) should be 4 ? which is wrong and same with other half. (car x) should be 3 now which is wrong.

Could anyone please explain ?

Upvotes: 3

Views: 764

Answers (1)

Rainer Joswig
Rainer Joswig

Reputation: 139411

I would rewrite a recursive split-list as this:

(defun split-list (list) 
  (if (endp list)
      (values nil nil)
    (multiple-value-bind (split1 split2)
        (split-list (rest list))
      (values (cons (first list) split2)
              split1))))

Above uses multiple values. The function returns the split result as two values. We also replace car with first and cdr with rest. The are just better names, but have the same functionality. multiple-value-bind binds the the two values of the recursive split-list call to the variables split1 and split2. The function values returns its two arguments as two values.

In the example below, you can see that the function indeed returns two values:

CL-USER 20 > (split-list '(a b c d e f))
(A C E)
(B D F)

You can trace its execution:

CL-USER 21 > (trace split-list)
(SPLIT-LIST)

CL-USER 22 > (split-list '(a b c d e f))
0 SPLIT-LIST > ((A B C D E F))
  1 SPLIT-LIST > ((B C D E F))
    2 SPLIT-LIST > ((C D E F))
      3 SPLIT-LIST > ((D E F))
        4 SPLIT-LIST > ((E F))
          5 SPLIT-LIST > ((F))
            6 SPLIT-LIST > (NIL)
            6 SPLIT-LIST < (NIL NIL)
          5 SPLIT-LIST < ((F) NIL)
        4 SPLIT-LIST < ((E) (F))
      3 SPLIT-LIST < ((D F) (E))
    2 SPLIT-LIST < ((C E) (D F))
  1 SPLIT-LIST < ((B D F) (C E))
0 SPLIT-LIST < ((A C E) (B D F))
(A C E)
(B D F)

Upvotes: 4

Related Questions