Scheme中的尾递归帕斯卡三角形

Question

我最近开始阅读SICP，对将递归过程转换为尾递归形式非常感兴趣。

对于“一维”情况（线性情况），比如斐波那契数列或阶乘计算，进行转换并不难。

例如，正如书中所述，我们可以将斐波那契计算重写如下：

(define (fib n)
    (fib-iter 1 0 n))
(define (fib-iter a b count)
    (if (= count 0) 
        b 
        (fib-iter (+ a b) a (- count 1))))

这个表单显然是尾递归的

然而，对于“二维”的情况，比如计算Pascal三角形（SICP中的例子1.12），我们仍然可以很容易地编写递归解决方案，如下所示

(define (pascal x y) 
  (cond ((or (<= x 0) (<= y 0) (< x y )) 0)
        ((or (= 1 y) (= x y) ) 1)
        (else (+ (pascal (- x 1) y) (pascal (- x 1) (- y 1))))))

问题是如何将这个转换成尾递归形式？

- Junjie

---

你的闭合括号让人感到烦躁。请将它们都放在同一行，这样有人就会开始回应了 ;) - Phil

@Phil，我认为将括号对齐到一列可能会使代码更清晰，因为放置太多的闭合括号在一起似乎有点难以匹配它们。 - Junjie

我建议你使用一个可以为你进行匹配的编辑器。像DrRacket这样专门为Scheme设计的编辑器还可以通过正确缩进代码来显示。 - Sylwester

你可以非常懒惰地使用帕斯卡三角形的任何元素都由row!/(column!(row - column)!)给出这一事实。但这并不是你问题的答案。 - Brendan Wilson

Answer 1

首先，递归过程 pascal 程序可以用更简单的方式表达（假设非负、有效输入）- 就像这样：

(define (pascal x y) 
  (if (or (zero? y) (= x y))
      1
      (+ (pascal (sub1 x) y)
         (pascal (sub1 x) (sub1 y)))))

现在来回答这个问题。可以将递归过程的实现转换为使用尾递归的迭代过程版本。但是，它比看起来更加棘手，而要完全理解它，必须掌握动态规划的工作原理。有关此算法的详细说明，请参考Steven Skiena的The Algorithm Design Manual第2版第278页。

这种算法不适合Scheme中的惯用解决方案，因为它要求我们作为解决方案的一部分修改状态（在本例中，我们正在更新向量中的部分结果）。这是一个相当人为的解决方案，并且我优化了表格内存使用方式，因此每次只需要一个行 - 下面是代码：

(define (pascal x y)
  (let ([table (make-vector (add1 x) 1)])
    (let outer ([i 1])
      (when (<= i x)
        (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-ref table y)))

事实上，在这种情况下，编写一个直接的迭代循环、在途中改变变量会更加自然。在Racket中，代码如下：

(define (pascal x y)
  (define current null)
  (define previous null)
  (define table (make-vector (add1 x) 1))
  (for ([i (in-range 1 (add1 x))])
    (set! previous 1)
    (for ([j (in-range 1 i)])
      (set! current (vector-ref table j))
      (vector-set! table j (+ (vector-ref table j) previous))
      (set! previous current)))
  (vector-ref table y))

我们可以打印结果并检查所有三个实现是否有效。再次在 Racket中：

(define (pascal-triangle n)
  (for ([x (in-range 0 n)])
    (for ([y (in-range 0 (add1 x))])
      (printf "~a " (pascal x y)))
    (newline)))

(pascal-triangle 5)

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 

- Óscar López

---

将其转换为符合Scheme语言习惯的解决方案非常简单。您只需要在达到所需数字后停止，而不是完成整行。请参阅我的答案。 - Sylwester

@Sylwester 是的，我研究了你的解决方案。我喜欢它是函数式的（因此更符合惯用法），但我也喜欢我的解决方案没有创建中间列表的事实 :P - Óscar López

Answer 2

更新：这个问题有一个更简单的数学解决方案，你可以只使用阶乘将其降至O(row)。基于此，它可以归结为：

(define (pascal-on row col)
  (define (factorial from to acc)
    (if (> from to)
        acc
        (factorial (+ 1 from) to (* acc from))))

  (let* ((rmc (- row col))
         (fac-rmc (factorial 1 rmc 1))
         (fac-pos (factorial (+ rmc 1) col fac-rmc))
         (fac-row (factorial (+ col 1) row fac-pos)))
    (/ fac-row fac-pos fac-rmc)))

旧回答：

你需要学习模式。基本上，您希望从三角形的开头开始迭代，直到有足够的信息来生成结果。显然，您需要上一行才能计算下一行，因此必须将其作为参数提供，并且如果请求的行不是当前行，则必须提供下一行。这个解决方案是尾递归和极快的。

New answer:

您需要学习这种模式。基本上，您需要从三角形的开头开始迭代，直到获得足够的信息以生成结果。显然，您需要使用前一行来计算下一行，因此必须将其作为参数输入，并且在请求的行不是当前行时必须提供下一行。这个解决方案使用尾递归，速度非常快。

(define (pascal row col)
  (define (aux tr tc prev acc)
    (cond ((> tr row) #f)              ; invalid input

          ((and (= col tc) (= row tr)) ; the next number is the answer
           (+ (car prev) (cadr prev))) 

          ((= tc tr)                   ; new row 
           (aux (+ tr 1) 1 (cons 1 acc) '(1)))

          (else (aux tr               ; new column
                     (+ tc 1) 
                     (cdr prev)
                     (cons (+ (car prev) (cadr prev)) acc))))) 

  (if (or (zero? col) (= col row))
      1
      (aux 2 1 '(1 1) '(1))))

- Sylwester

Answer 3

除了Óscar的答案，我们还可以使用续延传递风格来将任何程序转换为使用尾调用：

;; Int Int (Int → Int) → Int
(define (pascal/k x y k)
  (cond
   [(or (<= x 0) (<= y 0) (< x y)) (k 0)]
   [(or (= 1 y) (= x y)) (k 1)]
   [else (pascal/k (- x 1) y
                   (λ (a)
                     (pascal/k (- x 1) (- y 1)
                               (λ (b) (k (+ a b))))))]))

;; Int Int → Int
(define (pascal x y) (pascal/k x y (λ (x) x)))

你可能会认为这个程序并不令人满意，因为存在“增长”的闭包。但它们是在堆上分配的。一般情况下，具有尾递归的目的并不在于性能，而在于空间安全：您不会使评估体系膨胀。

- Phil