1. Initiate the native Maps app
2. Tap on the search bar
3. Tap on "Favorites"
4. At the bottom, tap on "recents"
5. Finally, tap on "Clear" in the upper left corner and then tap on "Clear All Recents" at the bottom.
6. Select "Done" in the upper right corner.