Which languages support *recursive* function literals / anonymous functions?

Question

It seems quite a few mainstream languages support function literals these days. They are also called anonymous functions, but I don't care if they have a name. The important thing is that a function literal is an expression which yields a function which hasn't already been defined elsewhere, so for example in C, &printf doesn't count.

EDIT to add: if you have a genuine function literal expression <exp>, you should be able to pass it to a function f(<exp>) or immediately apply it to an argument, ie. <exp>(5).

I'm curious which languages let you write function literals which are recursive. Wikipedia's "anonymous recursion" article doesn't give any programming examples.

Let's use the recursive factorial function as the example.

Here are the ones I know:

• JavaScript / ECMAScript can do it with callee:

  function(n){if (n<2) {return 1;} else {return n * arguments.callee(n-1);}}
  

• it's easy in languages with letrec, eg Haskell (which calls it let):

  let fac x = if x<2 then 1 else fac (x-1) * x in fac

  and there are equivalents in Lisp and Scheme. Note that the binding of fac is local to the expression, so the whole expression is in fact an anonymous function.

Are there any others?

Answer 1

Most languages support it through use of the Y combinator. Here's an example in Python (from the cookbook):

# Define Y combinator...come on Gudio, put it in functools!
Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))

# Define anonymous recursive factorial function
fac = Y(lambda f: lambda n: (1 if n<2 else n*f(n-1)))
assert fac(7) == 5040

Answer 2

C#

Reading Wes Dyer's blog, you will see that @Jon Skeet's answer is not totally correct. I am no genius on languages but there is a difference between a recursive anonymous function and the "fib function really just invokes the delegate that the local variable fib references" to quote from the blog.

The actual C# answer would look something like this:

delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);

static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
    Recursive<A, R> rec = r => a => f(r(r))(a);
    return rec(rec);
}

static void Main(string[] args)
{
    Func<int,int> fib = Y<int,int>(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
    Func<int, int> fact = Y<int, int>(f => n => n > 1 ? n * f(n - 1) : 1);
    Console.WriteLine(fib(6));                          // displays 8
    Console.WriteLine(fact(6));
    Console.ReadLine();
}