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