Anonymous recursion

While implementing a recursive function, it often happens that we must resort to a separate "helper function" to handle the actual recursion.

This is usually the case when directly calling the current function would waste too many resources (stack space, execution time), cause unwanted side-effects, and/or the function doesn't have the right arguments and/and return values.

So we end up inventing some silly name like "foo2" or "foo_helper". I have always found it painful to come up with a proper name, and see a quite some disadvantages:

You have to think up a name, which then pollutes the namespace
A function is created which is called from nowhere else
The program flow in the source code is interrupted

Some languages allow you to embed recursion directly in-place. This might work via a label, a local gosub instruction, or some special keyword.

Anonymous recursion can also be accomplished using the Y combinator.

If possible, demonstrate this by writing the recursive version of the fibonacci function (see Fibonacci sequence) which checks for a negative argument before doing the actual recursion.

Ada

In Ada you can define functions local to other functions/procedures. This makes it invisible to outside and prevents namespace pollution.

Better would be to use type Natural instead of Integer, which lets Ada do the magic of checking the valid range. <lang Ada> function Fib (X: in Integer) return Integer is

     function Actual_Fib (N: in Integer) return Integer is
     begin
        if N < 2 then
           return N;
        else
           return Actual_Fib (N-1) + Actual_Fib (N-2);
        end if;
     end Actual_Fib;
  begin
     if X < 0 then
        raise Constraint_Error;
     else
        return Actual_Fib (X);
     end if;
  end Fib;</lang>

Clojure

The JVM as of now has no Tail call optimization so the default way of looping in Clojure uses anonymous recursion so not to be confusing. <lang clojure> (defn fib [n]

   (loop [n n, v1 1, v2 1]

(cond (< n 0) (throw (new IllegalArgumentException "n should be > 0")) (< n 2) v2 true (recur (- n 1) v2 (+ v1 v2))))) </lang>

Forth

Recursion is always anonymous in Forth, allowing it to be used in anonymous functions. <lang forth>defer fib

noname ( n -- fib )

 dup 2 < if 0 max exit then
 1- dup recurse swap 1- recurse + ;  is fib

test ( n -- ) 0 do i fib . loop ;

11 test</lang>

J

Copied directly from the fibonacci sequence task, which in turn copied from one of several implementations in an essay on the J Wiki: <lang j> fibN=: (-&2 +&$: -&1)^:(1&<) M."0</lang>

Note that this is an identity function for arguments less than 1 (and 1 (and 5)).

Examples: <lang j> fibN 12 144

  fibN  i.31

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040</lang>

(This implementation is doubly recursive except that results are cached across function calls.)

$: is an anonymous reference to the largest containing verb in the sentence.

JavaScript

<lang javascript>function fibo(n) {

 if (n < 0)
   throw "Argument cannot be negative";
 else
   return (function(x) {
     if (n < 2)
       return 1;
     else
       return arguments.callee(n-1) + arguments.callee(n-2);
   })(n);

}</lang>

PicoLisp

<lang PicoLisp>(de fibo (N)

  (if (lt0 N)
     (quit "Illegal argument" N) )
  (recur (N)
     (if (> 2 N)
        1
        (+ (recurse (dec N)) (recurse (- N 2))) ) ) )</lang>

Python

<lang python>>>> Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args))) >>> fib = lambda f: lambda n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2))) >>> [ Y(fib)(i) for i in range(-2, 10) ] [None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</lang>

Tcl

This solution uses Tcl 8.5's lambda terms, extracting the current term from the call stack using introspection (storing it in a local variable only for convenience, with that not in any way being the name of the lambda term; just what it is stored in, and only as a convenience that keeps the code shorter). The lambda terms are applied with the apply command. <lang tcl>proc fib n {

   # sanity checks
   if {[incr n 0] < 0} {error "argument may not be negative"}
   apply {x {

if {$x < 2} {return $x} # Extract the lambda term from the stack introspector for brevity set f [lindex [info level 0] 1] expr {[apply $f [incr x -1]] + [apply $f [incr x -1]]}

   }} $n

}</lang> Demonstrating: <lang tcl>puts [fib 12]</lang> Prints