recursion - 二分木の末尾再帰を行うには?

Question

二分木がある場合、末尾再帰を使用して (順番に使用して) どのように繰り返すことができますか? 末尾再帰では、反復するときに新しい値を計算する必要があることを知っています。その後、基本ケースに到達したら、累積を返すだけです。しかし、関数呼び出しを 2 回呼び出さなければならない場合、ツリーに対してこれを行うにはどうすればよいでしょうか。

Answer 1

深さ優先の左から右へのトラバーサルを想定すると、左側のブランチには末尾再帰を使用できませんが、右側のブランチには使用できます。

Scheme コードの例 ( 、、およびtreeの 3 つのアクセサ関数があると仮定):valueleftright

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