Moves can collect data without an internet connection. This data will be analyzed as soon as you have a connection again.
However, if you travel to a new country and do not have a data connection, the location services in your iPhone may be less accurate until you establish a network connection. Visiting a Wi-Fi hotspot just once can help the phone produce better location data.
On Android devices, location services are fairly dependent on data connection availability. This means that without data connection location data becomes less accurate, and this will affect recognition of places and routes.