Description
Fibonacci
Write a program that, given a non-negative integer n, provides some information about the computation of 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 defined 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 /\ 21
/\ 11
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 first the tree of recursive calls and then output the required information using the tree structure. straightforward implementation of the Fibonacci function F(n) recursively defined 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 /\ 21
/\ 11
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 first the tree of recursive calls and then output the required information using the tree structure.
