这个函数尾递归吗？

Question

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

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

我的问题几乎就是这样,但我必须写一些其他内容来满足我的帖子质量标准.实际上,我不知道我的帖子质量标准是什么.

Answer 1

这几乎与您之前的问题相同.是的,这是尾递归的:每当你的函数中发生递归调用时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))

然后显然递归调用不会处于尾部位置,因为在递归返回之后执行操作:向递归的结果添加一个操作.