## 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)))))```