recursion - 如何对二叉树进行尾递归？

Question

如果你有一棵二叉树，你如何使用尾递归迭代（按顺序使用）它？我知道尾递归涉及您在迭代时计算新值，然后当您到达基本情况时，您只需返回累积值。但是，当您必须调用函数调用两次时，如何为树执行此操作？

Answer 1

假设深度优先从左到右遍历，您不能将尾递归用于左侧分支，但您可以将其用于右侧分支。

示例方案代码（假设您tree具有三个访问器函数value、left和right）：

(define (collect-in-order tree)
  (define (collect node result)
    (if node
        (collect (right node)
                 (cons (value node)
                       (collect (left node) result)))
        result))
  (reverse (collect tree '())))

处于尾部位置，因此这(collect (right node) ...)是尾部调用。

您还可以进行从右到左的遍历，在这种情况下，向左下降是尾递归的：

(define (collect-in-order tree)
  (let collect ((node tree)
                (result '()))
    (if node
        (collect (left node)
                 (cons (value node)
                       (collect (right node) result)))
        result)))