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 '()))