A code of length $n$ over an alphabet of $q\geq 2$ elements is called a full $k$-recursive code if it consists of all segments of length $n$ of a recurring sequence that satisfies some fixed (nonlinear in general) recursivity law $f(x_1,\ldots,x_k)$ of order $k\leq n$. Let $n^r(k,q)$ be the maximal number $n$ such that there exists such a code with distance $n-k+1$ (MDS-code). The condition $n^r(k, q)\geq n$ means that the function $f$ together with its $n-k-1$ sequential recursive derivatives forms an orthogonal system of $k$-quasigroups. We prove that if $q\notin\{2,6,14,18,26,42\}$, then $n^r(2,q)\geq 4$. The proof is reduced to constructing some special pairs of orthogonal Latin squares.