UNB/ CS/ David Bremner/ teaching/ cs4613/ tutorials/ Tail recursion in racket
Prerequisites
recursion, tests
```    #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.