We proceed by "guessing" a generating function for $R(n,q)$ and verifying that it has the right properties.

According to https://oeis.org/A143017, the generating function $G= \sum_{n=1}^\infty a(n) x^n$ satisfies
\begin{equation}
xG^3 + (4x-2)G^2 + (4x-1)G + x = 0
\tag{1}
\end{equation}
and it is easy to see that $G$ is uniquely determined as a formal power series by this equation and the condition that $G$ has no constant term.

Let $F$ be the compositional inverse of $x(1-x^2)/(1+x-x^2)$ so $$\frac{F(1-F^2)}{1+F-F^2} =x.$$

We note that we may rewrite the functional equation for $F$ as
$$F = x\left(1+\frac{F}{1-F^2}\right),$$
and $F/x$ is the generating function for sequence A101785.

First we show that $G = F/(1-F)$. By (1) it is sufficient to show that
\begin{equation*}
x\left(\frac{F}{1-F}\right)^3 + (4x-2)\left(\frac{F}{1-F}\right)^2 + (4x-1)\frac{F}{1-F}+ x = 0.
\end{equation*}
We have
\begin{align*}
x\left(\frac{F}{1-F}\right)^3 + (4x-2)&\left(\frac{F}{1-F}\right)^2 + (4x-1)\frac{F}{1-F}+ x\\
&=x\frac{1+F-F^2}{(1-F)^3} - \frac{F(1+F)}{(1-F)^2} \\
&=\frac{F(1-F^2)}{1+F-F^2}\frac{1+F-F^2}{(1-F)^3} - \frac{F(1+F)}{(1-F)^2}=0.
\end{align*}

Now let
\begin{equation*}
S_q(x) =\sum_{n=0}^\infty R(n,q) x^{n+1}.
\end{equation*}
The recurrence for $R(n,q)$ is equivalent to the identity
\begin{equation}
S_q(x) =x+ xS_{q+2}(x) + x\sum_{j=0}^q (-1)^j S_j(x).
\tag{2}
\end{equation}
and the $S_q(x)$ are determined by (2) and the condition that each $S_q(x)$ is a power series in $x$ starting with $x$.
Now let
$$U(z) = \sum_{q=0}^\infty S_q(x) z^q.$$
Multiplying (2) by $z^{q+2}$ and summing on $q\ge0$ gives
\begin{equation}
z^2 U(z) = \frac{xz^2}{1-z} +x \bigl(U(z) -S_0(x) -S_1(x)z\bigr) + \frac{xz^2}{1-z}U(-z)\tag{3}
\end{equation}
and $U(z)$ is the unique solution of (3).

I claim that
\begin{equation}
S_q(x) = \frac{F}{(1-F)^{\lfloor q/2\rfloor+1}(1+F)^{\lceil q/2\rceil}},\tag{4}
\end{equation}
which is equivalent to
\begin{equation}
U(z) = \frac{F(1+F+z)}{1-F^2-z^2}.\tag{5}
\end{equation}
To verify this, we use (4) and (5) to express (3) in terms of $x$, $z$, and $F$, and then replace $x$ with $F(1-F^2)/(1+F-F^2)$.
We obtain an easily verified identity of rational function in $z$ and $F$. In particular,
$$\sum_{n=1}^\infty R(n-1,0) x^{n}=S_0(x) = \frac{F}{1-F} = G = \sum_{n=1}^\infty a(n) x^n.$$