尾部嵌套调用的递归可以是尾递归吗？

Question

尾部嵌套调用的递归可以是尾递归吗？

例如，我在 Racket 中有以下函数，旨在将二叉树（定义为下面的嵌套结构）转换为列表，

至少在外观上，只有大约一半的递归调用位于尾部位置，而另一半则不是。

(define-struct node (key left right))

;; postorder traversal which converts a Binary Search Tree to an ascending list
(define (bst->list-help b acc)
  (cond
    [(empty? b) acc]
    [else (bst->list-help (node-left b)
                          (cons (node-key b)
                                (bst->list-help (node-right b) acc)))]))

(define (bst->list b)
  (bst->list-help b empty))

bst->list-help

是尾递归吗？

Answer 1

函数本身是尾递归是什么意思？

是的，尾递归正在应用于这些调用。它不是嵌套调用。这可以避免创建许多堆栈帧。但当你向右走时，你仍然会得到很深的筹码。

所以该功能正在从优化中受益。但只有一半的递归调用。你想叫它什么？