[databus]

God, if I see another code example using Factorial I am going to hurl.

[silentbicycle]

What are some other simple examples of recursion, though?

Quicksort would be pretty good for this, but the straightforward recursive version has several edge cases that lead to bad performance.

Getting the length of a linked list is probably a better example:

  (* ocaml *)
  let rec length l = match l with
     | []   -> 0
     | h::t -> 1 + length t

  ; scheme
  (define (length l)
     (if (null? l)
         0
         (+ 1 (len (cdr l))))

Neither of these is tail-recursive, of course, but that's another post entirely.

Any other ideas?

[13ren]

Does performance matter when seeking "simple" examples?

I vote for quicksort - not because it's quick, but because its implementation has the same form as its proof. It's simple if you use the Erlang-style version.

[paulgb]

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).

[silentbicycle]

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

  map square [1, 2, 3, 4, 5] ---> [1, 4, 9, 16, 25]

is pretty simple, though.

[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.