Reference no: EM13845204

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?