Scheme中的Tail递归函数

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