Algunos teléfonos puede que cuenten con la grabación nativa, como por ejemplo Xiaomi (no lo sé actualmente ya que el último, y acabé harto de Xiaomi, fue el MI8).
Puede que tengas la opción, dependerá del teléfono que tengas, que necesite desbloqueo de bootloader, root y puede que CustomROM para poder utilizar la grabación de llamadas.
Las aplicaciones, la última vez que lo intenté, no funcionaba ninguna, como máximo te grababan a tí pero no la conversación completa.
Puede que te baste con el desbloqueo de bootloader, el root, TWRP o similar (aunque después puede sobrar, pero yo lo dejaría) y algún módulo de Magisk para la grabación de llamadas.
En por ejemplo el S9+ la Custom que está instalada es básicamente la Stock y tiene la grabación de llamadas aunque Samsung lo capara, por lo que no necesitarías otras como Lineage, ...
Entre google, fabricantes y demás, con la supuesta ilegalidad (en Expaña sigue siendo legal la grabación, cuestión aparte como la emplees) no te permiten ninguna aplicación de llamadas, de forma nativa eliminadas directamente e imposibilidad de instalar nada (que sea funcional).
De Stock ya te digo que no sé si quedará Xiaomi y alguna más que lo permitan y del resto olvídate, aún siendo marcas chinas.
