LineageOS's default phone app supports call recording out of the box. I'm using LineageOS 18. I don't know if this is true for earlier versions.