What it teaches
The shortest honest example of a plan that contains itself. To move four discs you move three out of the way, move the big one, and move the three back — and moving three is the same problem again.
A child does not need the word recursion to feel that, and the feeling is what the game is for: the moment they notice the four-disc puzzle is the three-disc puzzle twice.
What to look for
Start at three. Seven moves is short enough to hold in the head, and the pattern has to be seen there before four discs mean anything.
The useful question is "where does the biggest disc need to be, and what is in its way?" — which is the recursive step, asked in words.