SICP——是我对阶乘迭代过程的递归定义

Question

我正在学习一本很棒的书SICP。尽管很棒，但这确实是一本很难读的书。我在使用长尾递归时遇到了问题，这是一个迭代过程的递归定义。书中给出了阶乘的迭代过程:

(define (factorial n)
  (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

我试着做一个方法没有看书的例子。我明白了:

(define (factorial n)
  (factorial-iter n 1 n))
(define (factorial-iter a product counter)
  (if (= counter 0)
      product
      (factorial-iter (- a 1)
                      (* product a)
                      (- counter 1))))     

我的方法在某种意义上是错误的吗?

Answer 1

在你的方法中没有错，它正确地计算了阶乘，只有一些多余的东西。您可以注意到两个变量a和counter的总是相同的值，因为它们总是以相同的方式更新。因此，您可以去掉其中一个，并以这种方式简化函数:

(define (factorial n)
  (factorial-iter n 1))
(define (factorial-iter a product)
  (if (= a 0)
      product
      (factorial-iter (- a 1)
                      (* product a))))

最后，为了安全起见，您可以更改终止的测试，以查看a是否小于或等于0，因此该函数将不会以负参数循环无限:

(define (factorial-iter a product)
  (if (<= a 0)
      product
      (factorial-iter (- a 1)
                      (* product a))))