recursion - 有没有更有效的方法来编写这个递归过程？

Question

我被要求编写一个程序，通过递归过程来计算帕斯卡三角形的元素。我可以创建一个过程，返回三角形中的单行或特定行中的数字。

这是我的解决方案:

(define (f n)
  (cond ((= n 1) '(1))
        (else
         (define (func i n l)
           (if (> i n)
               l
               (func (+ i 1) n (cons (+ (convert (find (- i 1) (f (- n 1))))
                                        (convert (find i (f (- n 1)))))
                                     l))))
         (func 1 n '()))))

(define (find n l)
  (define (find i n a)
    (if (or (null? a) (<= n 0))
        '()
        (if (>= i n)
            (car a)
            (find (+ i 1) n (cdr a)))))
  (find 1 n l))

(define (convert l)
  (if (null? l)
      0
      (+ l 0)))

这似乎工作正常，但查找以 (f 8) 开头的较大行的元素确实效率很低。有没有更好的程序通过递归过程来解决这个问题？

另外，如果我想使用迭代过程(尾递归)，我该如何编写它？

Answer 1

优化算法的方法有多种，最好的方法之一是使用 dynamic programming有效地计算每个值。这是我自己的solution类似的问题，其中包括更好地理解这种方法的引用资料 - 这是一个尾递归的迭代过程。关键点是它使用变异操作来更新预先计算值的向量，并且调整实现以打印给定行的列表是一件简单的事情:

(define (f n)
  (let ([table (make-vector n 1)])
    (let outer ([i 1])
      (when (< i n)
        (let inner ([j 1] [previous 1])
          (when (< j i)
            (let ([current (vector-ref table j)])
              (vector-set! table j (+ current previous))
              (inner (add1 j) current))))
        (outer (add1 i))))
    (vector->list table)))

或者，借用 @Sylwester 的 solution我们可以编写一个纯函数式尾递归迭代版本，它使用列表来存储预先计算的值；在我的测试中，这比以前的版本慢:

(define (f n)
  (define (aux tr tc prev acc)
    (cond ((> tr n) '())          
          ((and (= tc 1) (= tr n))
           prev)
          ((= tc tr)
           (aux (add1 tr) 1 (cons 1 acc) '(1)))
          (else 
           (aux tr
                (add1 tc) 
                (cdr prev)
                (cons (+ (car prev) (cadr prev)) acc))))) 
  (if (= n 1)
      '(1)
      (aux 2 1 '(1 1) '(1))))

无论哪种方式，对于较大的输入，它都能按预期工作，对于 n 来说速度会很快。值约为几千个:

(f 10)
=> '(1 9 36 84 126 126 84 36 9 1)