Design a procedure to reverse a list

Question

SICP exercise 2.18 asks the following:

Exercise 2.18. Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:

(reverse (list 1 4 9 16 25))
(25 16 9 4 1)

I wrote this iterative function:

(define (reverse n)
 (define (iter a b)
 (if (null? a) b
 (iter (cdr a) (cons (car a) b))))
 (iter n null))

I could not think of a way to do this recursively. Is there a better way to write this function? Is it possible to do it recursively?

Answer 1

Here's a recursive definition of reverse (named rev) that uses primitives (car/cdr/cons) and an inner definition of snoc (reverse cons):

(define (rev lis)
 (define (snoc elem lis)
 (if (null? lis)
 (cons elem lis)
 (cons (car lis) (snoc elem (cdr lis)))))
 (if (null? lis)
 lis
 (snoc (car lis) (rev (cdr lis)))))

Obviously, this definition is not meant to be efficient. =)

Answer 2

Not much different from yours, and kind of sloppy with the list mechanics (id generally prefer to use cons over append)

> (define (rev l)
 (if (null? (cdr l))
 l
 (append (rev (cdr l)) (list (car l)))))
> (rev '(1 2 3 4))
(4 3 2 1)

This, on the other hand, i like

(define (rev l) (foldr (lambda (a b) (append b (list a))) l '()))

• jaresty: Interesting. I didn't know about append - how is it different from cons?
• jon_darkstar: gives a proper null-terminated list when both arguments are proper lists
• jon_darkstar: there might be a way with just car/cons/cdr to do the same, but i played around for a while had a hard time making the list come out properly. if you can find a way to tweak mine like that plz let me know
• C. K. Young: @jaresty: append is O(n) on the lengths of all the given lists except the last. cons is O(1).