I'm struggling with the concept of recursive convolutional codes.
Say we have the generator matrix
$$\begin{pmatrix} \frac{D}{1+D^3} & 1 & 0 \\ \frac{D^2}{1+D^3} & 0 & 1 \end{pmatrix}$$
which means the first column is $[D+D^4+D^7+ \dots; D^2 + D^5 + D^8 + \dots]$. Why doesn't this give the system infinitely many states, or at least in the order of the length of the input so far? As I understand, it's supposed to have only three states but I don't see how...
Any recursive LTI filter of finite order is equivalent to a non-recursive filter of infinite order.
Taking your first example, let $$H(D)=\frac{D}{1+D^3} \tag{1}$$
You can write this as $$H(D)= D(1-D^3+D^6-D^9+\cdots)=D - D^4+D^7-D^{10}+\cdots \tag{2}$$
(of course, in $GF(2)$ the substractions turn into sums, but I'm writing this in general).
This second form would lead to a non-recursive implementation, say:
$$y[n]=x[n-1]-x[n-4]+x[n-7] \cdots$$
but this is non-realizable (requires infinite delays). The direct recursive form $(1)$, instead, leads to the (causal, finite) implementation:
$$ y[n]+y[n-3]=x[n-1] \implies y[n]=x[n-1]-y[n-3] \tag{3}$$
This is the realizable and natural way (not the only one), and it requires three delays (or states), for storing past values - of the output.