En algunos teléfono no se incluye esa opción, pero no porque no se pueda grabar, sino porque en algunos países no es legal grabar llamadas, al menos no sin avisar a la otra persona. En España es legal mientras participes en la conversación, y no estás obligado a avisar.
Pero hay multitud de aplicaciones de grabación que puedes instalar desde Google Play Store. Yo te recomiendo la que he usado yo en móviles que no tenían la opción de forma nativa: All Call Recording. Cuando llamas o te llaman muestra un perqueño widget flotante que te permite iniciar la grabación. Entre sus ventajaas está el poder subir las grabaciones automáticamente a Google Drive.
https://play.google.com/store/apps/details?id=com.nll.acr