The last time I had this working perfectly was with a Nexus 4 and I find that call recording apps do not work on newer phones I've bought since. Any suggestions? Android or iOS, I don't care which platform as long as it works well.
I used to set the app to only record incoming calls from callers not in my address book, and on several occasions it was a huge benefit to have these to refer to later.
Companies really do not like it when you email them recordings of their employee lying to you, and will go out of their way to make things right immediately when that happens.