scheme

Question

我已经在方案中实现了这个递归函数：

       (define f (lambda (n)

        (cond ((= n 0) 0)
              ((= n 1) 2)
              ((= n 2) 37)
              ((odd? n) (+ (f (- n 3)) 1))
              (else (+ (f (- (/ n 2) 1)) 7))))
        )

在很多练习中，我被问到我的解决方案是否是尾递归的，老实说，无论我阅读多少次尾递归的定义，我就是不明白。如果我定义尾递归，它会是这样的。

Definition: A tail-reursive function is calculated in a constant memory space no matter the input value.

这里还有另外两个。其中之一是尾递归，我想找出是哪一个。

(define ln2-a
 (lambda (n)
 (define loop
   (lambda (n)
     (if (= n 1)
         0
        (+ 1 (loop (quotient n 2))))))
 (trace loop)
 (loop n)))

这里。

(define ln2-b
  (lambda (n)
    (define loop
      (lambda (n result)
      (if (= n 1)
         result
       (loop (quotient n 2) (+ result 1)))))
 (trace loop)
 (loop n 0)))

我们来看看最后两个函数。这里我假设 ln2-b 是递归的。但我真的无法回答为什么，这让我很恼火。我认为跟踪循环对我有帮助，但我不太确定它说的是什么以及它如何帮助我。我尝试比较所有三个函数以找到相似之处以及它们之间的不同之处。但是，不幸的是，我做不到...

希望有好心人帮帮我，谢谢。哦，我对计算机科学也很陌生，所以也许我用错了一些术语。如果有什么不清楚的，就说出来。 :)

Answer 1

在您的第一个代码块中，f 不是尾递归的。 f 的递归调用必须发生，return 其结果，然后必须将 1 或 7 添加到结果中，具体取决于分支。由于对 f 的递归调用必须 return，并且对 f 的递归调用有任意多个，这意味着任意必须分配许多堆栈帧。

当您想到调用一个函数时，想象您拿了一张新纸并在该纸上写下所有局部变量和值可能会有所帮助。当您确定函数的结果时，可能会递归调用同一函数。如果调用是尾调用，那么当你为它拿一张纸时，你 可以扔掉旧的 sheet，因为你不需要任何它的价值观了。

例如，考虑两种计算列表长度的方法：

(define (length-1 list)
  (if (null? list)
      0
      (+ 1
         (length-1 (cdr list))))) ; recursive call, NOT a tail-call

在此实现中，您必须完成对 length-1 的递归调用，获取其结果，并将其加 1。这意味着您需要在递归调用之后返回某个地方。现在考虑一个尾递归版本：

(define (length-2 list current-length)
  (if (null? list)
      current-length
      (length-2 (cdr list) ; recursive call, IS a tail-call
                (+ 1 current-length))))

在此版本中，一旦开始对 length-2 进行递归调用，就不再需要原始调用的任何上下文。事实上，您可以通过 assigning (cdr list) to list 将其转换为循环，并且分配(+ 1 当前长度)到当前长度。您可以重复使用 相同的堆栈space。这就是尾调用优化（当尾调用是对同一个函数时）相当于一个循环。

Answer 2

尾递归函数会将累加的结果传递给每次调用，这样一旦达到结束条件，结果可以立即返回到最后一次函数调用。

非尾递归函数需要在返回结果后对其进行处理。因此，必须记住每一层递归，以便它可以返回计算最终结果。

在您的第一个示例中，您将添加到下一次调用 f 的结果中，因此它不是尾递归的。

第二个例子也是加入循环的下一次调用，所以不是尾递归

第三个例子，将最终结果作为参数传递给下一个函数调用，所以它是尾递归的。

Answer 3

非常简单.. 当你需要对递归的结果做一些事情时，它不是尾递归。

(define (length lst)
  (if (null? lst)
      0
      (+ 1
         (length (cdr lst))))

在这里你清楚地看到我们必须 + 1 到递归的答案。这在每一步都会发生，因此堆栈会不断累积，直到达到基本情况，然后我们在返回时为每个元素添加 1 。 (length '(1 2 3 4)) ; ==> (+ 1 (+ 1 (+ 1 (+ 1 0))))

当过程完成并且结果是最后一步（基本情况）的结果时，它是尾递归的。

(define (length lst)
  (define (aux lst count)
    (if (null? lst)
        count ; last step
        (aux (cdr lst) (+ 1 count))))

  (aux lst 0))

这里的辅助过程将 count 作为参数，而不必等待加 1，而是在递归发生之前执行（通过增加参数）。整个事情的结果只是基本情况的结果，仅此而已。它是尾递归的。连helper的调用都是尾调用，但不是递归的，但是所有的尾调用在Scheme中都做了优化

现在，你的两个过程中哪个是尾递归的？

scheme - 函数是尾递归的吗？

scheme - Is function tail-recursive?

recursion

tail-recursion