Consider the recursive C function below:

void foo(unsigned int n) {

printf(tick );

if(n > 0) {

foo(n-1);

foo(n-1);

}

}

1.Complete the following table indicating how many ticks are printed for various parameters n.

Unenforceable rule: derive your answers by hand -- not simply by writing a program calling the function.

n	number of ticks printed when foo(n) is called
0
1
2
3
4

2: Derive a conjecture expressing the number of ticks as a function of n -- i.e., complete the following:

Conjecture: for all n0, calling foo(n) results in _____________ ticks being printed

3.: Prove your conjecture from part 2.