Write a purely applicative LISP program that computes the Nth Fibonacci number using approximately N additions. In other words, the running time of your program should be proportional to N. Write a top-level function, called FASTFIB, that takes a single numeric argument N, and returns the Nth Fibonacci number. You may define and use only one auxiliary function. You may only use constructs covered in class and recitation. You may not use any global variables, or looping constructs, "labels". Try to minimize the number of arguments to your functions. My solution uses only two single-argument functions. Note that you are not expected to develop a closed-form analytic expression for the Nth Fibonacci number, but rather to formulate a recursive solution. Test your program for N = 1 through 10, and also 20, 30, 40, 50, 60, 70, 80, 90, and 100. Time the execution of your FIB function from part 1 and estimate how long your FIB function would take to compute the 100th Fibonacci number.

Not this function

(defun FASTFIB(n) (cond ((eq n 1) 0) ((eq n 2) 1) ((+ (FASTFIB (- n 1)) (FASTFIB(- n 2))))))))