[paulgb]

Agreed, map is a good example only if the person reading it gets first-class functions.

I can only think of a couple other suggestions for simple recursive functions. Euclid's algorithm for GCD would be a good one. Fibonacci numbers are easily expressed with recursion, but the most obvious solution is unfortunately not tail recursive and inefficient. My favorite example of mutual recursion is "even" and "odd":

even 0 = True even x = odd (x - 1)

odd 0 = False odd x = even (x - 1)

Inefficient, of course, but easy to prove correctness even to someone who's brain hasn't yet clicked into understanding recursion. Length of a list is as boring as factorials, but I guess that would be one too. Same with generating a list of counting numbers.

[silentbicycle]

I wonder if not getting first class functions is a consequence of already knowing too much, though. If you're thinking in C, you might get bogged down in thinking about passing around function pointers, but aside from implementation details, first class functions are not intimidating when the functions applied are familiar: "Take this list and do X to everything in it: square each number in a list of numbers, or convert every word to lowercase in a string list, or negate every bool in a bool list, etc.".

Euclid's algorithm is a really good example, by the way. Thanks.