AI Worksheet #2 - Recursion

All problems to be solved utilizing recursion

1. Without using the Lisp primitive nthcdr, write a procedure called TrimFirst
   that trims off the first n elements from a list.
      Example: (TrimFirst 4 '(a b c d e f g h i j)) returns (e f g h i j)
   
   
2. Write a procedure KeepFirst that will return the first n elements of a list.
   It should be tail recursive. Tail recursion means that the final result
   is returned when the "base case" is reached; no "backtracking" is needed.
   An example of non-tail recursion is:

             (defun length (ls)
   	    (if (null ls)
   	         0
   		 (+ 1 (length (rest ls)))))
    

   The above "length" function needs to backtrack for the result.
   Tail recursive, non-backtracking version:

             (defun length (ls &optional (result 0))
   	      (if (null ls)
   	           result
   		  (length (rest ls) (+ 1 result))))
    

   (See p. 75 "Recursion Can Be Efficient" and p. 83 "Optional Parameters")
   
      Example of KeepFirst: (KeepFirst 5 '(a b c d e f g h)) returns (a b c d e)
   
   
3. Write a function called Ins that will insert a number in an already sorted list.
      Example: (Ins '4 '(1 2 5 8)) returns (1 2 4 5 8)
   
   
4. Write a function InSort (which uses Ins above) which takes an unordered
   list as a parameter and returns an ordered list.
      Example: (InSort '(3 1 5 4 7 2 9)) returns (1 2 3 4 5 7 9)
   
   
5. Write a function Presentp which will determine if a given atom occurs anywhere
   in the list, even in the sublists.
      Example: (Presentp 'x '((a b)(w x)(1 3))) returns T