recursion - Scheme 中的尾递归函数

Question

我正在准备圣诞节考试并做一些考试样本，我遇到了这个让我有点困惑的问题

我可以很好地执行常规递归，但我无法理解如何使用尾递归编写相同的内容。

普通版:

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

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