1.2.2 Tree Recursion

線形の次はツリー型再帰だ。例題は良くあるフィボナッチ数の問題。素直に再帰で書くと各再帰深さにて２つのパラメータが未定（要再帰呼び出し）になったツリー状の演算グラフができる。これ、すごい数の無駄演算を行ってしまうが、簡単に書けて理解しやすい、というような話。*1
フィボナッチ数の場合、漸化式状態にできれば、末尾再帰に持って行くことができるが、複雑な例では大変。具体的な例が次の章、ですね。

*1:Haskellでは参照透明性によって同じ式は同じエンティティにbindされる（無駄演算しない）んだそうだけれど、どうなんだろう？