About me

About me

Feeds

RSS feed

Bisecting a list using recursion

29th September 2016

I've recently been devising a series of Lisp programming problems, and one of the more interesting problems was as follows:

Write a recursive function bisect that takes an integer n and a list, and bisects the list into two parts where n specifies the length of the first part. You can assume that n is not greater than the length of the list.

For example:

(bisect 3 '(a b c d e f g))

should return:

((a b c) (d e f g)).

The obvious way to program this is using subseq:

(defun bisect (n lis)
  (list (subseq lis 0 n) (subseq lis n))

However, for this exercise we want a recursive routine that doesn't use subseq, or any of the mapping or iteration constructs.

One approach

As usual, the best way to approach a recursive problem is to assume we already know how to solve a simpler version of the problem, and transform that into the answer we want.

For example, one obvious approach is to assume we know how to solve:

(bisect (1- n) lis)

To provide the answer to (bisect n lis) from this we need to move the first item in the second sublist to the end of the first sublist.

We also need to provide the explicit answer in a limiting case; for this problem the best choice is:

(bisect 0 lis)

which is simply:

(list nil lis)

An implemention of bisect based on this is as follows:

(defun bisect (n lst)
  (if (zerop n)
      (list nil lst))
  (let* ((l (bisect (1- n) lst))
         (l1 (first l))
         (l2 (second l)))
    (list (append l1 (list (car l2))) 
          (cdr l2))))

Another approach

However, surprisingly there's a different way of solving the problem which results in a simpler answer. We could instead assume we know how to solve:

(bisect (1- n) (cdr lis))

To provide the answer to (bisect n lis) from this we just need to add (car lis) onto the front of the first sublist.

The implemention of bisect based on this is then just:

(defun bisect (n lis)
  (if (zerop n)
      (list nil lis)
    (let ((l (bisect (1- n) (cdr lis))))
      (list (cons (car lis) (first l))
            (second l)))))

blog comments powered by Disqus