En general, Android no permite grabar llamadas y los grabadores usan el truco de activar el manos libres y grabar a la otra parte por el micrófono por lo que la calidad es pésima.
Hay excepciones, con algunos dispositivos y versiones de firmware el fabricante sí que añade esa posibilidad y algunas apps la aprovechan pero depende de qué dispositivo y versión concretos tengas. Así que no te dejes guiar por opiniones de gente que no tenga tu mismo dispositivo.
Por último, siendo root sí que hay más opciones porque ya no estás limitado por los mecanismos de seguridad que impone Android.