How to record phone conversation in iPhone 4?
Recorder
Recorder lets you record outgoing calls by using a 415 dial-in number, but for a fee ($2/hour, $13/8 hours).

Check it out on the iTunes store and purchase it for 99 cents