In particular, suppose a reporter or journalist calls a candidate for public office and starts asking questions. Is the reporter allowed to record the conversation? If so, is he required to notify the other person?
The answer depends on what state they are in. In some states, both parties must consent to being recorded. In the rest, only one party must consent. If the two are not in the same state, it may also depend on which states they are in. Here's a nice summary of the issues, and a fairly detailed list of the laws in each state. (Caveat: As the discussion in the comments shows, the summaries of each state's law are not always exact, so you should double check their claims.)
Edited to add:
In some states, you consent if the reporter sticks a microphone in your face:
Since you live in Washington, and asked about journalists, Washington law provides a narrow exception for journalists:
An employee of any regularly published newspaper, magazine, wire service, radio station, or television station acting in the course of bona fide news gathering duties on a full-time or contractual or part-time basis, shall be deemed to have consent to record and divulge communications or conversations otherwise prohibited by this chapter if the consent is expressly given or if the recording or transmitting device is readily apparent or obvious to the speakers.
What do you mean by “record”?
If “record” means taking notes, even verbatim notes if the journalist knows shorthand (which is a great skill for a journalist), then, absolutely.
If “record” means an audio recording with a piece of technology, then, it depends on where each person is and what technology is used and,perhaps what is being discussed.
The applicable law will generally be the more onerous of the law where each party is, so if the journalist is in a place where covert recording is OK but the politician is in a place where it isn’t, then it isn’t OK.
Because there is a phone call involved, Commonwealth law applies to the phone call. Under that law all parties must be informed if the phone is being recorded. However, if the call is placed on speaker and the conversation is recorded by a device not connected to the telecommunications network, then this law doesn’t apply.
Notwithstanding, new-south-wales law applies either way.
It is not legal to use a covert listening device to record a conversation you are not a party to. The key here is “covert” - if a reporter sticks a whacking great microphone in the politicians face, that’s not covert. Neither is obviously placing a recording device in plain view or asking “do you mind if I record this?” In those circumstances, you can make and publish the recording.
If you are a party to the conversation, you can record covertly for personal use but you can’t publish the recording without permission or legal excuse (e.g. to defend yourself in a defamation trial).
Can a journalist record a conversation without prior notice or consent? Yes.
Regardless of whether or not you are a journalist, no notice or permission is required to take and keep a record of any conversation in any jurisdiction that I am aware of. Anything you have to say about that conversation at a later time is legally deemed as hearsay. Having a record of the conversation ("eg. referring to your notes") may give your hearsay more weight depending on the circumstances. However, in most jurisdictions you do not have 'exclusive' ownership of that record, therefore your usage of that record (beyond purely personal) can be limited by the consents required in any or all of the various jurisdictions involved (yours, theirs, and/or the intended place of release). So using a voice or video recording you did not have prior consent for to 'prove' your hearsay description of a conversation would usually be inadmissible.
Continuing a conversation with someone who has identified themselves as a journalist gives implicit permission for a recording to be made and used as they see fit. If they have identified themselves as a journalist then there is reasonable expectation that the conversation is "on record". You would have to prove that the recording is incorrect and/or incomplete to have it excluded and that only happens after it is published
--- edit ---
Three down votes (at time of writing). One person expressed an opinion which was fair enough, but nobody has offered facts or counter arguments.
Fact 1 - anybody can make a record of anything. Fact 2 - public use of that record depends on consent. Fact 3 - consent is implied when speaking with identified journalists.