Let us define a logical function $p(n)$ that returns the primality of numbers of $n$ bits $x_{n-1}x_{n-2}\dots{x_0}$.
Assume there is some recursive definition $p(n)=f(p(n-1))$
Let us start from two-bit numbers of the form $x_1x_0$
decimal binary is_prime
0 00 0
1 01 0
2 10 1
3 11 1
The corresponding function is
$p(2)=x_1$
Let us go on to three-bit numbers. The function for two-bit numbers will be reused at length $3$ as $\overline{x_{2}}p(2)$, and there will be a new term accounting for numbers with the most significant bit on. These primes are $5$ and $7$, so the new term is $x_{2}\overline{x_{1}}x_{0}+x_{2}x_{1}x_{0} = x_{2}x_{0}$
Therefore,
$p(3)=\overline{x_2}x_{1}+x_{2}x_{0}$
For numbers with 4 bits, the function becomes
$p(4)=\overline{x_3}(\overline{x_2}x_{1}+x_{2}x_{0})+x_{3}(x_2\overline{x_1}+\overline{x_2}x_1)x_{0}$
And for five bits, we get
$p(5)=\overline{x_4}(\overline{x_3}(\overline{x_2}x_{1}+x_{2}x_{0})+x_{3}(x_2\overline{x_1}+\overline{x_2}x_1)x_{0})+ x_4 (\overline{x_3}\overline{x_2}\overline{x_1} + \overline{x_3}\overline{x_2}x_1 + \overline{x_3}x_2x_1 + x_3x_2\overline{x_1} + x_3x_2x_1 ) x_0$
In general, we have
$p(n)=\overline{x_{n-1}}p(n-1) + x_{n-1}q(n)x_0$
The question is how to define $q(n)$