The playlist "recently added" is a smart playlist (created by iTunes) and lists quite some songs in iTunes on the Mac. The library is kept in the iCloud by iTunes match, so the songs and the playlists are synced automatically to the iPhone. But "recently added" always is empty on the iPhone (unlike most other playlists).
You're not the only one suffering from this issue. A lot of people are complaining on the internet about this.
A solution would be to turn off iTunes Match on your iPhone, delete all your music on your iPhone (it's all in the iCloud, right? So you won't lose any) and then activate iTunes Match on your iPhone. You'll be able to download all your play-lists, including the recently added.
This should do the trick.