Factorial is the hello world of functional programming. The fact that everyone knows it inside out aids the example, because the reader can focus on the important details (the Y Combinator).
Agreed, but in a parallel universe where the parent post actually asked the implied question, what other functions would you suggest? I try to explain these things to other people enough that I'd love to hear other suggestions.
Map might be another good one, although for better and worse it expects the reader to follow the idea of first class functions. Something like
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.
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.
Map might be another good one, although for better and worse it expects the reader to follow the idea of first class functions. Something like
is pretty simple, though.