edited by
2,396 views
12 votes
12 votes

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);
}
}
  1. $625$
  2. $256$
  3. $120$
  4. $24$
  5. $5$
edited by

3 Answers

Best answer
15 votes
15 votes
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.$
selected by
10 votes
10 votes

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.

edited by
3 votes
3 votes

$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$

Answer:

Related questions

12 votes
12 votes
2 answers
2
4 votes
4 votes
2 answers
4
Arjun asked Dec 18, 2018
4,149 views
Which of the following decimal numbers can be exactly represented in binary notation with a finite number of bits ?$0.1$$0.2$$0.4$$0.5$All the above