EDIT: I was wrong, this is one of the permissions they require on Android, however, not on iOS as Apple doesn't make it available to third-party developers.
Almost all Android apps can do this in realtime, because to get the IMEI/device ID (a questionable thing in itself), Google decided you should also be required to have permissions to see who is calling/called.
It's a major privacy violation, with Google directly encouraging it for no good reason.
(Getting device ID should be a very rare, high-security permission; instead each app should get a unique app+deviceID. And seeing who is calling is likewise a rare thing that should be highly suspect. Or Google could add controls or do on-demand like MS and Apple do...)
I can't think of a valid reason why an app should require such permissions besides information gathering.. there are API for making you app talk, or discover other apps
