Programming Exercises in Recursion

This is an individual assignment.
You should complete the exercises in Common Lisp.
Note that, unless otherwise specified, all of the numbers we will deal with in this assignment will be counting numbers; not floats, complex or other numerical types. The counting numbers are the non-negative integers, i.e. 0,1,2,3,...
Call your repository recursion-exercises
For each exercise, write a function of the given name.

Provide tests for each function you write. Ensure good test coverage. Later we will use a unit testing package. For now, write your tests like this.

(defun test-my-length ()
  (or (= 0 (my-length ()))
      (= 1 (my-length '(a)))
      (= 2 (my-length '(a b)))
      (= 3 (my-length '(a b c)))))

(defun my-length (ns &optional (acc 0))
  "Return the length of a list of numbers"
  (if (null ns) acc
      (my-length (rest ns) (+ 1 acc))))

Lists

sum-list finds the sum of all numbers in the list.
double-list return the list with elements which are double those of the input list.
max-element finds the largest number in the list.
positives returns a list of the elements of the input list which are positive numbers (in the same order as they appear in the input list). (Input lists for this function may also contain negative numbers.)
merge-list takes two lists of numbers, both sorted in ascending order. It produces a single sorted list of numbers that contains all the numbers on both inputs lists. A number occurs in the output as many times as it occurs on the two input lists together.

The counting numbers

copies-x takes a counting number, n, and return a list containing n copies of the symbol x.
copies generalises copies-x to a function that can produce a given number of any symbol desired.
square-from returns a list of squares of a given length starting from a given counting number.
```
(squares 8 4) ; => (64 81 100 121)
```
take takes a list and a counting number, n and returns the list consisting of the first n elements of the input list.
drop takes a list and a counting number, n and returns the list gotten by dropping the first n elements of the input list.

Binary Trees

In Lisp we define a binary tree as:

(deftype bt () '(or node null))

(defstruct node
  (value  nil :type fixnum)
  (left   nil :type bt)
  (right  nil :type bt))

In Typed Racket we define a binary tree as:

(define-type BT (U Node Null))

(struct node ((value : Integer) (left : BT) (right : BT))
  #:type-name Node
  #:transparent)

Note the distinction between a binary tree (BT) and a binary search tree (BST). The latter has the extra property that the number at any node is greater than the numbers at all nodes left of it and less than the numbers at all nodes right of it.

A path is a list containing only the symbols left and right e.g.

'(left left right left)

In Common Lisp, the false value is nil. In Typed Racket the false value is #false.

bst<-list takes a list of integers and returns a BST containing those integers.
bt-member? takes a number and a BT and determines whether the number is present in the BT.
bst-member? takes a number and a BST and determines whether the number is present in the BST.
bst-path takes a number and a BST and returns a path describing the route from the root of the BST to the number if the number is present in the BST, or the false value if it is not.
bt-path takes a number and a BT and returns a path describing the route from the root of the BT to the number if the number is present in the BT, or the false value if it is not.
bt-follow-path takes a path and a BT and returns the number found by following the path through the BT, or the false value in case the path is not present in the BT.
Design three functions which takes a BT and returns a list of the numbers occurring in the BT
1. bt-traverse-left-to-right from left to right
2. bt-traverse-depth-first in depth-first search order
3. bt-traverse-breadth-first in breadth-first search order
path-sum takes a BT and a number and returns a path in the BT whose elements sum to that number or the false value if there is no such path.
path-max-sum takes a BT and returns the path through the BT that has the greates path sum among all of its paths.
bt-symmetric? determines whether a BT is symmetric around its vertical axis.
reverse-bst takes a BST and returns the BST with the same elements but in decreasing order left to right, instead of increasing order. The output BST should be a mirror image of the input BST reflected through a vertical line.

S-expressions

An atom is a number, a symbol or a string. (Note that Common Lisp has a broader definition of an atom but ours will suffice for these exercises.)

We define an s-expression to be anything which is an atom or a cons of two s-expressions.

sexp-strings takes an s-expression and returns a list of all of the strings it contains.
sexp-sum-numbers takes an s-expression and returns the sum of all the numbers occurring in it.
sexp-simplify-arithmetic takes an s-expression and simplifies any arithmetic expression occurring in it. For example in this s-expression,
```
'(a b (+ 3 4) c d (* 5 6 e))
```
the subexpression '(+ 3 4) is arithmetic, while the subexpression '(* 5 6 e) is not.