Secondo me l'unico modo possibile per farlo ricorsivo sarebbe una soluzione tipo sommatoria, mi spiego meglio.

Inanzittuto dovrebbe avere una cosa del tipo

codice:
if(ordinato==1) return;
Una funzione che ad ogni "giro" controlli se l'array sia ordinato e modifichi il valore di ordinato

E infine (il succo della ricorsione) si potrebbe fare confrontando e invertendo (se necessario) b[i] e b[i+1]

A questo punto si potrebbe richiamare la funzione al posto che da i, da i+1.

In "verba" funziona, ma sono gli "scripta" a parlare XD