PROBLEM 5: Consider the recursive C function below: void foo(unsigned int n) { p

Question

PROBLEM 5: Consider the recursive C function below:

void foo(unsigned int n) {

    printf("tick ");

    if(n > 0) {

        foo(n-1);

        foo(n-1);

    }

}

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

“Conjecture: for all , calling foo(n) results in ((2^(n+1))-1) ticks being printed”

5.C: Prove your conjecture from part B (hint: Induction!)

void foo(unsigned int n) {

    printf("tick ");

    if(n > 0) {

        foo(n-1);

        foo(n-1);

    }

}

Explanation / Answer

Every time foo is called, n is printed once. so

for n = 1

foo(1)
   +-------> foo(0)
   +-------> foo(0)

n is printed 3 times

for n = 2

foo(2)
   +-------> foo(1)
    |                +-------> foo(0
    |                +-------> foo(0)
   +-------> foo(1)
                      +-------> foo(0)
                      +-------> foo(0)

n is printed 7 times and print times = ((2^(n+1))-1) holds

let us consider that the formula also holds for n = m, so
     foo(m) will print ((2^(3+1))-1) number of times

for n = m + 1

foo(m + 1) will print once and call foo(m) twice.
so foo(m + 1) will print 2 * ((2^(m+1))-1) + 1 number of times
or 2 * 2^(m+1) - 2 * 1 + 1 number of times
or 2^(m+2) - 1 number of times
or ((2^((m+1)+1))-1) number of times

which is equivalent to expected number for n = m+1. Thus proved

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.