[原]Simply Scheme（4）：高级递归

分而治之，然后组合子问题的解答，就是整个问题的解答，这就是递归的真谛。

注意，当返回值为逻辑值时，accumulate模式没有明显的accumulate，也可以有，如palindrome？、substring?此时需要搞明白base case所代表的意义。

15.1  Write a procedure to-binary:

> (to-binary 9)
 1001
 > (to-binary 23)
 10111
 Answer:
(define (to-bin num)
   (if (= num 0)
       ""
       (word (to-bin (/ (- num (modulo num 2)) 2))
             (modulo num 2))))

;; Tail Recursion

(define (to-bin num)

  (define (iter r num)

    (if (= num 0)

        r

        (iter (word (remainder num 2) r) (/ (- num (remainder num 2)) 2))))

  (iter "" num))

15.2  A "palindrome" is a sentence that reads the same backward as forward. Write a predicate palindrome? that takes a sentence as argument and decides whether it is a palindrome. For example:

> (palindrome? '(flee to me remote elf)) #T > (palindrome? '(flee to me remote control)) #F

Do not reverse any words or sentences in your solution.

(define (palindrome? sent)

  (define (to-word st)

    (if (empty? st)

""

(word (first st)

     (to-word (bf st)))))

  (define (iter result wd)

    (if (or (not result)

   (empty? wd)

   (empty? (bf wd))

   (empty? (bl wd)))

 result

 (iter (and result (equal? (first wd) (last wd)))

(bf (bl wd)))))

  (iter #t (to-word sent)))

或者：

(define (palindrome? sent)

  (define (to-word sent)

    (if (empty? sent)

        ""

        (word (first sent)

              (to-word (bf sent)))))

  (let ((wrd (to-word sent)))

    (cond ((empty? wrd) #f)

((= (count wrd) 1) #t)

((= (count wrd) 2) (equal? (first wrd) (last wrd)))

(else (and (equal? (first wrd) (last wrd))

  (palindrome? (bf (bl wrd))))))))

后者会对整个sent做递归，而前者一旦遇到否定的情况便会退出。--也可以使用continuation来退出，不过我不熟悉，因此不给出实现。

;; Tail Recursion

(define (se-to-wd st)

  (define (iter st r)

    (if (empty? st)

        r

        (iter (bf st) (word r (first st)))))

  (iter st ""))

(define (palindrome? st)

  (let ((wd (se-to-wd st)))

    (define (iter r w)

      (if (or (<= (count w) 1) (not r))

          r

          (iter (and r (equal? (first w) (last w))) (bl (bf w)))))

    (iter #t wd)))

15.3  Write a procedure substrings that takes a word as its argument. It should return a sentence containing all of the substrings of the argument. A substring is a subset whose letters come consecutively in the original word. For example, the word bat is a subset, but not a substring, of brat.

(define (substrings wd)
  (if (empty? wd)
      '()
      (se (substrings (bf wd))
          (up wd))))

15.4  Write a predicate procedure substring? that takes two words as arguments and returns #t if and only if the first word is a substring of the second. (See Exercise 15.3 for the definition of a substring.)

Be careful about cases in which you encounter a "false start," like this:

> (substring? 'ssip 'mississippi) #T

and also about subsets that don't appear as consecutive letters in the second word:

> (substring? 'misip 'mississippi) #F

(define (substring? wd1 wd2)

  (define (subst wd n)

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

        ""

        (word (first wd)

              (subst (bf wd) (- n 1)))))

  (if (or (empty? wd1) (empty? wd2))

      #f

      (if (equal? wd1 (subst wd2 (count wd1)))

          #t

          (substring? wd1 (bf wd2)))))

15.5  Suppose you have a phone number, such as 223-5766, and you'd like to figure out a clever way to spell it in letters for your friends to remember. Each digit corresponds to three possible letters. For example, the digit 2 corresponds to the letters A, B, and C. Write a procedure that takes a number as argument and returns a sentence of all the possible spellings:

> (phone-spell 2235766) (AADJPMM AADJPMN …CCFLSOO)

(We're not showing you all 2187 words in this sentence.) You may assume there are no zeros or ones in the number, since those don't have letters.

Hint: This problem has a lot in common with the subsets example.

这题有些难度。分析如下：

先不考虑将数字转换成字母。假定有两个数字的电话号码，得到的句子为：'(pqrs abc)

那么phone-spell的结果应该是：'(pa qa ra sa pb qb rb sb pc qc rc sc)

计算过程如下：

1. base case：将第一个单词拆分成句子'(p q r s)
2. 然后将第二个单词的第一个字母分别添加到该句子的每个单词后：'(pa qa ra sa)
3. 将第二个单词的第二个字母分别添加到该句子的每个单词后：'(pb qb rb sb)
4. ……
5. 将这些句子串接起来
6. 用递归的思想实现就是将为完成部分的每个单词分配到已完成的部分所得到的结果中去。

其中，2～5是由dist函数实现的，而6使用ps-sent函数，即使用句子作为参数的phone-spell的版本

我们首先需要一些helper函数：

;; 将数字转换成单词（此处应该有判断，数字的长度为1）

(define (phone-letter num)

  (item num '("" abc def ghi jkl mno pqrs tuv wxyz)))

;; 将一串数字转换成句子：

(define (phone-sent num)

  (if (empty? num)

      (se '())

      (se (phone-letter (first num)) (phone-sent (bf num)))))

当只有一个数字时，phone-spell应该返回其对应单词的单个字母组合，即'abc转换为'(a b c)，'pqrs则被转换为'(p q r s)；当有两个单词时，首先第一个被拆分，如前所述，然后将第二个单词的每个字母依次分配给句子中的每个单词。因此，我们需要一个函数将单词中的每个字母依次分配给现有句子中的每个单词：

(define (dist sent wd)

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

      '()

      (se (append-every (first wd) sent)

           (dist sent (bf wd)))))

这样就得到了将一个句子作为参数的phone-spell（这里叫做ps-sent）：

(define (ps-sent sent)

  (cond ((empty? sent) sent)

        ((= (count sent) 1) (dist (empty-word-sent (count sent)) (first sent)))

        (else (dist (ps-sent (bl sent))

                    (last sent)))))

注意到当sent中只有一个单词的情况。此时不能用'()作为参数调用dist函数，而应该使用包含n个空单词的句子——此处n为单词的长度，因此，此时需要一个helper来生成n个空单词的句子：

(define (empty-word-sent n)

  (if (= n 0)

      '()

      (se "" (empty-word-sent (- n 1)))))

最终，将这些函数组合起来实现phone-spell：

(define (phone-spell num)

  (let ((sent (phone-sent num)))

    (ps-sent sent)))

×××××××××××××××××××××××××××××××××

×Simply Scheme的学习暂时告一段落了，工作第一：毕竟是养家糊口的×

×××××××××××××××××××××××××××××××××