he 4th Amendment doesn't cover foreigners engaging in war against the US or our allies, and the NSA is supposed to be looking for things like this.
Case law on this is very clear. When you have an expectation of privacy, a warrant is required. If you were on the phone in a public place, it's legal to record your half of the conversation, because you're speaking loudly in a public place. If you're at home, a warrant is required to record the phone call, because you have an expectation of privacy in your home.