Which languages support *recursive* function liter

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

Anonymous functions exist in C++0x with lambda, and they may be recursive, although I'm not sure about anonymously.

auto kek = [](){kek();}

Answer 2

You can do this in Matlab using an anonymous function which uses the dbstack() introspection to get the function literal of itself and then evaluating it. (I admit this is cheating because dbstack should probably be considered extralinguistic, but it is available in all Matlabs.)

f = @(x) ~x || feval(str2func(getfield(dbstack, 'name')), x-1)

This is an anonymous function that counts down from x and then returns 1. It's not very useful because Matlab lacks the ?: operator and disallows if-blocks inside anonymous functions, so it's hard to construct the base case/recursive step form.

You can demonstrate that it is recursive by calling f(-1); it will count down to infinity and eventually throw a max recursion error.

>> f(-1)
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

And you can invoke the anonymous function directly, without binding it to any variable, by passing it directly to feval.

>> feval(@(x) ~x || feval(str2func(getfield(dbstack, 'name')), x-1), -1)
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Error in ==> create@(x)~x||feval(str2func(getfield(dbstack,'name')),x-1)

To make something useful out of it, you can create a separate function which implements the recursive step logic, using "if" to protect the recursive case against evaluation.

function out = basecase_or_feval(cond, baseval, fcn, args, accumfcn)
%BASECASE_OR_FEVAL Return base case value, or evaluate next step
if cond
    out = baseval;
else
    out = feval(accumfcn, feval(fcn, args{:}));
end

Given that, here's factorial.

recursive_factorial = @(x) basecase_or_feval(x < 2,...
    1,...
    str2func(getfield(dbstack, 'name')),...
    {x-1},...
    @(z)x*z);

And you can call it without binding.

>> feval( @(x) basecase_or_feval(x < 2, 1, str2func(getfield(dbstack, 'name')), {x-1}, @(z)x*z), 5)
ans =
   120

Answer 3

It also seems Mathematica lets you define recursive functions using #0 to denote the function itself, as:

(expression[#0]) &

e.g. a factorial:

fac = Piecewise[{{1, #1 == 0}, {#1 * #0[#1 - 1], True}}] &;

This is in keeping with the notation #i to refer to the ith parameter, and the shell-scripting convention that a script is its own 0th parameter.

Answer 4

In C# you need to declare a variable to hold the delegate, and assign null to it to make sure it's definitely assigned, then you can call it from within a lambda expression which you assign to it:

Func<int, int> fac = null;
fac = n => n < 2 ? 1 : n * fac(n-1);
Console.WriteLine(fac(7));

I think I heard rumours that the C# team was considering changing the rules on definite assignment to make the separate declaration/initialization unnecessary, but I wouldn't swear to it.

One important question for each of these languages / runtime environments is whether they support tail calls. In C#, as far as I'm aware the MS compiler doesn't use the tail. IL opcode, but the JIT may optimise it anyway, in certain circumstances. Obviously this can very easily make the difference between a working program and stack overflow. (It would be nice to have more control over this and/or guarantees about when it will occur. Otherwise a program which works on one machine may fail on another in a hard-to-fathom manner.)

Edit: as FryHard pointed out, this is only pseudo-recursion. Simple enough to get the job done, but the Y-combinator is a purer approach. There's one other caveat with the code I posted above: if you change the value of fac, anything which tries to use the old value will start to fail, because the lambda expression has captured the fac variable itself. (Which it has to in order to work properly at all, of course...)

Answer 5

In Perl 6:

my $f = -> $n { if ($n <= 1) {1} else {$n * &?BLOCK($n - 1)} }
$f(42);  # ==> 1405006117752879898543142606244511569936384000000000

Answer 6

Clojure can do it, as fn takes an optional name specifically for this purpose (the name doesn't escape the definition scope):

> (def fac (fn self [n] (if (< n 2) 1 (* n (self (dec n))))))
#'sandbox17083/fac
> (fac 5)
120
> self
java.lang.RuntimeException: Unable to resolve symbol: self in this context

If it happens to be tail recursion, then recur is a much more efficient method:

> (def fac (fn [n] (loop [count n result 1]
                     (if (zero? count)
                       result
                       (recur (dec count) (* result count))))))