SICP -练习1.12 -pascal三角

Question

来自国际预防犯罪中心：

练习1.12:下面的数字模式称为Pascal三角形。1 1 1 1 2 1 1 3 3 1 4 6 4 1 。。.三角形边的数字都是1，三角形内的每一个数都是上面两个数的之和。编写一个通过递归过程计算Pascal三角形元素的过程。

这是我的代码：

(define (pascals-triangle row col)
  ;; "The numbers at the edge of the triangle are all 1"
  (if (or (= col 0) (= col row))
      1
      (+ (pascals-triangle (- row 1)
                            (- col 1))
          (pascals-triangle (- row 1)
                            col))))

我注意到，三角形后面的边(可能)总是行数，因为我们在进入下一行时总是添加1。所以我重写了代码，只做了一点小小的改动。

(define (pascals-triangle row col)
  (cond ((or (= col 0) (= col row))
         1)
        ((or (= col 1) (= col (- row 1)))
         row)
      (else (+ (pascals-triangle (- row 1)
                                  (- col 1))
                (pascals-triangle (- row 1)
                                  col)))))

在前面的代码中，如果colum为0，则运行时间为常量。现在，在修改后的代码中，如果列为1，它也是常量。由于这是递归的，我猜我保存了几个步骤。这样的小改动对我的代码和系统会产生比这更大的影响吗？

如何改进这段代码？

Answer 1

您应该回溯递归调用，以使其更快。因为每个值都有一个计算兄弟(它的值来自(一个或两个)父级，其中每个父母也有另一个子值)，所以您可以删除可能发生的双重计算。

此外，这些双重计算实际上会以指数方式累积，因此它不再仅仅是一种微观优化；它实际上会影响您的运行时复杂性。所以更重要的是实施回忆录。