有沒有更有效的方法來編寫這個遞歸過程？

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))