Scheme中的尾递归函数

Question

我正在为圣诞节的考试学习，并做一些示例考题，我遇到了这个问题有点困惑。

我可以正常使用递归，但我无法理解如何使用尾递归来编写相同的内容。

常规版本：

    (define (factorial X)
      (cond
            ((eqv? X 1) 1)
            ((number? X)(* X (factorial (- X 1))))))

- Eogcloud

Answer 1

如果一个函数是尾递归的，那么在函数返回后就不需要做任何操作，除了返回它的值。也就是说，在递归步骤中最后发生的事情是对函数本身的调用。通常通过使用累加器参数来跟踪答案来实现这一点：

(define (factorial x acc)
  (if (zero? x)
      acc
      (factorial (sub1 x) (* x acc))))

上述过程将最初使用1作为累加器调用，如下所示：

(factorial 10 1)
=> 3628800

注意到当基础情形得到满足时，累加值将被返回，并且在递归调用中，acc参数会得到更新。我不得不在过程中添加了一个额外的参数，但这可以通过定义内部过程或命名为let来避免，例如：

(define (factorial x)
  (let loop ((x x)
             (acc 1))
    (if (zero? x)
        acc
        (loop (sub1 x) (* x acc)))))

- Óscar López