Apple - "Recent Items" menu item disappears from Apple menu
Rebuild LaunchServices
Library
From this discussion board I learned to "rebuild the LaunchServices library". I do not understand the details, but this one line executed in Terminal.app does the trick:
/System/Library/Frameworks/CoreServices.framework/Versions/A/Frameworks/LaunchServices.framework/Versions/A/Support/lsregister -kill -r -domain local -domain system -domain user
Then restart your Mac. Relaunching the Finder is not enough, you must restart your Mac to get back your Recent Items menu.
Good news: It works.
Bad news: The effect is temporary. Eventually (days, weeks) your Recent Items menu will either disappear or develop duplicates.
Because this is only a partial workaround, and not a true fix, I will not mark this Answer (my own) as Accepted. Hopefully someone else might post a real fix.
I suspect, but have not proven, that the real solution is a clean-install. I took some bad advice and upgraded in-place to Mavericks and El Capitan. Next time I do a major upgrade I will go back to the tried-and-true method of a clean install.