Recast characters are those who were originally played by one actor, but the role was recast and played by another actor.
Stuntmen, body doubles, or different actors playing the same character at different points in their lifetime (i.e., Nell Williams as Young Cersei in Season 5) do not count as "recastings". Different actor-infants used to play the same baby character also count more as stuntmen than a significant "recasting".
Three major roles were prominently recast by Season 4: Ser Gregor Clegane, Daario Naharis, and Tommen Baratheon. Gregor Clegane was recast for Season 2 and yet again for Season 4. Daario Naharis was given a full introduction as a major new character in Season 3 with significant dialogue and primary interaction with Daenerys Targaryen, but was recast due to scheduling conflicts. Tommen Baratheon had appeared as a third-tier character in Season 1 and Season 2, and was recast for Season 4 by an older actor (who coincidentally appeared briefly as Tommen's first cousin Martyn Lannister in Season 3) to fit his more prominent role and mature storyline.
In season 4, the Three-Eyed Raven was played by Struan Rodger when Bran finally reaches his cave north of the wall. He is now played by veteran actor Max Von Sydow in season 6 to train Bran how to use the Weirwood trees for visions, both of the past and future.
In Season 6, the Night King was recast, with Vladimir Furdik replacing Richard Brake, who had appeared in one episode in both Seasons 4 and 5. Furdik also played the human who became the Night King in Bran's flashback of the Children of the Forest creating the White Walkers.
Minor role Joss Stilwood - Gregor's squire - was recast between Seasons 1 and 4, though he hadn't spoke prior, wasn't identified by name, and it isn't confirmed if they were really meant to be the same character.
The Lord of Bones was also recast for his brief return appearance in Season 5, though it was hard to tell given that he wears a face-obscuring mask, and he died at the end of the one scene he reappeared in.
Sort of a gray area are characters who were initially played by uncredited extras, then officially cast and introduced. Such characters weren't really a major "recasting" given that they were always meant to be recast at some point in the future, and had minimal screentime: they were just placeholder appearances because the character wouldn't be fully introduced until much later.
For example, the first High Septon (Before the riot of King's Landing) technically appeared in Season 1, but with no speaking lines and not identified as "the High Septon" except by his costume. Similarly, Selyse Baratheon technically appeared in the Season 2 premiere, but only appeared in a crowd shot, had no speaking lines, nor was she identified; we only know from casting information that this was actually supposed to be Selyse.
Beric Dondarrion and Rickard Karstark were "placeholders" in Season 1 before their main introduction in later seasons. They had one or two speaking lines but were not really intended to be longstanding figures in the roles.
Jaqen H'ghar is a persona adopted by several shapeshifters from the Faceless Men, but this "persona" is still played by the same actor. The actor and character were first introduced in Season 2, though a hooded figure appears in Yoren's prisoner cart during the Season 1 finale. This was also simply a "placeholder" and doesn't really merit being called a recasting: the actor wasn't cast until Season 2, and an extra was shot from behind wearing a hood to establish the on-screen continuity that Yoren was transporting some prisoners.