edited by
11,067 views
31 votes
31 votes

Consider the following C program:

void abc(char*s)
{
    if(s[0]=='\0')return;
    abc(s+1);
    abc(s+1);
    printf("%c",s[0]);
}

main()
{ 
    abc("123");
}
  1. What will be the output of the program?
  2. If $abc(s)$ is called with a null-terminated string $s$ of length $n$ characters (not counting the null ('\0') character), how many characters will be printed by $abc(s)$?
edited by

2 Answers

Best answer
44 votes
44 votes

Answer (A) $:332 \ 332 \ 1$
Answer (B) $:2^n-1$

Q. (A) $O/p$ :

$3 3 2 3 3 2 1$

(B) : $T(n) = 2T(n-1) +1 ; n>0 $

$\qquad =  0 ; n=0$ [Since for length zero string no character will be printed]

After solving it by substitution,

$T(n) = 2T(n-1) +1$

$\qquad = 2(2T(n-2)  + 1 )  +1$

$\qquad = 2^2T(n-2)  +  2 +1$

$\qquad =  2^2(2T(n-3) +1 )  + 2 + 1$

$\qquad = 2^3T(n-3) + 2^2  + 2 + 1$

Finally, it will expand like

$T(n)= 2^nT(n-n) + 2^{n-1} + 2^{n-2} + \ldots + 2^2 + 2 + 1 $

$\qquad = 2^nT(0) + 2^{n-1} + 2^{n-2} + \ldots+ 2^2 + 2 + 1$

$\qquad = \frac{1.(2^n -1)}{(2 - 1)}$

$\qquad = 2^n -1$

edited by
5 votes
5 votes
ans for B is: 2^n -1

for length 2 -> 3 characters

for length 3-> 7 characters

for length 4-> 15 characters

hence for n-> 2^n - 1 characters

Related questions