The problem with recursion (and with the counting example in the post) is that a student will ask "why can't I do this with a loop?" It's better to use a problem where recursion MUST be used, such as a binary tree:

The size (# of nodes) of a binary tree is:

- 0, if the tree is empty, or

- size of left subtree + size of right subtree + 1

If you draw a tree, any student will agree that the recursive method makes sense. Indeed, they would be hard-pressed to come up with solution that uses a loop (unless they know about stacks, OK OK).