8
$\begingroup$

In writing recursive functions (functional style), I often need to refer to the current function (depending on the context). e.g.

f 0  = 0
f (S n) = f n + 2

Are there any functional languages that allow using a generic name such as this_function or self to be used instead of the specific function name f?

So, hypothetically, the above would be rewritten as

f 0  = 0
f (S n) = self n + 2

It seems to make the spot of recursion easier to identify and the intention clearer. Also, it seems to allow one to write recursive anonymous functions, e.g. a function to double a number in pseudo-code:

\n r -> if n > 0 then self (n - 1) (r + 2) else r

Does such facility exist or is it possible?

$\endgroup$
9
  • 11
    $\begingroup$ I actually think this obfuscates the meaning more than clarifies it. I don't generally make a recursive call because it's a recursive call. For instance, when I write append, I make a call to append because I've done some of the work and now I need to append two lists. The fact that it happens to be the same function is almost a coincidence. If it were a different fn that also appended it'd still work. I just need to ensure I make progress. This is often how I think about recursion: "do some of the work, then treat the function 'as though it already works' when making recursive calls" $\endgroup$ Feb 8 at 17:03
  • $\begingroup$ That perspective also naturally extends to mutually recursive functions, even when there are more than two functions involved. $\endgroup$ Feb 8 at 17:36
  • 7
    $\begingroup$ One issue is that you have to be very careful about a sort of dual of scoping. In many languages, \n r -> ... can best be understood as syntactic sugar for \n -> \r -> .... But your example, \n r -> ... self (n-1) (r+2) ... relies critically on \n r -> ... and \n -> \r -> ... having distinct meanings. Or consider f x = if x > 0 then (\n -> ...self...) else (\n -> 3); here you must decide whether self should refer to just the inner \n -> ... or to the entire f x = .... Of course all of these decisions can be made, it just may be more complicated than you first think. $\endgroup$ Feb 8 at 18:37
  • 1
    $\begingroup$ I agree with all these potential limitations, e.g. on mutual recursion, scoping and the implicitness. It's just an idea that occurred to me, and I was wondering it's being around. $\endgroup$
    – tinlyx
    Feb 9 at 2:15
  • 3
    $\begingroup$ @Absinthe by definition, a recursive function is one that calls itself. But in order to specify what "itself" is, the code for that function will typically include a name for itself, which then has to be looked up in an enclosing scope (possibly the global scope). In OP's example in Haskell syntax, the recursively-defined f has code that includes the symbol f itself. The goal is to make this recursive call without relying on the name. So, for example, it should be possible to rename the function and still have it work and make those recursive calls, without changing the code inside. $\endgroup$ Feb 11 at 4:19

7 Answers 7

10
$\begingroup$

APL

A few APL dialects support the glyph inside a dfn (which is pretty much a lambda) which refers to the dfn itself. See Dyalog documentation on recursion.

(I guess it depends if you consider APL a functional language or not, tbf it doesn't have a lot of features standard FP languages are supposed to have)

$\endgroup$
1
  • $\begingroup$ Thanks. The Implicit self-reference using '∇' APL counts though I don't know the language. $\endgroup$
    – tinlyx
    Feb 9 at 2:21
7
$\begingroup$

Forth

Recursion in Forth actually requires a construct like this, as a word is not visible inside its own definition. In order to recurse, you need to use the recurse word, like so:

: factorial ( n -- n! )
    dup 0> if
        dup 1- recurse *
    else
        drop 1
    endif
;
$\endgroup$
5
$\begingroup$

In Perl — which is not primarily a functional language, but does support functional programming styles — the keyword __SUB__ is a reference to the current subroutine; your last example could be written as

sub { my ($n, $r) = @_; $n > 0 ? __SUB__->($n-1, $r+2) : $r }

Wikipedia refers to this as anonymous recursion, and in addition to Perl and APL, it also mentions equivalent features in JavaScript and R.

$\endgroup$
1
  • $\begingroup$ Thanks for the link. I just noticed it today and it covers all of the languages mentioned thus far except for Mathematica. Maybe we can update the Wiki page? $\endgroup$ Feb 10 at 17:11
4
$\begingroup$

Mathematica, a definition of the factorial function:

If[#1 == 1, 1, #1 #0[#1 - 1]]&

(The ampersand indicates a definition of an anonymous function; #0 is the anonymous function itself, and #1 is the first argument to that function.)

$\endgroup$
3
$\begingroup$

In JavaScript, arguments.callee could be used, but it is now deprecated and invalid in strict mode.

function f(n) { return n === 0 ? 0 : arguments.callee(n-1) + 2; }
$\endgroup$
2
  • $\begingroup$ Doesn't this work by inspecting the runtime stack, rather than being an actual syntactic feature? $\endgroup$ Feb 11 at 4:20
  • $\begingroup$ I think so, but I still wanted to comment because JS is widely-used. $\endgroup$
    – corvus_192
    Feb 11 at 11:48
3
$\begingroup$

In R we have Recall. From the docs we see (calling ?Recall):

Recall is used as a placeholder for the name of the function in which it is called. It allows the definition of recursive functions which still work after being renamed, see example below.

## A trivial (but inefficient!) example:
fib <- function(n)
   if(n<=2) { if(n>=0) 1 else 0 } else Recall(n-1) + Recall(n-2)
fibonacci <- fib; rm(fib)
## renaming wouldn't work without Recall
fibonacci(10) # 55
$\endgroup$
3
$\begingroup$

C++

Since C++23 you can add an explicit object parameter to member functions and lambdas. You still have to give the parameter a name, but you would typically use self for that argument:

auto factorial = [](this auto self, int n) -> int {
    return n > 1 ? n * self(n - 1) : 1;
}
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .