Ratio of leaves to total nodes in a Fibonacci call stack

If you were to look at a recursive implementation of calculating the nth Fibonacci number (root 100, children 99 and 98, grandchildren 98, 97, 97, and 96, etc. etc.), roughly what would be the ratio of the number of leaves to the to开发者_StackOverflowtal number of nodes in the recursive tree?

    100
   /   \
  98   97
 /  \   .
96  97  .
.    .  .
.    .  

Not homework, just academically curious about this. (And yes, I realize that a recursive implementation is a god-awful way to calculate Fibonacci numbers)

The number of leaves is simply F(n) since the F(i) is simply the number of leaves beneath that node. Do you see why? (hint: use induction)

The number of non-leaf nodes is the number of leaf nodes-1. This is a property of binary trees. So the total number of nodes is F(n) + F(n)-1 = 2F(n)-1.

The ratio thus approaches 1/2 as n grows large.

fib(x) consist of leaves fib(x-1) and leaves of fib(x-2). So you get the same recursive equation as you have for fibonacci numbers.

If the termination point (leaves) are Fib1 and Fib0, then

tree   numofleaves
fib2   2
fib3   3
fib4   5
fib5   8
fib6   13
...

and numofleaves(x) = fib(x+1).

For the number of nodes you get the equation numnodes(x) = 1 + numnodes(x-1) + numnodes(x-2).

I actually worked out a proof by induction that shows that the number of leaves in a Fibonacci tree always exceeds the number of internal nodes.

Proof: Let E(n) be the # of leaves of fibonacci tree for input n, and M(n) be the # of internal nodes of fibonacci tree for input n

   E(n) >= M(n) + 1

Base cases:

f(0): E(0) = 1, M(0) = 0

f(1): E(1) = 1, M(1) = 1

f(2): E(2) = 2, M(2) = 1

f(3): E(3) = 3, M(3) = 2

The leaves of a tree of size n is equal to the leaves of each sub-tree:

E(n) = E(n - 1) + E(n - 2)

The internal nodes of a tree of size n is equal to the internal nodes of each sub-tree, plus the root

M(n) = M(n - 1) + M(n - 2) + 1

E(n) >= [M(n - 1) + 1] + [M(n - 2) + 1], (by the Inductive Hypothesis)

So, E(n) = M(n - 1) + M(n - 2) + 2

So, E(n) >= M(n) + 1, QED