1

在球拍中，我定义了以下函数，我想知道它是否是尾递归：

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

我的问题实际上是这样的，但我必须写点别的东西来满足我的帖子质量标准。实际上，我不知道我的帖子质量标准是什么。

4

4 回答 4

5

这实际上与您之前的问题相同。是的，这是尾递归：每当您的函数中发生递归调用时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-18T01:01:40.473 回答
1

这是将代码转换为帧变异版本的伪代码（实际上是 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).

于 2013-03-18T15:09:16.397 回答
0

唯一的调用foo是在尾部位置，所以这个函数在我看来是尾部递归的。

于 2013-03-18T01:00:53.943 回答
0

Scheme R6RS第 59 页的第 11.20 节描述了尾调用并显示了基本 Scheme 句法形式的尾调用位置，例如 forif和lambda

您对 inside 的调用foo处于foo尾部位置。（因为它们分别处于内if尾位、外if尾位和lambda尾位。）

于 2013-03-18T04:51:19.483 回答