[原]Simply Scheme（3）：递归模式

三种基本递归模式：

• every：对每个元素进行递归操作并保留
• keep：保留其中某些递归结果
• accumulate：将递归结果组合起来

在实际使用中，经常会将其中的一些模式组合起来。

14.1  

> (remove-once 'morning '(good morning good morning)) (GOOD GOOD MORNING)

Answer:

;; Keep模式。

;; 分部法

;; 判断句子第一个单词是否与目标单词相等，

;; 如果是，则返回除了第一个单词外的所有单词；

;; 如果不是，则将第一个单词保留下来，再对剩下的句子递归执行remove-once操作

;; 该方式是将句子分成两部分：一部分已完成，无目标单词，第二部分未完成，含目标单词。

;; 一旦发现目标单词，则忽略该单词，完成删除一次操作，将剩余句子添加到完成部分。

(define (rm-once wd sent)

   (cond ((or (empty? wd) (empty? sent)) sent)

         ((equal? wd (first sent)) (bf sent))

         (else (se (first sent)

                      (rm-once wd (bf sent))))))

14.2  

> (up 'town) (T TO TOW TOWN)

;; Accumulate模式

;; 直观方法：（从头部开始）

;; 如'town => (t)和'town => (t to)和'town……

;; 1、编写sub-word-n函数，取一个单词的前n个字符

(define (sub-word-n wd n)

  (if (= n 0)

      ""

      (word (first wd)

                 (sub-word-n (bf wd) (- n 1)))))

;; 2、从1开始，到单词的长度为止，串接所有的sub-word-n为句子

(define (up-m wd n m)

  (if (> n m)

      '()

      (se (sub-word-n wd n)

           (up-m wd (+ n 1) m))))

;; 3、使用up-m来实现up：

(define (up wd)

  (up-n wd 1 (count wd)))

;; 从尾部开始的方法：

;; 假设后部是已完成的部分，前部是未完成部分，

;; 则只需要将前部的最后一个单词添加到已完成的句子里

;; 如：'tow和(town) => 'tw和(tow town)。代码如下：

(define (down-n rem wd)

  (if (= rem 0)

      '()

      (se (down-n (- rem 1) (bl wd))

            wd)))

(define (up wd)

  (down-n (count wd) wd))

14.3  

> (remdup '(ob la di ob la da)) ;; remove duplicates (OB LA DI DA)

(It's okay if your procedure returns (DI OB LA DA) instead, as long as it removes all but one instance of each duplicated word.)

Answer：

;; Keep模式

;; 采用高阶函数：

;; using high order function

(define (rm-dup sent)

  (if (empty? sent)

      '()

      (se (first sent)

          (rm-dup (keep (lambda (x)

                                     (not (equal? (first sent) x)))

                        (bf sent))))))

;; 采用直观方法：从第一个单词开始，到最后一个单词，每次将其后的句子中的该单词删除

;; 采用数学函数表示则为：

;; rm-dup(x) =

;; concatenate(first(x),

;;             rm-dup(rm-all(first(x),

;;                           but-first(x))))

(define (rm-all wd sent)

  (if (or (empty? wd) (empty? sent))

      sent

      (se (if (equal? wd (first sent))

              '()

              (first sent))

          (rm-all wd (bf sent)))))

(define (rm-dup sent)

  (if (empty? sent)

      '()

      (se (first sent)

          (rm-dup (rm-all (first sent)

                          (bf sent))))))

;; 将句子分成done（删除重复单词）和not-done两个部分。每次从not-done部分取第一个单词，如果不在done部分，则添加到done部分，否则取not-done下一个单词。

;; cat-new(done, not-done) =

;; cat-new(concatenate(done,

;;                     new-word(first(not-done))),

;;         but-first(not-done))

(define (rm-dup sent)

  (define (cat-new done not-done)

    (if (empty? not-done)

        done

        (cat-new (se done

                     (if (member? (first not-done)

                                  done)

                         '()

                         (first not-done)))

                 (bf not-done))))

  (cat-new '() sent))

14.4  

> (odds '(i lost my little girl)) (I MY GIRL)

Answer：

;; keep模式。无难度(define (odds sent) (if (< (count sent) 2) sent (se (first sent) (odds (bf (bf sent))))))

14.5  Write a procedure letter-count that takes a sentence as its argument and returns the total number of letters in the sentence:

> (letter-count '(fixing a hole)) 11

Answer：

;; Accumulate模式。无难度

(define (letter-count sent)

  (if (= (count sent) 0)

      0

      (+ (count (first sent))

         (letter-count (bf sent)))))

14.6  Write member?.

Answer：

(define (member? thing1 thing2)

  (cond ((or (empty? thing1) (empty? thing2)) #f)

        ((equal? thing1 (first thing2)) #t)

        (else (member? thing1 (bf thing2)))))

14.7  Write differences, which takes a sentence of numbers as its argument and returns a sentence containing the differences between adjacent elements. (The length of the returned sentence is one less than that of the argument.)

> (differences '(4 23 9 87 6 12)) (19 -14 78 -81 6)Answer：;; Accumulate

(define (differences nums)

  (let ((ns (keep number? nums)))

        (if (<= (count ns) 1)

            '()

            (se (- (first (bf ns)) (first ns))

                (differences (bf ns))))))

;; Accumulate

14.8  Write expand, which takes a sentence as its argument. It returns a sentence similar to the argument, except that if a number appears in the argument, then the return value contains that many copies of the following word:

> (expand '(4 calling birds 3 french hens)) (CALLING CALLING CALLING CALLING BIRDS FRENCH FRENCH FRENCH HENS) > (expand '(the 7 samurai)) (THE SAMURAI SAMURAI SAMURAI SAMURAI SAMURAI SAMURAI SAMURAI)

(define (expand-n n wd)

  (if (or (= n 0) (empty? wd))

      '()

      (se wd

          (expand-n (- n 1) wd))))

(define (expand sent)

  (cond ((empty? sent) sent)

        ((and (number? (first sent))

              (= (count sent) 1)) '())

        ((not (number? (first sent))) (se (first sent)

                                          (expand (bf sent))))

        (else (se (expand-n (first sent) (first (bf sent)))

                  (expand (bf (bf sent)))))))

14.9  Write a procedure called location that takes two arguments, a word and a sentence. It should return a number indicating where in the sentence that word can be found. If the word isn't in the sentence, return #f. If the word appears more than once, return the location of the first appearance.

> (location 'me '(you never give me your money))

 4

Answer:

;; Accumulation

(define (location wd sent)

  (define (iter n sent)

     (cond ((or (empty? wd) (empty? sent)) #f)

               ((equal? wd (first sent)) n)

               (else (iter (+ n 1) (bf sent)))))

 (iter 1 sent))

14.12  Write a procedure progressive-squares? that takes a sentence of numbers as its argument. It should return #t if each number (other than the first) is the square of the number before it:

> (progressive-squares? '(3 9 81 6561)) #T > (progressive-squares? '(25 36 49 64)) #F
Answer：
;; Accumulate模式，需要对初始值进行设置。预设为#t，对于空的句子返回#f。当只剩一个数时返回结果
;; 一旦出现不满足条件的情况，立刻返回#f。否则，将所有每次执行结果用and来执行accumulate操作
(define (progressive-squares? sent)
(let ((nums (keep number? sent)))
(define (iter result st)
(cond ((empty? st) #f)
((not result) #f)
((= (count st) 1) result)
(else (and result
(iter (equal? (square (first st))
(first (bf st)))
(bf st))))))
(iter #t nums)))

或者：

(define (prg-sq sent)

  (cond ((empty? sent) #f)

        ((<= (count sent) 2) (equal? (square (first sent)) (last sent)))

        (else (and (equal? (square (first sent)) (first (bf sent)))

                   (prg-sq (bf sent))))))

14.14  Write a predicate same-shape? that takes two sentences as arguments. It should return #t if two conditions are met: The two sentences must have the same number of words, and each word of the first sentence must have the same number of letters as the word in the corresponding position in the second sentence.

> (same-shape? '(the fool on the hill) '(you like me too much))
 #T
 > (same-shape? '(the fool on the hill) '(and your bird can sing))
 #F

(define (same-shape? sent1 sent2)
(define (iter result st1 st2)
(cond ((not (= (count st1) (count st2))) #f)
((empty? st1) result)
(else (and result
(iter (= (count (first st1))
(count (first st2)))
(bf st1)
(bf st2))))))
(iter #t sent1 sent2))

或者：

(define (same-shape? sent1 sent2)

  (if (not (equal? (count sent1) (count sent2)))

      #f

      (if (empty? sent1)

          #t

          (and (equal? (count (first sent1)) (count (first sent2)))

               (same-shape? (bf sent1) (bf sent2))))))

14.15   Write merge, a procedure that takes two sentences of numbers as arguments. Each sentence must consist of numbers in increasing order. Merge should return a single sentence containing all of the numbers, in order. (We'll use this in the next chapter as part of a sorting algorithm.)

> (merge '(4 7 18 40 99) '(3 6 9 12 24 36 50))
 (3 4 6 7 9 12 18 24 36 40 50 99) (define (merge sent1 sent2)
(cond ((empty? sent1) sent2)
((empty? sent2) sent1)
((< (first sent1) (first sent2)) (se (first sent1)
(merge (bf sent1) sent2)))
(else (se (first sent2)
(merge sent1 (bf sent2))))))

注意，当返回值为逻辑值时，accumulate模式没有明显的accumulate，也可以有，如progressive-square、same-shape?