The option shows for me. You have to choose an application to handle the recording in settings. Typically Voice Recorder, but you have to set it yourself. It is blank by default.
That said, I cannot hear my recordings when I try and play them back... which is a pretty big bummer. Call recording was a big part of my purchase decision. I regularly speak to filmmakers and actors for media obligations, and having native call recording would be so cool--if it worked.
But yeah--this is something that should be handled in settings under the Phone option. You shouldn't have to download anything additional.