Jesse's Blog

0.
'In fact, it is not hard to show that the number of times the procedure will
compute (fib 0) or (fib 1) (the number of leaves in the above tree, in
general) is precisely Fib(n+1).'

Proof:

Let r(n) to be the number of leaves in the tree rooted in Fib(n), then it's
easy to see that,

r(n) = r(n-1) + r(n-2) (when n > 1)

( since the tree rooted in Fib(n) has two braches, which are repectively
rooted in Fib(n-1) and Fib(n-2). )

When n is 0 or 1,
r(n) = 1

The above description makes precisely a Fibonacci sequence (1,1,2,3..),
lacking the first element, i.e., r(0) is Fib(1), r(1) is Fib(2), so,

r(n) = Fib(n+1)

1.
FIXME: 'The space required grows only linearly with the input, because we
need keep track only of which nodes are above us in the tree at any point
in the computation.'

2.
FIXME: Come up with the efficient answer to count-change problem.