[原]Simply Scheme（2）：递归

递归对于函数式编程来说是一个essential，对于所有的遍历都可以使用递归。因此Simply Scheme专门用了一个部分来讲述。至于如何编写递归程序，初学者可以先写一些基本的case，然后逐渐扩展，最终便可以得到递归的程序。而在分析问题时，采用的是把大问题化为规模小一点的同类问题，然后再组合起来。这也就是著名的“分而治之”的方法。闲话少说，看练习题。
11.2 When you teach a class, people will get distracted if you say "um" too many times. Write a count-ums that counts the number of times "um" appears in a sentence:
  > (count-ums '(today um we are going to um talk about the combining um method))
 3
Answer： ;; 高阶函数版本——当然，在keep里也用到了递归
(define (count-ums sent)
  (count (keep (lambda (x)
                 (equal? x 'um))
               sent)))

;; 递归版本
(define (count-ums sent)
  (if (= (count sent) 0)
      0
      (if (equal? (first sent) 'um)
          (+ 1 (count-ums (bf sent)))
          (count-ums (bf sent)))))

;; 尾递归版本

(define (count-ums-iter sent)

  (define (iter r sent)

    (if (= (count sent) 0)

        r

        (iter (if (equal? (first sent) 'um) (+ 1 r) r) (bf sent))))

  (iter 0 sent))

11.3  Write a procedure phone-unspell that takes a spelled version of a phone number, such as POPCORN, and returns the real phone number, in this case 7672676.
Answer：
(define (phone-unspell wd)
  (if (empty? wd)
      ""
      (word (unspell-letter (first wd))
          (phone-unspell (bf wd)))))

11.5  Write a procedure initials that takes a sentence as its argument and returns a sentence of the first letters in each of the sentence's words:

> (initials '(if i needed someone)) (I I N S)
Answer：
(define (initials sent)
  (if (empty? sent)
      '()
      (se (first (first sent))
          (initials (bf sent)))))

;; Tail recursion version

(define (initials-iter sent)

  (define (iter r sent)

    (if (empty? sent)

        r

        (iter (se r (first (first sent))) (bf sent))))

  (iter '() sent))

11.6  Write a procedure countdown that works like this:

> (countdown 10) (10 9 8 7 6 5 4 3 2 1 BLASTOFF!) > (countdown 3) (3 2 1 BLASTOFF!)
Answer：
(define (countdown num)
   (cond ((= num 0) 'blastoff!)
         ((> num 0) (se num
                        (countdown (- num 1))))
         (else 'error!))) 

;; Tail recursion

(define (countdown-iter num)

  (define (iter r num)

    (cond ((= num 0) (se r 'blastoff!))

          ((> num 0) (iter (se r num) (- num 1)))

          (else 'error!)))

  (iter '() num))

11.7  Write a procedure copies that takes a number and a word as arguments and returns a sentence containing that many copies of the given word:

> (copies 8 'spam) (SPAM SPAM SPAM SPAM SPAM SPAM SPAM SPAM)
Answer：
(define (copies num wd)
  (if (= num 0)
      '()
      (se wd
          (copies (- num 1)
                  wd))))

12.1  Here is a definition of a procedure that returns the sum of the numbers in its argument sentence:

(define (addup nums) (if (empty? (bf nums)) (first nums) (+ (first nums) (addup (bf nums)))))

Although this works, it could be simplified by changing the base case. Do that.

Answer：
(define (addup nums)
  (if (empty? nums)
      0
      (+ (first nums)
         (addup (bf nums)))))

12.2  Fix the bug in the following definition:

(define (acronym sent) ;; wrong
 (if (= (count sent) 1)
     (first sent)
     (word (first (first sent))
           (acronym (bf sent)))))
Answer：
(define (acronym sent)
  (if (empty? sent)
      ""
      (word (first (first sent))
            (acronym (bf sent)))))

12.8  Write a procedure numbers that takes a sentence as its argument and returns another sentence containing only the numbers in the argument:

> (numbers '(76 trombones and 110 cornets)) (76 110)
Answer:
(define (numbers sent)
   (if (empty? sent)
   '()
   (se (if (number? (first sent))
           (first sent)
           '())
       (numbers (bf sent)))))

12.10  Write a procedure remove that takes a word and a sentence as arguments and returns the same sentence, but with all copies of the given word removed:

> (remove 'the '(the song love of the loved by the beatles)) (SONG LOVE OF LOVED BY BEATLES)
Answer:
(define (remove wd sent)
   (if (or (empty? wd) (empty? sent))
       sent
       (se (if (equal? wd
                       (first sent))
               '()
               (first sent))
           (remove wd (bf sent)))))
12.11  Write the procedure count, which returns the number of words in a sentence or the number of letters in a word. Answer：
(define (count thing)
   (if (empty? thing)
       0
       (+ 1 (count (bf thing))))))

12.13  Write a new version of the describe-time procedure from Exercise . Instead of returning a decimal number, it should behave like this:

> (describe-time 22222) (6 HOURS 10 MINUTES 22 SECONDS)
> (describe-time 4967189641) (1 CENTURIES 57 YEARS 20 WEEKS 6 DAYS 8 HOURS 54 MINUTES 1 SECONDS)

Can you make the program smart about saying 1 CENTURY instead of 1 CENTURIES? 

Answer：

(define (plural num wd)
  (cond ((or (empty? wd) (empty? num)) "")
    ((or (= num 0) (= num 1)) (se num wd))
    ((> num 1) (se num (if (equal? wd 'century)
                   'centuries
                   (word wd 's))))
    (else 'error)))

(define (unit n)
  (item n '(second minute hour day week year century)))

(define (mod n)
  (item n '(60 60 24 7 52 100 1)))

(define (plural num wd)
  (cond ((or (empty? wd) (empty? num)) "")
    ((or (= num 0) (= num 1)) (se num wd))
    ((> num 1) (se num (if (equal? wd 'century)
                   'centuries
                   (word wd 's))))
    (else 'error)))

(define (unit n)
  (item n '(second minute hour day week year century "")))

(define (mod n)
  (item n '(60 60 24 7 52 100)))

(define (describe-time nsec)
  (define (iter n sec)
     (cond ((and (= n 0) (= sec 0)) '(0 second)) ; 参数为0时
       ((or (= sec 0) (= n 8)) '()) ; 计算完毕
       ((= n 7) (plural sec (unit n))) ; Base case
       (else (se (iter (+ n 1) (/ (- sec (modulo sec (mod n)))
                      (mod n)))
             (plural (modulo sec (mod n)) (unit n))))))
   (iter 1 nsec))

很显然，(describe-time 4967189641)的结果并不如题中所示。计算过程如下：

4967189641 sec = 82786494 min 1 sec

82786494 min = 1379774 hr 54 min

1379774 hr = 57490 d 14 hr

57490 d = 8212 w 6 d

8212 w = 157 y 48 w

157 y = 1 century 57 y

因此应该是(1 century 57 years 48 weeks 6 days 14 hours 54 minutes 1 second)

14.1  > (remove-once 'morning '(good morning good morning)) (GOOD GOOD MORNING)
Answer:
;; keep pattern
 (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)
这道题起初我没有做对，因为没有注意到需要使用helper。这是个accumulate pattern:
(define (up-n rem wd)
  (if (= rem 0)
      '()
      (se (up-n (- rem 1) (bl wd))
          wd)))

(define (up wd)
  (up-n (count wd) wd))

;; 用尾递归就简单多了！：

(define (up wd)

  (define (iter r wd)

    (if (= (count wd) 0)

        r

        (iter (se r 

                  (word (if (empty? r)

                            ""

                            (last r))

                        (first wd)))

              (bf wd))))

  (iter '() wd))