List Homework
September 7, 2018
We’ve done these before, but it doesn’t hurt to do them again. First, a simple recursive version of the list-length program:
(define (len xs) (if (null? xs) 0 (+ (len (cdr xs)) 1))) > (len '(1 2 3 4 5)) 5
That works, but it’s not tail recursive, because len
isn’t in tail position (it is inside the call to +
), so the function operates in linear time and space; here is a better version:
(define (len-aux xs len) (if (null? xs) len (len-aux (cdr xs) (+ len 1)))) (define (len xs) (len-aux xs 0)) > (len '(1 2 3 4 5)) 5
Now len-aux
is in tail position; the function operates in linear time and constant space. Here we reverse a list, using a tail recursive function:
(define (rev-aux xs zs) (if (null? xs) zs (rev-aux (cdr xs) (cons (car xs) zs)))) (define (rev xs) (rev-aux xs '())) > (rev '(1 2 3 4 5)) (5 4 3 2 1)
You can run the program at https://ideone.com/x46jpU.
Here’s a solution in C.
Example Usage: