Problem
In the recursive calculation of Fn , determine exactly how many times each smaller Fibonacci number will be calculated. From this, determine the orderof-magnitude time and space requirements of the recursive function. [You may find out either by setting up and solving a recurrence relation (top-down approach), or by finding the answer in simple cases and proving it more generally by mathematical induction (bottom-up approach).]