# Background

# Part 1: Tail Recursion

- Time
- 30 minutes
- Activity
- Small groups / individuals

make a directory

`~/fcshome/cs2613/labs/L05`

to store files from this lab.Background for this part is Racket Guide on Tail Recursion

Run the following code in the debugger, and observe how deep the stack gets.

```
#lang racket
(module+ test
(require rackunit))
(define (odds-evens lst)
(cond
[(empty? lst) (list 0 0)]
[(odd? (first lst)) (map + '(1 0) (odds-evens (rest lst)))]
[(even? (first lst)) (map + '(0 1) (odds-evens (rest lst)))]))
(module+ test
(check-equal? (odds-evens (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4)))
```

Our initial version of

`odds-evens`

is not*tail recursive*because the result(s) of the recursive calls are processed further before returning (i.e. here passed to`map`

).Complete the following tail recursive function to count the number of odd and even numbers in a list. The general idea is that the recursive call to

`helper`

- reduce the size of the list argument by one, and
- increment exactly one of the arguments
`odd`

and`even`

. This is a very common pattern in Racket, where recursion replaces mutation (i.e. replaces`odds=odds+1`

)

```
(define (odds-evens2 lst)
(define (helper lst odds evens)
(cond
[(empty? lst) (list odds evens)]
[(odd? (first lst)) (helper )]
[(even? (first lst)) (helper )]))
(helper lst 0 0))
(module+ test
(define random-list (build-list 100 (lambda (x) (random 1 100))))
(check-equal? (odds-evens2 (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4))
(check-equal? (odds-evens random-list) (odds-evens2 random-list)))
```

Use the racket debugger to test the stack usage of your function.

save the results of this section in

`~/fcshome/cs2613/labs/L05/odds-evens.rkt`

, and commit this file.

# Part 2: for loops

- Time
- 15 minutes
- Activity
- Group discussion/demo

Although some Racket programmers like a minimalist style using pure tail recursion, many prefer to use for loops

To accumulate values, one Racket library form is

`for/fold`

```
(define (odds-evens3 lst)
(define-values (odds evens)
(for/fold
([odds 0] [evens 0])
([n lst])
(cond
[(odd? n) (values (add1 odds) evens)]
[(even? n) (values odds (add1 evens))])))
(list odds evens))
(module+ test
(check-equal? (odds-evens3 (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4))
(check-equal? (odds-evens random-list) (odds-evens3 random-list)))
```

For this particular example, because we want to return a list, rather than multiple return values, we have to wrap the

`for/fold`

in a bit of glue code; this loses some of the simplicityLet's finish off by comparing the speed of our three implimentations

```
(define big-list (build-list 1000000 identity))
(for* ([fun (list odds-evens odds-evens2 odds-evens3)]
[rep '(1 2 3)])
(display fun)
(displayln rep)
(time (fun big-list)))
```

- add the results of this section to
`~/fcshome/cs2613/labs/L05/odds-evens.rkt`

, and commit your changes.

# Part 3: Racket review

- Time
- 15 minutes
- Activity
- Group discussion

What's new in the first half of today's lab?

- built in functions / forms?
- concepts?
- which of these can you map to other programming languages that you know?

# Part 4 Numerical Integration examples

- Time
- 30 minutes
- Activity
- individuals (you may need your files for next lab)

In this section we'll play a bit with some crude numerical derivative and integral calculation. Don't worry about the calculus too much, this is mainly a chance to reinforce

- tail recursion
- for loops
- higher order functions

We'll also think about about testing numerical functions.

```
#lang racket
(require racket/math)
(module+ test
(require rackunit)
(define epsilon .001))
(define dx 0.001)
(define -2pi (* -2 pi))
(define 2pi (* 2 pi))
;; compute the derivative of `f' at the given point `x'
(define (deriv f x)
(/ (- (f (+ x dx)) (f x)) dx))
;; Integrate a function from 0 to x (using tail recursion)
(define (integrate f x)
(define (loop y acc)
(if (> y x)
(* acc dx)
(loop (+ y dx) (+ acc (f y)))))
(loop 0 0))
```

- In general it's a bad idea to test floating point numbers for exact equality.
`rackunit`

provides`check-=`

exactly for this situation. Choose different values of`epsilon`

and`dx`

to make the following test succeed and fail:

```
(module+ test
(check-= (integrate cos (/ pi 4)) (sin (/ pi 4)) epsilon))
```

- it's a bit (extremely?) boring to test numerical functions if we have to write down all of the input values. The following sets up a bunch of random numbers between 0 and 2pi, and also defines some test functions. Fill in the body of the loop to do many tests.

```
(module+ test
(define test-points (build-list 20 (lambda (x) (* 2 pi (random)))))
(define (sin2 x) (integrate cos x))
(define (cos2 x) (deriv sin x))
(for ([x test-points])
))
```

- The following translation of
`integrate`

to use`for/fold`

is*almost*correct, but missing a kindof sneaky step in the base case. How would you add that in? There are at least two correct solutions, and one obvious-but-wrong solution.

```
(define (integrate2 f x)
(for/fold
([acc 0])
([y (in-range 0 x dx)])
(+ acc (f y))))
(module+ test
(for ([x test-points])
(check-= (integrate cos x) (integrate2 cos x) epsilon)))
```

save the results of this section in

`~/fcshome/cs2613/labs/L05/calculus.rkt`

, and commit this file.push any new commits from this lab.