Using the recursion theorem to implement the Sieve of Eratosthenes. Update: I provided an answer here that shows how to define a mathematical function using the recursion theorem. This function can be reconfigured to compute the prime-counting function, $\pi(x)$.
Only one question remains:

Question 1: Has the Sieve of Eratosthenes already been mathematically
  revamped as a recursive function?

I did not find the word 'recursion' in the wikipedia article Generating primes, so this theory might be useful.
When running computers to get a list of all primes numbers using recursion, the 'state variables' should be retained for the next computer run.

The initial development was the construction of a Python program that maintained/updated state variables to generate, and keep generating, the list of prime numbers. I was using concepts found in the wiki article The Sieve of Eratosthenes.
 A: The Legendre formula, 
https://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_π(x)
http://mathworld.wolfram.com/LegendresFormula.html
which based on the sieve, is recursive: $\phi(x,a)=\phi(x,a-1)-\phi(\frac{x}{p_a},a-1)$. With it you can find $\pi(x)=\phi(x,a)+a-1$ where $a=\pi(\sqrt[2]{x})$.
However, I am not sure it is recursive the way you want it to be recursive
A: Here $\mathbb N = \{2,3,4,\dots\}$.
Let $\mathcal P$ denote the set of all finite subsets of $\mathbb N  \times \mathbb N$.
We define
$\tag 1 \gamma_n: \mathcal P \to \mathcal P$
$\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\;\;   \rho \mapsto \rho \cup \{(n,n+n)\}$
We define
$\tag 2 \mu_n: \mathcal P \to \mathcal P$
$\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\;\;  \rho \mapsto \rho \cup \{(m,n+m) \; | \; (m,n) \in \rho \}$
The mapping $\Gamma: \mathbb N \times \mathcal P \to \mathcal P$ is defined by
$$   
    \Gamma(n,\rho) = \left\{\begin{array}{lr}
        \gamma_n(\rho), & \text{when } n \notin \text{Range}(\rho)\\
        \mu_n(\rho), & \text{otherwise}
        \end{array}\right\} 
$$
Using the recursion theorem, we define
$\tag 3 \mathtt E: \mathbb N \cup \{1\} \to \mathcal P \quad \quad \text{ by }$
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \mathtt E(1) = \emptyset$
$\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \mathtt E(n+1) = \Gamma(n+1,\mathtt E(n))$
The function $\mathtt E$ has the property that the projection of $\mathtt E(n)$ onto the first coordinate is the set of all prime numbers less than or equal to $n$. So, letting $pr_1$ denote this projection, we define
$\tag 4 \pi': \mathbb N \to \mathbb N$
$\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\;\;  n \mapsto \text{#} \left[\, pr_1(\mathtt E(n))\,\right]$
so that $\pi'(n)$ is the set of all primes less than or equal to $n$. It is immediate that this function is the restriction of the prime-counting function $\pi$ to $\mathbb N$.
Values of $\mathtt E(n)$ for $n \le 11:$
E(2) = {(2, 4)}
E(3) = {(2, 4), (3, 6)}
E(4) = {(2, 6), (2, 4), (3, 6)}
E(5) = {(2, 6), (5, 10), (2, 4), (3, 6)}
E(6) = {(2, 6), (5, 10), (3, 9), (3, 6), (2, 8), (2, 4)}
E(7) = {(7, 14), (2, 6), (5, 10), (3, 9), (3, 6), (2, 8), (2, 4)}
E(8) = {(7, 14), (2, 6), (5, 10), (3, 9), (3, 6), (2, 8), (2, 4), (2, 10)}
E(9) = {(7, 14), (2, 6), (5, 10), (3, 9), (3, 6), (3, 12), (2, 8), (2, 4), (2, 10)}
E(10) = {(7, 14), (2, 6), (5, 10), (3, 12), (2, 8), (2, 10), (3, 9), (5, 15), (2, 12), (3, 6), (2, 4)}
E(11) = {(7, 14), (2, 6), (5, 10), (3, 12), (2, 8), (11, 22), (2, 10), (3, 9), (5, 15), (2, 12), (3, 6), (2, 4)}

Note: These function values came from the Python program. Since mathematics is not concerned with 'efficiency' in any way, the program was 'dumbed down' so the outputs of $\mathtt E$ can contain elements that are no longer used by the recursion algorithm; this made it easier to define the algorithm.
