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 tomap
).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
andeven
. This is a very common pattern in Racket, where recursion replaces mutation (i.e. replacesodds=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.