Proving the (in)tractability of this Nth prime recurrence
The following paper shows that PRIMES is in P (it also won a Gödel award in 2006):

http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

By setting the solution of the Nth prime minimization procedure to the AKS PRIMES algorithm (modulo a subtraction), we may effectively get a tractable solution to the recurrence relation (if you can prove that the prime gap is given by the recurrence relation).

Source codes can be found on the internet. I am not pointing to them here because I did not check them personally.

As is however, we may still have the upper bound of $\sqrt{n}$ for checking all numbers...