(defun fibonacci(n) ; displays the first n fibonacci numbers
  (setq a '()) 	            ; initialize the list
  (cond                     ; test n
       ((= n 1) (setq a '(1)))
       ((= n 2) (setq a '(1 1)))
	             ;adds a number to the beginning of list and reverses list
       ((> n 2) (reverse (push (+ (car (reverse (fibonacci (- n 1)))) (cadr a)) a)))))

2) As with number 1, a common problem was printing the answer instead of returning it. I took off for this with first-elements because the problem specifies to return the first n elements. Printing with parts B and C usually also resulted in the answer being returned so I did not take off for those two. We wanted you to use recursion in all of these. It may be tough to grasp recursion for list manipulation at first, but the solutions become much simpler if you use it.

With (middle x), the idea behind not using numbers was to make you use recursion. The simplest way to do this is to recursively chop off the first and last element of the list until there are only one or two elements left. Then return the first of the remaining elements.

; first-elements - recursively call this function, each time removing the first element, decreasing n, 
; and calling the function on the remainder of the list. Each recursive call returns a list of the atoms 
; after if but before the nth.  The current element is cons's with that list as the recursion works back up to
; the first element.


  (defun first-elements (x n)
    (cond
      ((< n 1) NIL)
      ((= n 1)
        (list (car x)))
      (T
        (cons (car x) (first-elements (cdr x) (- n 1))))))


; nth-element - recursively call this function, each time removing the first element, decreasing n, 
; and calling the function on the remainder of the list.  When n = 1 (at the nth element), return that
; element up through the recursion.

  (defun nth-element (x n)
    (cond
      ((< n 1) NIL)
      ((= n 1)
        (car x))
      (T
        (nth-element (cdr x) (- n 1)))))


; middle x - Recursively chops off the first and last element until only one or 
; two elements remain. At that point, return the first of those elements
; (or just the first of the one element).

  (defun middle (x)
    (cond
      ((= (length x) 0)      ; length x = 0, return nil
         nil)
      ((<= (length x) 2)      ; (length x) is 1 or 2
        (car x))                 ; return first element of the two
      (t                         ; (length x) >= 3
        (middle (cdr (butlast x))))))		; call function on list w/o first and last atoms

3) Some students used the Lisp sort function. The problem clearly states to write your own sort function. Encapsulating the Lisp sort inside a new mysort function declaration does not count for writing your own sort function.

Again recursion was the best way to go about this. This solution uses two functions to implement an insert sort. The first function inserts an atom into a list. If the list is null, it returns the atom as a list. If the atom is less than the first atom in the list, it is inserted at the beginning of the list. Otherwise, it recursively calls itself each time taking off the first element and trying to insert with the remaining elements in the list (cdr lst). Eventually, the atom will be inserted and then the elements before it are cons-ed back onto the beginning of the list as we recurse back up. The mysort function uses recursion to insert the first element of a list into the sorted remainder of the list.

  (defun insert-sort (a lst)
    (cond ((null lst) (list a))
      ((< a (car lst)) (cons a lst))
      (t (cons (car lst) (insert-sort a (cdr lst))))))
	  
  (defun mysort (lst)
    (if (null lst) ()
      (insert-sort (first lst) (mysort (cdr lst)))))
  

This solution was written by an AI professor who is an expert at Lisp. In no way did I expect your answers to be this simple and efficient. I gave credit as long as your solution worked. If you don't follow the recursion in this solution, I recommend executing it while tracing both functions.

4) This was pretty straightforward and just to introduce you to structures.

(defstruct point 
  x 
  y)


(defstruct seg 
  (p1 :type point) 
  (p2 :type point) )


  ;; distance calculates the distance between two points
  ;; using Pythagoras' theorem.
  (defun distance (p1 p2)
    (sqrt (+ (square (- (point-x p1) (point-x p2)))
             (square (- (point-y p1) (point-y p2))))))
  
  (defun square (x) (* x x))
  

  ;; the midpoint of a line segment l lies half way between its endpoints
  ;; on both the x and the y axis.
  (defun midpoint (l)
    (make-point :x (/ (+ (point-x (seg-p1 l)) (point-x (seg-p2 l))) 2)
                :y (/ (+ (point-y (seg-p1 l)) (point-y (seg-p2 l))) 2)))
  
  ;;; Intersectp finds the coordinates of the two segments endpoints,
  ;;; and uses them to calculate the values of v and w.
  ;;; Note that we need to check for the case where the lines are
  ;;; parallel, which would give a divide-by-zero error in the
  ;;; expressions for v and w.
  ;;; If v and w are both in the range [0,1], return the point
  ;;; of intersection (an example of a useful truth value.)
  (defun intersectp (l1 l2)
    (let* ( (x1 (point-x (seg-p1 l1))) (y1 (point-y (seg-p1 l1)))
            (x2 (point-x (seg-p2 l1))) (y2 (point-y (seg-p2 l1)))
            (x3 (point-x (seg-p1 l2))) (y3 (point-y (seg-p1 l2)))
            (x4 (point-x (seg-p2 l2))) (y4 (point-y (seg-p2 l2)))
            (d (- (* (- x3 x4) (- y1 y2)) (* (- x1 x2) (- y3 y4)))))
    (if (zerop d)
        nil                     ;;; lines are parallel - no intersection
       (let ((v (/ (- (* (- x2 x4) (- y3 y4)) (* (- x3 x4) (- y2 y4))) d))
             (w (/ (- (* (- x2 x4) (- y1 y2)) (* (- x1 x2) (- y2 y4))) d)))
                               ;;; is the intersection inside the line segments?
       (if (and (>= v 0) (<= v 1) (>= w 0) (<= w 1))
           (make-point :x (+ (* v x1) (* (- 1 v) x2)) 
		               :y (+ (* v y1) (* (- 1 v) y2)))
		    nil)))))