Generating function of recursive algorithm with random subcalls

The recurrence $q_n=1+\frac12\sum_{k=1}^nq_k$ for $n\ge 2$ appears to be correct, and you have the initial conditions $q_0=0$ and $q_1=1$. I would modify the recurrence slightly to make it correct for all $n\ge 0$ on the assumption that $q_n=0$ for all $n<0$:

$$q_n=1+\frac12\sum_{k=1}^nq_k-[n=0]-\frac12[n-1]\;,\tag{1}$$

where the square brackets are Iverson brackets, and we can include $k=0$ because $q_k=0$. Now multiply $(1)$ by $x^n$ and sum over $n\ge 0$:

$$\sum_{n\ge 0}q_nx^n=\sum_{n\ge 0}x^n+\frac12\sum_{n\ge 0}\left(\sum_{k=0}^nq_i\right)x^n-1-\frac{x}2\;.\tag{2}$$

The lefthand side of $(2)$ is the desired generating function, say $g(x)$, so we have

$$\begin{align*} g(x)&=\frac1{1-x}-1-\frac{x}2+\frac12\sum_{n\ge 0}\left(\sum_{k=0}^nq_i\right)x^n\\ &=\frac12\left(\frac{x+x^2}{1-x}+\sum_{n\ge 0}\left(\sum_{k=0}^nq_i\right)x^n\right)\;. \end{align*}$$

Now recognize $\sum_{n\ge 0}\left(\sum_{k=0}^nq_i\right)x^n$ as the Cauchy product of $\sum_{n\ge 0}q_nx^n$ and a very simple power series whose corresponding function $f(x)$ you know, so that

$$2g(x)=\frac{x+x^2}{1-x}+f(x)g(x)\;.$$

You can then solve for $g(x)$:

$$g(x)=\frac{x+x^2}{(1-x)(2-f(x))}\;.$$

And if you’ve done this correctly, you’ll easily be able to expand $g(x)$ into a power series from which you can read off the coefficients $q_n$.