I know this has been discussed in other threads, but I have to give my recent account and hope it helps others. I have a rooted Nexus 5. I used the One Click Root which was an unbelievably easy root. I am using stock KitKat. I tried finding a phone call recorder, but nothing would work. I finally found the Total Recall app, which worked for a while but decided it was going to work some days but not others. On any given day it would work for a few hours, quit for several and then start again. I emailed back and forth with Killer Mobile, but nothing worked. After reading through the XDA forums on the subject I stumbled across a couple of threads regarding the Call Recorder App from Skvalex. I heard some good things about it so I downloaded it along with Skvalex's AlsaMixer. I read somewhere that you needed that app as well. Don't know if that's true, but I downloaded AlsaMixer first and then Call Recorder. Call Recorder works great. I get a clear sound from both ends of the conversation and it works all the time. I have a week before I have to pay for it, but I can't figure out how to pay. You download the app for free, and in the settings there is a place that says to "buy the full version", but when you do it takes you to Google Play and the download. Beats me. Anyway, the app is working great for me. I don't know how it would work if you are not rooted or are flashing a different ROM. But if you are rooted and with stock KitKat, then this should work for you.
Mark
Mark