;; CMPU 101, Spring 2013
;; HW 3

(display "\n         CS101 Assignment 3, Spring 2013")
(display "\n         PLEASE WRITE YOUR NAME HERE\n\n")

; Before starting to write functions, you should read completely through
; every problem statement. There is one part to problem 1 and three 
; parts for problem 2.


(display "Problem 1: Writing a function to add all the even numbers\n")
(display "              from 2 to N\n\n")
; 
; Problem 1:
; 
;   Write a recursive function called add-evens that consumes 
;   a positive natural number n and returns the sum of all the 
;   even numbers between 2 and n, including 2 and n if n is even.  
;   If n is odd, your function should call itself with the 
;   argument n - 1.
;   
;   This function must be able to consume either an even or an
;   odd number as the initial value of n.  
;  
;   Several calls to this function as they would appear in the 
;   interactions window are shown below:
; 
;   > (add-evens 9)
;   20
;   > (add-evens 11)
;   30
;   > (add-evens 2)
;   2
;   > (add-evens 5)
;   6
;          
;          


; Contract:  
; Header:   
; Purpose: 


; Pre-Function tests:

; Function definition:


; Printfs:

(newline)
(newline)

(display "Problem 2(a): Computing the nth Fibonacci number.\n\n")
; 
; PROBLEM 2(a):  Computing the nth Fibonacci number (a.k.a the 
;                "rabbit breeder's problem")
; 
;     The Fibonacci numbers are defined as follows:
; 
;        - the 0th Fibonacci number is 0,
;        - the 1st Fibonacci number is 1, and
;        - each subsequent Fibonacci number is the sum of the
;          previous two Fibonacci numbers. 
;          
;          (fibonacci 2) = (fibonacci 1) + (fibonacci 0) = 1
;          (fibonacci 3) = (fibonacci 2) + (fibonacci 1) = 2
;          (fibonacci 4) = (fibonacci 3) + (fibonacci 2) = 3
;          (fibonacci 5) = (fibonacci 4) + (fibonacci 3) = 5 
;          
;     The first 9 Fibonacci numbers are:
;     
;     0  1  2  3  4  5  6  7  8 (non-negative natural number arguments) 
;     0  1  1  2  3  5  8 13 21 (corresponding Fibonacci numbers output) 
;     
;     Define a recursive function, fibonacci, that computes sums 
;     of the form described above.   
;     
;     If you are writing a recursive function in which n is the 
;     recursive parameter, you will probably choose to write the      
;     function such that n gets closer to 0 on each recursive 
;     call.
;     
;     This function should consume 1 parameter, the value of n. You
;     should have 2 base cases, and the recursive call should match 
;     this format: (fibonacci i) = (fibonacci i-1) + (fibonacci i-2) 
;     
;     Write the contract, header, purpose, pre-function tests, 
;     function definition, and post-function printf's.
;        
;     WARNING: Avoid writing tests for numbers larger than 25 
;     because this function is VERY inefficient and will take a 
;     prohibitively long time to complete.
;     
;     


; Contract:
; Header:
; Purpose:

; Pre-function tests:


; Function definition:


; Post-function printf's:



(newline)
(newline)

(display "Problem 2(b): Computing the nth Fibonacci number using ")
(display "accumulators.\n\n")
; 
; PROBLEM 2(b):  An alternate way to compute the nth Fibonacci number  
; 
;     Define a tail-recursive function, FIB-ACC, that computes numbers 
;     of the form described in problem 2(a).   
;     
;     This function should consume 3 parameters, the value of n,
;     the value of the base case when n = 0, (parameter acc0, 
;     initially 0), and the value of the base case when n = 1, 
;     (parameter acc1, initially 1).
;     
;     This function should have 2 base cases, 0 and 1. Since this
;     is an accumulator function, base case 0 should return acc0, 
;     and base case 1 should return acc1.  The actual fibonacci 
;     number for n will be accumulated in acc1 in each recursive
;     step. As the recursive parameter n gets smaller on each step of 
;     the recursion, the accumulators should be added together, 
;     sending their sum in for the next value of acc1, and the value 
;     of acc1 should be sent in for the next value of acc0. 
;     
;     The 0 base case return value, acc0, will only be returned if 
;     n = 0. In all other cases, the value of acc1 will be returned
;     for the base case because the base case of n = 1 will be 
;     executed for all n > 0.
;     
;     Follow the design recipe when writing this function:
;     Write the contract, header, purpose, pre-function tests, 
;     function definition, and post-function printf's.
;        
; 


; Contract:
; Header:
; Purpose:

; Pre-function tests:

; Function definition:

; Post-function printf's:


(newline)
(newline)

(display "Problem 2(c): Measuring the run time of the fibonacci\n")
(display "              and fib-acc functions\n\n")
; 
; PROBLEM 2(c):  Comparing the run time of fibonacci and fib-acc  
; 
;     Uncomment the calls to the time function, shown below, on
;     the fibonacci function and the fib-acc function with the
;     same input. 
;     
;     The time function measures the actual computer time taken to 
;     run a procedure as shown:
;        
;                cpu time: 0 real time: 0 gc time: 0
;          
;     The cpu time is the time that the central processing unit (cpu) 
;     spent running the function, the real time is the clock time the 
;     function took to run, and the gc is the time the cpu spent in 
;     garbage collection on the function call. All times are measured
;     in milliseconds. Garbage collection is the process in which 
;     memory that is no longer used is reclaimed by the sytem during
;     execution of a function.
; 


;(time (fibonacci 31))
(newline)
;(time (fib-acc 31 0 1))

(newline)
(newline)