Tu código tiene un error que una vez sabido te va a parecer obvio: Cuando haces la llamada recursiva, guardas el resultado en la variable booleana enc
. ¡Pero te olvidas de comprobarla! Qué pasa si encuentras el elemento en el primer cuadrante? Pues que no estará en el tercer cuadrante y enc pasará de true a false, "olvidando" que ya habías encontrado el elemento
//Busca en primer cuadrante
enc = encontrarNumero(matriz, f0, fk, c0, ck, elem); //enc==true
//busca en el tercero
enc = encontrarNumero(matriz, fk+1, fN, c0, ck, elem); //enc==false
Por tanto tu algoritmo sólo encuentra los números que están en el último lugar que se mira, porque si se encuentran antes, se sigue buscando.