Rather than use analogy, I think it best to demonstrate the power of recursion on a problem for which the recursive solution is natural and the alternative solutions are an obvious exercise in masochism. Take the Towers of Hanoi problem. When one sees how the problem just cleaves and dissolves into the recursive formulation, that experience of awe will drive one to a deeper and more nuanced exploration of recursion. Elegant expression requires no analogy.

Rather than use analogy, I think it best to demonstrate the power of recursion on a problem for which the recursive solution is natural and the alternative solutions are an obvious exercise in masochism, to write and especially to prove. Take the Towers of Hanoi problem. When one sees how the problem just cleaves and dissolves into the recursive formulation, that experience of awe will drive one to a deeper and more nuanced exploration of recursion. Elegant expression requires no analogy.