Here is Church factorial in graphical notation:

  ┬──────────────────────
  │ ┬────────────── ─ ┬ ┬
  │ ┼─┬───────┬──── ┬ │ │
  │ ┼─┼───────┼─┬── │ │ │
  │ │ ┼─┬─┬── ┼─┼─┬ │ │ │
  │ │ ┼─┼─┼─┬ │ ├─┘ │ │ │
  │ │ └─┤ ├─┘ ├─┘   │ │ │
  │ │   ├─┘   │     │ │ │
  │ └───┤     │     │ │ │
  │     ├─────┘     │ │ │
  └─────┤           │ │ │
        └───────────┤ │ │
                    └─┤ │
                      └─┘

That's pretty cool looking, but I have no idea what I'm looking at. Does this notation have a name? Is it documented somewhere? (Hm, I wonder how hard it would be to write a parser for it. :-)

That's my graphical notation for lambda calculus, documented at http://www.cwi.nl/~tromp/cl/diagrams.html

Btw, here's an even shorter version of factorial:

  ┬────────────────
  ┼─────────────┬──
  │ ──┬──────── ┼ ┬
  │ ┬─┼─┬────── │ │
  │ │ │ ┼─┬─┬── │ │
  │ │ │ ┼─┼─┼─┬ │ │
  │ │ │ └─┤ ├─┘ │ │
  │ │ │   ├─┘   │ │
  │ │ ├───┘     │ │
  │ ├─┘         │ │
  └─┤           │ │
    └───────────┤ │
                └─┘

In de-Bruijn notation it is \\2 (\\1 (2 (\\3 2 (2 1)))) (\2) (\1), which in conventional notation is \n\f.n (\x\m.m (x (\a\b.m a (a b)))) (\x.f) (\x.x)

BTW, is there a description of how this works written up anywhere? I tried to reverse-engineer it and got lost in lambdas. (I did manage to translate it into Scheme and verify empirically that it works!)

Wow! That is wicked-cool! Thanks!

Whether the loop is recursive or iterative you still need a loop, so you still need a Y combinator.

You don't need Y if you apply a Church numeral instead, which gives you a bounded iteration.

Ah, good point!