I've tried a few approaches to explaining recursion ("just assume that it works", "trust yourself", "turn off your brain" (the latter of which is from Will Byrd)), but I like "Recursion Fairy" an awful lot. Might have to try that next time.
"Nothing to fear but fear itself: introducing recursion in lower secondary schools"
But the supporting tool is actually in Italian:
Enjoy!