Description

Assignment 11
Hand-in via https://dtu.codejudge.net/02393-e17/assignment/
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
/
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 first the tree of recursive calls and then output the required information using the tree structure.