1. Given the following code:
unsigned long long Fac (unsigned long long n)
{
i f (n == 0)
return 1 ;
return n * Fac (n - 1 ) ;
}
Show the call stack for Fac(5).
2. Write C++ code to recursively compute the n-th Fibonacci number.
Recall that Fibonacci numbers are dened as follows:
Fn = Fn-1 + Fn-2
and,
F1 = 1; F2 = 1
unsigned long long Fib (unsigned long long n)
{
//Your code here
}
3. Run the above code for n = 30; 40; and 50. What happens as n increases?
What do you think this implies about big-O run time of the algorithm?