1
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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. =)

\$\endgroup\$
0
\$\begingroup\$

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 '()))
\$\endgroup\$
  • \$\begingroup\$ Interesting. I didn't know about append - how is it different from cons? \$\endgroup\$ – jaresty Apr 5 '11 at 6:28
  • \$\begingroup\$ gives a proper null-terminated list when both arguments are proper lists \$\endgroup\$ – jon_darkstar Apr 5 '11 at 6:32
  • \$\begingroup\$ 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 \$\endgroup\$ – jon_darkstar Apr 5 '11 at 6:40
  • \$\begingroup\$ @jaresty: append is O(n) on the lengths of all the given lists except the last. cons is O(1). \$\endgroup\$ – Chris Jester-Young Apr 5 '11 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.