SICP 全笔记

Exercise 2.27. 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-reversed as well. For example,

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

x
((1 2) (3 4))

(reverse x)
((3 4) (1 2))

(deep-reverse x)
((4 3) (2 1))

需要深度递归的过程，都需要处理三种情况：

  1. 当前表为空的时候：有了这种情况的处理，递归就不会无限循环下去
  2. 第一项不为 pair：第一项为原子 atom? 时的处理。
  3. 第一项为 pair：第一项为序对时的处理。

《The Little Schemer》简洁明了地介绍了写递归函数需要考虑的问题，这一整本书都在教如何写递归。对话风格，简洁明了，强烈推荐。

(define (deep-reverse lst)
  (cond ((null? lst) '())
        ((not (pair? (car lst))) ; atom?
         (append (deep-reverse (cdr lst)) (list (car lst))))
        (else  ; else
         (append (deep-reverse (cdr lst))
                 (list (deep-reverse (car lst)))))))


;;; tests begin
(load "../testframe.scm")

(assertequal? (deep-reverse '((1 2 3 (4 5)) (6 7)))
              '((7 6) ((5 4) 3 2 1)))

(let ((x (list (list 1 2) (list 3 4))))
  (assertequal? (deep-reverse x)
                '((4 3) (2 1))))