Description
Fibonacci
Write a program that, given a non-negative integer n, provides
some information about the computation of the straightforward implementation
of the Fibonacci function F(n) recursively defifined as follows
F(0) = 1
F(1) = 1
F(n) = F(n − 2) + F(n − 1)
For example if the input is 3, a recursive implementation of F(n) would result
in the following tree of recursive calls:
F(3)
/ \
F(2) F(1)
/ \
F(1) F(0)
We want to know all Fibonacci numbers computed, the size of the tree, its
height and the number of leafs (i.e. nodes without sub-trees, which in this case
correspond to the base cases of the recursive formulation).
The numbers should be provided in pre-order. That is, if we replace the
calls F(i) by their result the tree would look like this:
3
/ \
2 1
/ \
1 1
And the pre-order traversal of such a tree would be 3 2 1 1 1.
The format of the output should look like this:
Call tree in pre-order: 3 2 1 1 1
Call tree size: 5
Call tree depth: 3
Call tree leafs: 3
Use a tree structure to build fifirst the tree of recursive calls and then output
the required information using the tree structure.
