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