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

Question

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

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

根据定义，当递归调用是函数执行的最后一件事时，递归函数是尾递归的。在此示例中，函数执行的最后一件事是调用 foo 并返回其值，但在此之前它使用嵌套 foo 函数的返回值。所以我很困惑。

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

示例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 是在尾部位置之外调用的 -

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

上面，递归斐波那契可以产生两个对斐波那契的调用，每个调用可以产生两个更多调用到斐波那契。如果不重写它，两个调用都不可能位于尾部位置。我们可以使用具有附加参数的辅助函数来解决这个问题，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

无论是否尾递归，上面的斐波那契都是一个指数过程，即使对于很小的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。

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

---

在您编辑的问题中，您包含一个可以将嵌套数字列表相乘的方案程序。我们首先展示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 是一个成本高昂的列表操作，对于嵌套很深的列表，此过程可能会产生不良性能。当然还有其他解决方案。看看你能想出什么并提出其他问题。之后我将分享一个我认为优点最多、缺点最少的解决方案。