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

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) 

Answer 2

已经有很多soluitons，他们指出，使用动态编程是一个很好的选择。我认为这可以写得更简单一点。以下是我将作为一个简单的基于列表的解决方案。它是基于观察，如果行n是（a b c d e），那么行n + 1是（a（+ a b）（+ b c）（+ c d）（+ d e）e）。一个容易计算的方法是迭代（0 a b c d e）收集（（+ 0 a）（+ a b）...（+ d e）e）的尾部。

(define (pascal n) 
    (let pascal ((n n) (row '(1))) 
    (if (= n 0) row 
     (pascal (- n 1) 
       (maplist (lambda (tail) 
          (if (null? (cdr tail)) 1 
           (+ (car tail) 
            (cadr tail)))) 
         (cons 0 row)))))) 

(pascal 0) ;=>  (1) 
(pascal 1) ;=> (1 1) 
(pascal 2) ;=> (1 2 1) 
(pascal 3) ;=> (1 3 3 1) 
(pascal 4) ;=> (1 4 6 4 1) 

本作使用的辅助功能MAPLIST的：

(define (maplist function list) 
    (if (null? list) list 
     (cons (function list) 
      (maplist function (cdr list))))) 

(maplist reverse '(1 2 3)) 
;=> ((3 2 1) (3 2) (3))