SICP练习1.12生成帕斯卡三角形

这道练习的中文版翻译有误，原文是『...Write a procedure that computes elements of Pascal’s triangle by means of a recursive process.』，译文只翻译了『。。。它采用递归计算过程计算出帕斯卡三角形。』，这里应该是『帕斯卡三角形的各个元素』才对。

在SICP解题集中，作者分别展示了用递归计算过程和迭代计算过程来求出一个值的过程，该值是帕斯卡三角形第row行的第col个元素的数值，过程接收row和col两个参数。

我自己的想法是，我希望写出一个过程，它接收一个正整数，求值出一个n个元素的表，表的第x(1 <= x <= n)个元素是帕斯卡三角形第x层的元素表。

于是我首先define一个过程，把它命名为pasika（没错，就是帕斯卡的拼音哈哈），它接收形参n，求值出1~n层的帕斯卡三角形，并将它们按递增顺序装入一个表中。

为了实现它，我用“按愿望思维”的策略。

我先假定有那么一个中间过程pasika-n-list，它接收形参N，求值出帕斯卡三角形的第N层的所有数值，并组成一个表；

然后我又假定有一个过程pasika-list，它接收形参a和b，返回帕斯卡三角形从a层到b层元素表的表。如此一来过程pasika就可以这样定义：

       (define (pasika n) 
            (pasika-list 1 n))

然后pasika-list过程也可以这样定义：

        (define (pasika-list a b) 
            (if (or (< a b) (= a b)) 
                (cons (pasika-n-list a) (pasika-list (+ 1 a) b))
                nil))

其含义是，如果参数a<b或者a=b，那么就组合起第a层的表和从第a+1层表到b层表的表，否则返回nil。

接下来考虑pasika-n-list的实现，同样“按愿望思维”，

假定有个过程pasika-n-list-recursive，它接收参数s和一个表before-list，表before-list代表上一层的表，该过程返回一个before-list下一层所有元素的表，s是一个计数器，当s为0时该过程返回nil充当表尾，其他情况则是用于组合起该层第s个元素；

然后再假定一个过程nlist-recursive，它相似的接收一个参数a和一个表before-list，返回第N层的第a个元素，可以把它定义在pasika-n-list里面，这样它的参数N就对nlist-recursive是*变量（“词法作用域”）。

现在的问题在于，如何知道帕斯卡三角形任意一层的任意一个元素的数值呢？

我们知道帕斯卡三角形每一层的第一个和最后一个元素的数值是1，其他数值则是其上一层对应元素和之前一个元素的和。

于是我们可以假定有个过程no. ，它接收一个表llist和参数k，求值出表llist的第k个元素，这样就可以定义过程nlist-recursive:

         (define (nlist-recursive a before-list)  
             (if (or (= a 1) (= a N)) 
                 1
                 (+ (no. before-list (- a 1))
                    (no. before-list a))))

no.过程可以直接定义：

            (define (no. llist k) 
                (cond ((null? llist) nil) 
                      ((= k 1) (car llist)) 
                      (else (no. (cdr llist) (- k 1)))))

接下来pasika-n-list-recursive也可以这样定义了：

  (define (pasika-n-list-recursive s before-list)  
                (cond ((= s 0) nil)
                      (else (cons (nlist-recursive s before-list)
                                (pasika-n-list-recursive (- s 1) before-list)))))

最后，定义pasika-n-list如下：

   (define (pasika-n-list N)           
       (cond ((= N 1) (list 1))
             ((= N 2) (list 1 1))
             (else (pasika-n-list-recursive N (pasika-n-list (- N 1)))))) 

把代码整合一下，整体就出来了。

     (define (pasika n) 
        (define (pasika-n-list N)  
    
            (define (no. llist k)  
                (cond ((null? llist) nil) 
                      ((= k 1) (car llist)) 
                      (else (no. (cdr llist) (- k 1)))))
        
            (define (nlist-recursive a before-list) 
                (if (or (= a 1) (= a N)) 
                    1
                    (+ (no. before-list (- a 1))
                    (no. before-list a))))
    
            (define (pasika-n-list-recursive s before-list)  
                (cond ((= s 0) nil)
                      (else (cons (nlist-recursive s before-list)
                                (pasika-n-list-recursive (- s 1) before-list)))))
    
            (cond ((= N 1) (list 1))
                  ((= N 2) (list 1 1))
                  (else (pasika-n-list-recursive N (pasika-n-list (- N 1))))))
    
    
            
        (define (pasika-list a b)     
            (if (or (< a b) (= a b)) 
                (cons (pasika-n-list a) (pasika-list (+ 1 a) b))
                nil))
                
        
    
            (pasika-list 1 n))

在Racket上运行一下，效果如图