这样的函数结构是尾递归的吗？

Question

这样的函数结构是尾递归吗？

function foo(data, acc) {
    ...
    return foo(data, foo(data, x));
}

根据定义，当递归调用是函数执行的最后一件事时，递归函数是尾递归的。在这个例子中，函数做的最后一件事是调用 foo 和 return 它的值，但是在此之前它使用嵌套 foo 函数的 return 值。所以我很困惑。

编辑：考虑方案语言和一个将给定列表中的元素相乘的简单函数：

示例 1：

(define (foo list) (helper list 1) )

(define (helper list acc)
  (cond ((null? list) acc)
   ((not (pair? list)) (* list acc))
   ((list? (car list)) (helper (car list) (helper (cdr list) acc)))
   (else (helper (cdr list) (* acc (car list)))))
)

示例 2：这是纯尾递归吗？

(define (foo list) (helper list 1) )

(define (helper list acc)
    (cond ((null? list) acc)
    ((not (pair? list)) (* list acc))
    ((list? (car list)) (helper (cdr list) (* (foo (car list)) acc)))
    (else (helper (cdr list) (* acc (car list))))))

根据答案，我假设第一个不是纯尾递归。

Answer 1

我认为这里的棘手之处在于有两种不同的方式来思考尾递归函数。

首先是纯尾递归函数，也就是只用尾递归进行递归的函数。对于上面的情况，您的函数不是纯粹的尾递归，因为递归分支，而纯尾递归不能分支。

其次，有些函数可以通过使用尾调用优化来消除一些递归。这些函数执行它们想要执行的任何类型的递归，但至少有一个递归调用可以使用尾调用优化以非递归方式重写。你的功能确实属于这一类，因为编译器可以

已使用真正的递归进行递归调用 foo(data, x)，但是
回收堆栈space以评估foo(data, /* result of that call */)。

那么你的函数是纯尾递归的吗？不，因为递归分支。但是一个好的编译器可以优化掉其中一个递归调用吗？是的

Answer 2

不，它不是尾递归的，因为foo是在尾部位置调用的-

function foo(data, acc) {
    ...
                     // foo not in tail position here
    return foo(data, foo(data, x));
}

让我们使用像 fibonacci -

这样的具体程序来解决这个问题

const fibonacci = n =>
  n < 2
    ? n                   // non tail call!
    : fibonacci (n - 2) + fibonacci (n - 1)
    
console .log (fibonacci (10)) // 55

以上，递归 fibonacci 可以产生两次对 fibonacci 的调用，每个调用可以产生两个更多呼叫 fibonacci。如果不重写它，两个调用都处于尾部位置是不可能的。我们可以使用具有附加参数的辅助函数来解决这个问题，下面是 then -

const helper = (n, then) =>
{ if (n < 2)
    return then (n)                // tail
  else 
    return helper (n - 2, a =>     // tail
             helper (n - 1, b =>   // tail
               then (a + b)        // tail
           ))
}

const fibonacci = n =>
{ return helper (n, x => x)        // tail
}
    
console .log (fibonacci (10)) // 55

某些语言允许您指定默认参数，因此无需使用单独的辅助函数 -

const identity = x =>
  x

const fibonacci = (n, then = identity) =>
{ if (n < 2)
    return then (n)                  // tail
  else 
    return fibonacci (n - 2, a =>    // tail
             fibonacci (n - 1, b =>  // tail
               then (a + b)          // tail
           ))
}

console .log (fibonacci (10))
// 55

fibonacci (10, res => console .log ("result is", res))
// result is: 55

无论尾递归与否，上面的 fibonacci 是一个 指数级 过程，即使 n 的小值也非常慢。通过使用附加参数 a 和 b -

表示我们的计算状态，可以实现线性过程

const fibonacci = (n, a = 0, b = 1) =>
  n === 0
    ? a                            // tail
    : fibonacci (n - 1, b, a + b)  // tail
  
console .log
  ( fibonacci (10)   // 55
  , fibonacci (20)   // 6765
  , fibonacci (100)  // 354224848179262000000
  )

有时您需要使用额外的状态参数，有时您需要使用辅助函数或延续，例如 then。

如果您使用特定语言向我们提出特定问题，我们可能会写出更具体的答案。

在您编辑的问题中，您包含了一个可以乘以嵌套数字列表的 Scheme 程序。我们首先展示 then 技术

(define (deep-mult xs (then identity))
  (cond ((null? xs)
         (then 1))
        ((list? (car xs))
         (deep-mult (car xs) ;; tail
                    (λ (a)
                      (deep-mult (cdr xs) ;; tail
                                 (λ (b)
                                   (then (* a b)))))))
        (else
         (deep-mult (cdr xs) ;; tail
                    (λ (a)
                      (then (* a (car xs))))))))

(deep-mult '((2) (3 (4) 5))) ;; 120

您也可以像我们在第二种技术中那样使用状态参数 acc，但是因为输入可以嵌套，所以我们必须使用 then 技术来展平潜在两次调用 deep-mult -

(define (deep-mult xs (acc 1) (then identity))
  (cond ((null? xs)
         (then acc)) ;; tail
        ((list? (car xs))
         (deep-mult (car xs) ;; tail
                    acc
                    (λ (result)
                      (deep-mult (cdr xs) result then)))) ;; tail
        (else
         (deep-mult (cdr xs) ;; tail
                    acc
                    (λ (result) then (* result (car xs)))))))

(deep-mult '((2) (3 (4) 5)))
;; 120

我不太喜欢这个版本的程序，因为每种技术只解决了一半的问题，而之前只使用了一种技术。

对于这个特定问题，也许一个聪明的解决方法是在嵌套列表的情况下使用 append

(define (deep-mult xs (acc 1))
  (cond ((null? xs)
         acc)
        ((list? (car xs))
         (deep-mult (append (car xs) ;; tail
                            (cdr xs))
                    acc))
        (else
         (deep-mult (cdr xs) ;; tail
                    (* acc (car xs))))))

(deep-mult '((2) (3 (4) 5))) 
;; 120

但是，append 是一个代价高昂的列表操作，对于嵌套很深的列表，此过程的性能可能很差。当然还有其他解决方案。看看你能想出什么，并提出更多问题。之后我将分享一个我认为提供最多优点和最少缺点的解决方案。

Answer 3

通常，通过命名所有临时实体将您的函数转换为 SSA form，然后查看对您的 foo 的每次调用是否处于尾部位置，即最后要做的事情。

你问尾位怎么可能不止一个？他们可以，如果每个人都在自己的条件分支中，并且该条件本身位于尾部位置。

关于您编辑的 lisp 函数。两者都不是尾递归的，即使最后一个 helper 在非尾位置调用 foo，因为 foo 最终也会调用 helper。是的，要完全尾递归，非尾位置的调用必须不会导致调用函数本身。但是，如果它处于尾部位置，那么就可以了。尾调用是一个美化goto，是这里的目标。

但是你可以通过遍历输入嵌套列表nay tree数据结构来尾递归地编码，如

(define (foo list) (helper list 1) )

(define (helper list acc)
  (cond 
    ((null? list)  acc)
    ((not (pair? list))  (* list acc))
    ((null? (car list))  (helper (cdr list) acc))
    ((not (pair? (car list)))  (helper (cdr list) (* (car list) acc)))
    (else  (helper (cons (caar list)
                     (cons (cdar list) (cdr list))) acc))))

Answer 4

这可能是吹毛求疵，但是函数不被认为是尾递归的。如果过程调用可以发生在尾上下文中，则该调用称为尾调用。

在你的例子中：

function foo(data, acc) {
    ...
    return foo(data, foo(data, x));
}

或

(define (foo data acc)
  (foo data (foo data x)))

有两个调用：内部调用(foo data x)不在尾上下文中，但外面的 (foo data ...) 是。

R5RS Scheme中尾上下文的规范，参见[1]。

总结：检查一个特定的调用是否是尾调用是一种语法检查。

你的功能是"tail recursive"吗？那取决于你如何定义"a tail recursive function"。如果你的意思是 "all recursive calls must be tail calls" - 那么不是。如果你的意思是 "all body evaluations end with a recursive call" - 那么是的。

现在函数的运行时行为也很重要。当你评估一个函数调用时，会发生什么样的计算过程？解释有点复杂，所以我会平底船，只留下参考：[2] SICP “1.2 Procedures and the Processes They Generate.”。

[1] http://www.dave-reed.com/Scheme/r5rs_22.html [2] https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2

这样的函数结构是尾递归的吗？

Is such a function structure tail recursive?

recursion

scheme

pseudocode

tail-recursion