I've always thought an easy solution would be to pay private prisons based on recidivism. e.g. The government gives twenty percent of all future tax income from the inmate to the prison company - until the inmate is incarcerated again.

The government gains an incentive not to jail people unnecessarily (loss of revenue). Prisons get an incentive to rehabilitate and educate.