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

而这种形式显然是尾递归的

但是，对于“二维”情况，例如计算帕斯卡三角形(SICP 中的 Ex 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))))))

问题是，如何将其转换为尾递归形式？

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