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"); }

- What will be the output of the program?
- 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)$?

## 2 Answers

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$

### 8 Comments

https://gateoverflow.in/754/gate2001-13?show=145156#c145156

Refer this comment... Your doubts will get clarified..

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

= 2^2 x T(n-2) + 3

= 2^2 x (2*T(n-3) +1 ) + 2 + 1

= 2^3 x T(n-3) + 7

= [(2^n) x T(n-n)] + ((2^n - 1))

= [(2^n) x T(0) ] + ((2^n - 1))

= (2^n) + ((2^n - 1))

=(2^(n+1)) - 1

What's wrong in this! Both solutions seems correct but gives different answer.

for length 2 -> 3 characters

for length 3-> 7 characters

for length 4-> 15 characters

hence for n-> 2^n - 1 characters

### 3 Comments

**a) **3323321

**b) **we can also get the answer of b by solving recurrence relation

**T(n) = 2 * T(n-1) +1 ; n>0 **

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

After solving it by substitution,

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

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

= 2^{2 }x T(n-2) + 2 +1

= 2^{2 }x (2*T(n-3) +1 ) + 2 + 1

= 2^{3 }x T(n-3) + 2^{2 }+ 2 + 1

Finally it will expand like

= 2^{n }x T(n-n) + 2^{n-1} + 2^{n-2} + - - - - - - - + 2^{2 }+ 2 + 1

= 2^{n }x T(0) + 2^{n-1 }+ 2^{n-2 }+ - - - - - - - - - - + 2^{2 }+ 2 + 1

= 1x (2^{n }-1) / (2 - 1 )

= 2^{n }-1

lets assume to solve length n input it takes T(n) times

now in ques they have two abc(s+1) and one printf

abc(s+1) reduces the length of input by 1 so now it have length (n-1)

now to solve length (n-1) input it takes T(n-1) times and printf take 1 unit of time

hence reccurence relation is :

**T(n)=2.T(n-1)+1**