And what if the other party doesn't want the call recorded?
Microsoft protect people's privacy in this way. There's call recorders on Android because they let people do whatever the want and respect of privacy is largely optional.
Call Recorders are available in Store, keep your cellphone in Speaker mode it will fulfill your Call Recording mood, before that ask to your caller can i Record this call ?....
You might want to carefully read reviews for any call recorder apps. Certainly don't pay for one without knowing absolutely that it works.
You most probably won't find any that will allow you to record phone calls. If it were possible, you would find lots of apps with lots of positive reviews.