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