[原]重新开始学习Scheme（9）：杨辉（Pascal）三角

一个杨辉三角如下所示：

为了计算某个位置上的值：

(define pascal-triangle
  (lambda (row col)
    (cond ([or (= row 0) (= col 0)] 0)
          ([= row col] 1)
          (else (+ (pascal-triangle (- row 1) (- col 1))
                   (pascal-triangle (- row 1) col))))))

没错，这是个树形递归，会占用较大的空间。那么，来考虑一下通用的情况：

f(0,0) = 0

f(0,1) = 0

f(1,1) = f(0,1)+f(0,0)

f(2,1) = f(1,1)+f(1,0)

f(2,2) = f(1,2)+f(1,1)

f(3,1) = f(2,1)+f(2,0)

f(3,2) = f(2,2)+f(2,1)

...

f(m-1,n-1) = f(m-2,n-1)+f(m-2,n-2)

f(m-1,n) = f(m-2,n)+f(m-2,n-1)

f(m,n) = f(m-1,n)+f(m-1,n-1)

f(m+1,n) = f(m,n)+f(m,n-1)

可以看出，每一次计算下一个值的时候，都无法完全使用上一步计算的结果，所以到目前为止我还没有找到一种使用尾递归的方式来改写这个函数。如果哪位同学能够用尾递归方式解出来，请及时通知我。

为了打印出杨辉三角，需要用两个循环变量来控制行和列的循环。每次增加一行，就需要对该行的每一列进行输出，知道行、列值相等。如下：

(define p-t
  (lambda (n)
    (let iter ([i 1] [j 1])
      (when (< i (+ n 1))
        (display (pascal-triangle i j)) (display " ")
        (if (= i j)
            (begin (newline) (iter (+ i 1) 1))
            (iter i (+ 1 j)))))))

此处i为行号，j为列号。(p-t 8)结果如下：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

再次考虑是否能使用尾递归：

由于Scheme提供do来完成循环，且可以利用尾递归——其实，使用do编写尾递归的关键因素是找到循环不变式，但目前我没有找到：使用do来考虑上面的结果，如果要计算出第7行第3列的15，需要保存上一步的两个计算结果5和10，而为了得到5，又需要保存其上一步的结果1和4，为了得到10，又需要保存其上一步的结果6和4，此时需保存的结果变为3个。考虑第8行第4列的35，最多的时候需要保存第5行的所有5个结果。由于每一步保存结果个数不一样，因此这种方式的尾递归行不通。