It’s all a question of definition. In the Middle Ages, 1000 years ago, or in the Stone Age, 10 000 years ago, people ate grain gruel/ stew. When the potato arrived, it was added as part of the stew, along with spices from the spice islands. Does this count as traditional recipe or a new one?
Likewise, while the Italians invented the Pizza Margharita for their new Queen rather late, and the currently traditional Italian pizza is with Tomato sauce, the idea of a flat bread with stuff on top can be found in many cuisines. The Turkish imbiss places call their Lamacun Turkish pizza so people know what it is.
And while Spaghetti with tomato sauce had to wait for Columbus, Spaghetti with other sauces like Alio e Olio (garlic and oil) were traditional before, since legend has it that Marco Polo brought the noodles from China to Italy. (Since it’s doubtful he went all the way, or rather, just travelled part of the silk road and listened to stories from other relays, him bringing back noodle recipes is also a bit doubtful).
On the other hand, traditions can form and spread quickly. In the 50s and 60s,Currywurst was a new street food in Germany. But in the 90s, it was overtaken by the rising star of popularity, the Döner Kebap (from the many Turkish eateries).
The new trend in the last 10 years (besides the rise of Sushi everywhere) is Wraps - they came over from America, and now everything is being wrapped, even things that were never wrapped before.