是这个函数尾递归吗？

问题描述：

在球拍，我定义了下面的函数，我想知道它是否是尾递归：是这个函数尾递归吗？

(define foo 
    (λ (c m s1 s2) 
     (if (< c m) 
      (if (= (modulo m c) 0) 
       (foo (+ c 1) m (+ s1 c) s2) 
       (foo (+ c 2) m s1 (+ s2 c))) 
      (cons s1 s2))))

我的问题实际上是这样的，但我必须写别的东西来满足我后质量标准。实际上，我不知道我的职位质量标准是。

答

这与您之前的问题基本相同。是的，这是尾递归：当函数foo发生递归调用时，它处于尾部位置。意思是：在执行递归调用之后，没有其他任何事情要做，那个执行分支结束了。 (cons s1 s2)部分是递归的基本情况，所以它不计数。为了更清楚地看到它的foo程序是相同的：

(define (foo c m s1 s2) 
    (cond ((>= c m) 
     (cons s1 s2))     ; base case of recursion 
     ((= (modulo m c) 0) 
     (foo (+ c 1) m (+ s1 c) s2)) ; recursive call is in tail position 
     (else 
     (foo (+ c 2) m s1 (+ s2 c))))) ; recursive call is in tail position

我们先来看看什么是不一尾递归的例子。例如，如果第二if的后事件部分被定义如下：

(+ 1 (foo (+ c 1) m (+ s1 c) s2))

那么显然递归调用不会在尾部位置，因为递归返回之后进行的操作：将一个到递归的结果。

我很难想象解释器在这种情况下如何重复使用与最优化相同的调用堆栈。 – 2013-03-18 14:42:30

在我上面的实现中，它更加清晰，将'foo'的尾调用看作一个奇怪的'for for'，其中参数是每次迭代中更新的变量，第一个条件是循环的退出条件。然后很容易看到，相同的堆栈帧在调用之间重复使用 - 只有参数值需要更新 – 2013-03-18 15:05:01

非常感谢。 – 2013-03-18 15:12:50

答

对foo的唯一调用位于尾部位置，因此该函数看起来是递归给我的。

答

见11.20，中Scheme R6RS 59页描述了尾调用并显示基本计划语法形式的尾调用位置，像if和lambda

你的内foo调用foo在尾部位置。（因为他们是在内部if尾位置，外if尾位置和lambda尾位置）

答

下面是一个伪代码（Common Lisp的实际上）代码的翻译框架变异版本：

(defun foo (c m s1 s2) 
    (prog 
     ((c c) (m m) (s1 s1) (s2 s2)) ; the frame 
     BACK 
     (if (< c m) 
      (if (= (modulo m c) 0) 
       (progn 
       (psetf s1 (+ s1 c)  ; set! 
         c (+ c 1)) ; in parallel 
       (go BACK)) 
       (progn 
       (psetf s2 (+ s2 c)  ; set! 
         c (+ c 2)) ; in parallel 
       (go BACK))) 
      (return-from foo (cons s1 s2))))))

由于在每次尾部呼叫后没有更多的事情可做，我们可以只需(go BACK)。

是这个函数尾递归吗？

相关推荐