There are many programs that I have always been assigned when learning a new language that help you grasp the basics.

Odd that both examples you gave are usually the ones that programming books give to teach recursion. I wouldn't exactly call that a basic topic for most new-to-programming types. I always mention recursion and dance around it for a little while to expand a few brains in the audience. Then take those students who are prepared for it (aside) on an adventure through factorials, fibonacci, reversing strings/arrays (non-perl classes), and to cut the wheat from the chaff: Towers of Hanoi.

It's terribly useful when you need it, it's good that they're aware of it even to point out some uses (trees, etc...) but when they're busy grasping the concept of what a subroutine/function is, it can be a but much. Forget recursion for most, come back to it later when you can traverse directory structures or search b-trees or something.

PS: The other problem I've had with Fibonacci and factorials in particular is they're terribly easy to program, but they're not useful in everyday life. If I have to explain the math (which with those two to an average audience, I usually do) it's not worth the trip.