## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.27

## Problem

Modify your `reverse` procedure of exercise 2.18 to produce a
`deep-reverse` procedure that takes a list as argument and returns as
its value the list with its elements reversed and with all sublists
`deep-reverse`d as well. For example,

(define x (list (list 1 2) (list 3 4))) x

*Output:*

`
`

((1 2) (3 4))

(reverse x)

*Output:*

`
`

((3 4) (1 2))

(deep-reverse x)

*Output:*

`
`

((4 3) (2 1))

## Solution

Here's the definition of `reverse` from our answer to exercise 2.18:

(define nil (quote ())) (define (reverse items) (if (null? items) nil (append (reverse (cdr items)) (cons (car items) nil))))

Here's an implementation of `deep-reverse`:

(define (deep-reverse x) (cond ((null? x) nil) ((pair? x) (append (deep-reverse (cdr x)) (cons (deep-reverse (car x)) nil))) (else x)))

Note that when `x` is a pair, the procedure makes a list of the
results of applying `deep-reverse` to `(car x)`, before applying `append`.
This behavior mirrors that of procedure `reverse`. `append` expects its
2nd argument to be a list, but removes the list structure of that
argument when forming its result. When `(car x)` is itself a list, we
need to encapsulate it in another list to retain its list structure
during the `append` operation; otherwise, all sublists in the list
will be "flattened" into a single list by `append`, which isn't the
behavior we want. Of course, this code also does the right thing
when `x` is not a pair, since in that case `deep-reverse` simply returns
`x`.

Test:

(deep-reverse x)

*Output:*

`
`

((4 3) (2 1))

(define y (list 1 2 (list 3 4))) y

*Output:*

`
`

(1 2 (3 4))

(deep-reverse y)

*Output:*

`
`

((4 3) 2 1)

(define z (list (list 1) (list 2) 3 (list 4))) z

*Output:*

`
`

((1) (2) 3 (4))

(deep-reverse z)

*Output:*

`
`

((4) 3 (2) (1))

(define w (list (list (list 1 2) 3) (list (list (list 4))))) w

*Output:*

`
`

(((1 2) 3) (((4))))

(deep-reverse w)

*Output:*

`
`

((((4))) (3 (2 1)))