Keep in mind that call recording is illegal in some countries and states. However, certain Android roms support call recording on an OS level. I do not know of any apps that provide this: I'm fairly certain it requires OS support.
My dad has a simple flip phone, that I was messing around with the other day & found out the while you are talking on the phone you can push options the go down to voice memo activate it, then push the speaker phone button & it records what ever voice memo is hearing, (it's working through the microphone) (that's why it best to have it on speaker phone). My phone (the cheapest candy bar phone) won't let me do voice memo while I'm talking on the phone, in fact it takes 3 buttons to be pushed before I can even put on the speaker phone mode. I tried the same thing that I was doing with my dad's phone yesterday, with a fancy phone that friend has & it worked with his phone also.