TIFR CSE 2019 | Part B | Question: 6

Question

Given the following pseudocode for function $\text{printx()}$ below, how many times is $x$ printed if we execute $\text{printx(5)}?$

void printx(int n)  {
    if(n==0){
        printf(“x”);
}
for(int i=0;i<=n-1;++i){
    printx(n-1);
}
}

• A. $625$
• B. $256$
• C. $120$
• D. $24$
• E. $5$

Comments

5times.

---

try the code

---

Number 1 lesson after going through these C questions - always try the code, never assume.

---

What is the recursion tree for this question??

Answer 1

If we denote the number of times $x$ being printed for input $n$ by $C(n)$ we can write

$C(n) = n \times C(n-1)$ (Since the for loop runs $n$ times and each iteration does a recursive call to $printx(n-1))$

$C(0) = 1$

So, $C(5) = 5 \times 4 \times 3 \times 2 \times 1 \times 1 = 120.$

Answer 2

loop running from 0 to n

n=0 ==> 'x' is printed one time

n=1 ==> for loop is executed twice i.e. A(n-1)===> A(0) is called twice ==> 2(A(0)times)==>2 times

n=2 ==>for loop is executed thrice i.e A(n-1)===> A(1) is called thrice ==> 3(A(1)times)==>3*2=> 6 times

n=3 ==> for loop is executed 4 times i.e. A(n-1)==>A(2) is called 4 times=> 4(A(2)times)==>4*6=>24 times

n=4 ==> for loop is executed 5 times i.e. A(n-1)==>A(3) is called 5 times=> 5(A(3)times)==>5*24=>120 times

n=5 ==> for loop is executed 6 times i.e. A(n-1)==>A(4) is called 6 times=> 6(A(4)times)==>6*120=>720 times

Instead this you can identify the pattern at n=3 itself as (n+1)! itself.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------

edit : As per the changed question loop running from 0 to n-1:

n=0 ==> 'x' is printed one time

n=1 ==> for loop is executed once i.e. A(n-1)===> A(0) is called once ==> 1(A(0)times)==>1 time

n=2 ==>for loop is executed twice i.e A(n-1)===> A(1) is called twice ==> 2(A(1)times)==>2*1=> 2 times

n=3 ==> for loop is executed 3 times i.e. A(n-1)==>A(2) is called 3 times=> 3(A(2)times)==>3*2=>6 times

n=4 ==> for loop is executed 4 times i.e. A(n-1)==>A(3) is called 4 times=> 4(A(3)times)==>4*6=>24 times

n=5 ==> for loop is executed 5 times i.e. A(n-1)==>A(4) is called 5 times=> 5(A(4)times)==>5*24=>120 times

Instead this you can identify the pattern at n=3 itself as (n)! itself.

Comments

Question edited as per question asked in exam. Pls edit your ans accordingly

---

@Sayan Bose Answer is edited as per the modified question. Please add the source of this question if available.

Answer 3

$P(5)\rightarrow(i=0;i<=4;++i)$

$\downarrow$

$P(4)\rightarrow(i=0;i<=3;++i)$

$\downarrow$

$P(3)\rightarrow(i=0;i<=2;++i)$

$\downarrow$

$P(2)\rightarrow(i=0;i<=1;++i)$

$\downarrow$

$P(1)\rightarrow(i=0;i<=0;++i)$

$\downarrow$

$P(0)\rightarrow printf(x)$

$\downarrow$

$(i=0;i<=-1;++i) //condition\ false$

---

$P(0): x\ printed\ 1\ time$

$P(1)\rightarrow(i=1;i<=0;++i)// condition\ false$

$P(2)\rightarrow(i=1;i<=1;++i): x\ printed\ 1\ time$

$P(2)\rightarrow(i=2;i<=1;++i)// condition\ false$

$P(3)\rightarrow(i=1;i<=2;++i): x\ printed\ 2\ times$

$P(3)\rightarrow(i=2;i<=2;++i): x\ printed\ 2\ times$

$P(3)\rightarrow(i=3;i<=2;++i)// condition\ false$

$P(4)\rightarrow(i=1;i<=3;++i): x\ printed\ 6\ times$

$P(4)\rightarrow(i=2;i<=3;++i): x\ printed\ 6\ times$

$P(4)\rightarrow(i=3;i<=3;++i): x\ printed\ 6\ times$

$P(4)\rightarrow(i=4;i<=3;++i)// condition\ false$

$P(5)\rightarrow(i=1;i<=4;++i): x\ printed\ 24\ times$

$P(5)\rightarrow(i=2;i<=4;++i): x\ printed\ 24\ times$

$P(5)\rightarrow(i=3;i<=4;++i): x\ printed\ 24\ times$

$P(5)\rightarrow(i=4;i<=4;++i): x\ printed\ 24\ times$

$P(5)\rightarrow(i=5;i<=4;++i)// condition\ false$

---

$x\ is\ printed\ 120\ times$