Which is closer to how it should be taught. The factorial example is trivial and too familiar. It's easy for students to think "Oh, I know that" when in fact t

Which is closer to how it should be taught. The factorial example is trivial and too familiar. It's easy for students to think "Oh, I know that" when in fact they don't get it at all. Recursive operations on data structures are more likely to be unfamiliar. And you need something unfamiliar to demonstrate the point and also illustrate how it's likely to be used in practice.