Church factorial can be implemented without recursion though.
Hint: consider a function that maps the pair <n,n!> to <(n+1),(n+1)!> ...
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.
Here it is in action computing the factorial of 6: