How often will occur * ?
void Star(int n) {
for (i=0;i<n;i++) {
printf("*");
Star(i);
}
}
I thing so $\displaystyle 2^n - 1$, but I don`t know how I can count it.
You are right about the number of *. Let's call the number of * printed by a call to Star(n) by $\displaystyle s_n$. The program gives rise to the recurrence relation on $\displaystyle s_n$:
$\displaystyle s_n=\sum_{i=0}^{n-1}(1+s_i)=n+\sum_{i=0}^{n-1}s_i$.
After you have a recurrence relation, you can calculate the first several values and make a hypothesis about the general formula, but you have already done this. Then you need to prove this hypothesis, i.e., $\displaystyle s_n=2^n-1$ for all n, by induction on n using the recurrence relation.