Worksheet #2, Period 1 September 2000

Recursion - all problems to be solved recursively

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.
      Example: (KeepFirst 5 '(a b c d e f g h)) returns (a b c d e)
   
   
3. Write an efficient version of Fibonacci which is not as inefficient as the one
   shown in the book. Use optional parameters and think of working forward
   from the first month.
   
   
4. • Part A. Write a procedure called Ins which will insert a number in an already sorted
     list.    Example: (Ins '4 '(1 2 5 8)) returns (1 2 4 5 8)
     
   • Part B. Write a procedure called 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