Anonymous recursion

Anonymous recursion
You are encouraged to solve this task according to the task description, using any language you may know.

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>

AutoHotkey

If: <lang ahk>fib(n) { if(n < 0)

               return error
       else if(n < 2)
               return 1
       else
               return n * fib(n-1)

}</lang> Ternary: <lang ahk>fib(n) { return n < 0 ? "error" : n < 2 ? 1 : n * fib(n-1) }</lang>

C

Using scoped function fib_i inside fib, with GCC: <lang C>#include <stdio.h>

long fib(long x) {

       long fib_i(long n) { return n < 2 ? n : fib_i(n - 2) + fib_i(n - 1); };
       if (x < 0) {
               printf("Bad argument: fib(%ld)\n", x);
               return -1;
       }
       return fib_i(x);

}

long fib_i(long n) /* just to show the fib_i() inside fib() has no bearing outside it */ {

       printf("This is not the fib you are looking for\n");
       return -1;

}

int main() {

       long x;
       for (x = -1; x < 4; x ++)
               printf("fib %ld = %ld\n", x, fib(x));

       printf("calling fib_i from outside fib:\n");
       fib_i(3);

       return 0;

}</lang>

Output:

Bad argument: fib(-1)
fib -1 = -1
fib 0 = 0
fib 1 = 1
fib 2 = 1
fib 3 = 2
calling fib_i from outside fib:
This is not the fib you are looking for

C++

In C++ (as of the 2003 version of the standard, possibly earlier), we can declare class within a function scope. By giving that class a public static member function, we can create a function whose symbol name is only known to the function in which the class was derived.

<lang cpp>double fib(const double n) {

 if(n < 0)
 {
   throw "Invalid argument passed to fib";
 }
 else
 {
   class actual_fib
   {
     public:
       static double calc(const double n)
       {
         if(n < 2)
         {
           return n;
         }
         else
         {
           return calc(n-1) + calc(n-2);
         }
       }
   };

   return actual_fib::calc(n);
 }

} </lang>

The upcoming C++0x standard includes lambda functions which simplifies this. <lang cpp>#include <functional> using namespace std;

double fib(double n) {

 if(n < 0)
   throw "Invalid argument";
 
 function<double(double)> actual_fib = [&](double n)->double
 {
   if(n < 2) return n;
   return actual_fib(n-1) + actual_fib(n-2);
 };

 return actual_fib(n);

}</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]

 (when (neg? n)
   (throw (new IllegalArgumentException "n should be > 0")))
 (loop [n n, v1 1, v2 1] 
   (if (< n 2)
     v2
     (recur (dec n) v2 (+ v1 v2)))))

</lang>

Using an anonymous function

Common Lisp

This puts a function in a local label. The function is not anonymous, but the name fib1 is local and never pollutes the outside namespace.

<lang common lisp> (defun fib (number)

 "Fibonacci sequence function."
 (if (< number 0)
     (error "Error. The number entered: ~A is negative" number)
     (labels ((fib1 (n a b)
                (if (= n 0)
                    a
                    (fib1 (- n 1) b (+ a b)))))
       (fib1 number 0 1))))

</lang>

D

In D Anonymous delegates/functions can't refer themselves. Here an anonymous class is created, and by using opCall member function, the anonymous class object can take arguments and act like an anonymous function. The recursion is done by calling opCall inside itself. <lang d>import std.stdio: writeln;

int fib(int n)

   in {
       assert(n >= 0);
   }
   body {
       return (new class {
           int opCall(int m) {
               if (m < 2)
                   return m;
               else
                   return opCall(m - 1) + opCall(m - 2);
           }
       })(n);
   }

void main() {

   writeln(fib(39));

}</lang> Output:

63245986

Ela

Using fix-point combinator:

<lang ela>let fib n | n < 0 = fail "Negative n"

         | else = fix (\f n -> if n < 2 then n else f (n-1) + f (n-2)) n</lang>

Function 'fix' is defined in standard Prelude as follows:

<lang ela>let fix f = f (& fix f)</lang>

F#

Using a nested function:

The function 'fib2' is only visible inside the 'fib' function.

<lang fsharp>let fib = function

   | n when n < 0 -> None
   | n -> let rec fib2 = function
              | 0 | 1 -> 1
              | n -> fib2 (n-1) + fib2 (n-2)
           in Some (fib2 n)</lang>

Using a fixed point combinator:

<lang fsharp>let rec fix f x = f (fix f) x

let fib = function

   | n when n < 0 -> None
   | n -> Some (fix (fun f -> (function | 0 | 1 -> 1 | n -> f (n-1) + f (n-2))) n)</lang>

Output:

Both functions have the same output. <lang fsharp>[-1..5] |> List.map fib |> printfn "%A" [null; Some 1; Some 1; Some 2; Some 3; Some 5; Some 8]</lang>

Factor

One would never use anonymous recursion. The better way defines a private word, like fib2, and recurse by name. This private word would pollute the namespace of one source file.

To achieve anonymous recursion, this solution has a recursive quotation.

<lang factor>USING: kernel math ; IN: rosettacode.fibonacci.ar

fib ( n -- m )

   dup 0 < [ "fib of negative" throw ] when
   [
       ! If n < 2, then drop q, else find q(n - 1) + q(n - 2).
       [ dup 2 < ] dip swap [ drop ] [
           [ [ 1 - ] dip dup call ]
           [ [ 2 - ] dip dup call ] 2bi +
       ] if
   ] dup call( n q -- m ) ;</lang>

The name q in the stack effect has no significance; call( x x -- x ) would still work.

The recursive quotation has 2 significant disadvantages:

1. To enable the recursion, a reference to the quotation stays on the stack. This q impedes access to other things on the stack. This solution must use dip and swap to move q out of the way. To simplify the code, one might move q to a local variable, but then the recursion would not be anonymous.
2. Factor cannot infer the stack effect of a recursive quotation. The last line must have call( n q -- m ) instead of plain call; but call( n q -- m ) defers the stack effect check until runtime. So if the quotation has a wrong stack effect, the compiler would miss the error; only a run of fib would detect the error.

Falcon

Falcon allows a function to refer to itself by use of the fself keyword which is always set to the currently executing function. <lang falcon>function fib(x)

  if x < 0
     raise ParamError(description|"Negative argument invalid", extra|"Fibbonacci sequence is undefined for negative numbers")
  else
     return (function(y)
        if y == 0
           return 0
        elif y == 1
           return 1
        else
           return fself(y-1) + fself(y-2)
        end
     end)(x)  
  end

end

try >fib(2) >fib(3) >fib(4) >fib(-1) catch in e > e end</lang>

Output:

1
2
3
ParamError SS0000 at falcon.core.ParamError._init:(PC:ext.c): Negative argument invalid (Fibbonacci sequence is undefined for negative numbers)
  Traceback:
   falcon.core.ParamError._init:0(PC:ext.c)
   "/home/uDTVwo/prog.fam" prog.fib:3(PC:56)
   "/home/uDTVwo/prog.fam" prog.__main__:22(PC:132)

Forth

This example is incorrect. Please fix the code and remove this message. Details: The check for a negative argument is not outside the recursion.

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>

Go

Go has recursive types and function literals that are closures. This is enough to solve the task within the specified constraints.

Code is modeled after Y combinator code, but I'm not sure the result is really the Y combinator. I'm not even sure it's a fixed point combinator. It does, however, assemble function objects in a way that implements recursion and then calls them to perform the desired computation. <lang go>

package main

import "fmt"

type funType func(int, int, int) int type fixType func(fixType) funType

func main() {

   for _, n := range []int{5, 10, 1, 0, -1} {
       f, ok := func(n int) (int, bool) {
           switch {
           case n < 0:
               return 0, false
           case n < 2:
               return 1, true
           }
           return func(fix fixType) funType {
               return func(arg1, arg2, arg3 int) int {
                   fmt.Println("fixing...")
                   return fix(fix)(arg1, arg2, arg3)
               }
           }(func(fix fixType) funType {
               return func(left, term1, term2 int) int {
                   if left == 0 {
                       return term1 + term2
                   }
                   fmt.Println("recursing:", left, "terms left to compute")
                   return fix(fix)(left-1, term1+term2, term1)

               }
           })(n-2, 1, 1),
               true
       }(n)

       if ok {
           fmt.Printf("fib %d = %d\n", n, f)
       } else {
           fmt.Println("fib undefined for negative numbers")
       }
   }

} </lang> To demonstrate results, I loop over several test cases, showing normal terms, the special cases of 0 and 1, and the disallowed case of < 0. To illustrate operation of the combinator and the resulting recursive function object, I inserted a couple of test prints.

Output:

fixing...
recursing: 3 terms left
recursing: 2 terms left
recursing: 1 terms left
fib 5 = 8
fixing...
recursing: 8 terms left
recursing: 7 terms left
recursing: 6 terms left
recursing: 5 terms left
recursing: 4 terms left
recursing: 3 terms left
recursing: 2 terms left
recursing: 1 terms left
fib 10 = 89
fib 1 = 1
fib 0 = 1
fib undefined for negative numbers

Groovy

Groovy does not explicitly support anonymous recursion. This solution is a kludgy trick that takes advantage of the "owner" scoping variable (reserved word) for closures. <lang groovy>def fib = {

   assert it > -1
   {i -> i < 2 ? i : {j -> owner.call(j)}(i-1) + {k -> owner.call(k)}(i-2)}(it)

}</lang>

Test: <lang groovy>def fib0to20 = (0..20).collect(fib) println fib0to20

try {

   println fib(-25)

} catch (Throwable e) {

   println "KABOOM!!"
   println e.message

}</lang>

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
KABOOM!!
assert it > -1
       |  |
       |  false
       -25

Haskell

Haskell has two ways to use anonymous recursion. Both methods hide the 'anonymous' function from the containing module, however the first method is actually using a named function.

Named function:

We're defining a function 'real' which is only available from within the fib function. <lang haskell>fib :: Integer -> Maybe Integer fib n

 | n < 0 = Nothing
 | otherwise = Just $ real n
             where real 0 = 1
                   real 1 = 1
                   real n = real (n-1) + real (n-2)</lang>

Anonymous function:

This uses the 'fix' function to find the fixed point of the anonymous function. <lang haskell>import Data.Function (fix)

fib :: Integer -> Maybe Integer fib n

 | n < 0 = Nothing
 | otherwise = Just $ fix (\f -> (\n -> if n > 1 then f (n-1) + f (n-2) else 1)) n</lang>

Output:

Both functions provide the same output when run in GHCI. <lang haskell>ghci> map fib [-4..10] [Nothing,Nothing,Nothing,Nothing,Just 1,Just 1,Just 2,Just 3,Just 5,Just 8,Just 13,Just 21,Just 34,Just 55,Just 89]</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>

Note that arguments.callee will not be available in ES5 Strict mode.

K

<lang k>fib: {:[x<0; "Error Negative Number"; {:[x<2;x;_f[x-2]+_f[x-1]]}x]}</lang>

Examples:

<lang k> fib'!10 0 1 1 2 3 5 8 13 21 34

 fib -1

"Error Negative Number"</lang>

Lua

Using a Y combinator.

<lang lua>

local function Y(x) return (function (f) return f(f) end)(function(y) return x(function(z) return y(y)(z) end) end) end

return Y(function(fibs)

 return function(n)
   return n < 2 and 1 or fibs(n - 1) + fibs(n - 2)
 end

end)

</lang>

using a metatable (also achieves memoization)

<lang lua>

return setmetatable({1,1},{__index = function(self, n)

 self[n] = self[n-1] + self[n-2]
 return self[n]

end})

</lang>

Mathematica

An anonymous reference to a function from within itself is named #0, arguments to that function are named #1,#2..#n, n being the position of the argument. The first argument may also be referenced as a # without a following number, the list of all arguments is referenced with ##. Anonymous functions are also known as pure functions in Mathematica.

<lang Mathematica> check := #<0& fib := If[check[#],Throw["Negative Argument"],If[#<=1,1,#0[#-2]+#0[#-1]]&[#]]& fib /@ Range[0,10]

{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89} </lang>

Making sure that the check is only performed once.

<lang Mathematica> check := (Print[#];#<0)& fib /@ Range[0,4] 0 1 2 3 4

{1, 1, 2, 3, 5} </lang>

Perl

Translation of: PicoLisp

recur isn't built into Perl, but it's easy to implement.

<lang perl>sub recur (&@) {

   my $f = shift;
   local *recurse = $f;
   $f->(@_);

}

sub fibo {

   my $n = shift;
   $n < 0 and die 'Negative argument';
   recur {
       my $m = shift;
       $m < 3 ? 1 : recurse($m - 1) + recurse($m - 2);
   } $n;

}</lang>

One can also use caller to get the name of the current subroutine as a string, then call the sub with that string. But this won't work if the current subroutine is anonymous: caller will just return '__ANON__' for the name of the subroutine. Thus, the below program must check the sign of the argument every call, failing the task. Note that under stricture, the line no strict 'refs'; is needed to permit using a string as a subroutine.

<lang perl>sub fibo {

   my $n = shift;
   $n < 0 and die 'Negative argument';
   no strict 'refs';
   $n < 3 ? 1 : (caller(0))[3]->($n - 1) + (caller(0))[3]->($n - 2);

}</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>

Explanation: The above uses the 'recur' / 'recurse' function pair, which is defined as a standard language extensions as <lang PicoLisp>(de recur recurse

  (run (cdr recurse)) )</lang>

Note how 'recur' dynamically defines the function 'recurse' at runtime, by binding the rest of the expression (i.e. the body of the 'recur' statement) to the symbol 'recurse'.

PostScript

Library: initlib

Postscript can make use of the higher order combinators to provide recursion. <lang postscript> % primitive recursion /pfact {

 {1} {*} primrec}.

%linear recursion /lfact {

  {dup 0 eq}
  {pop 1}
  {dup pred} 
  {*}
  linrec}.

% general recursion /gfact {

   {0 eq}
   {succ}
   {dup pred}
   {i *}
   genrec}.

% binary recursion /fib {

   {2 lt} {} {pred dup pred} {+} binrec}.

</lang>

Prolog

Works with SWI-Prolog and module lambda, written by Ulrich Neumerkel found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl The code is inspired from this page : http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord#Hiord (p 106). It uses the Y combinator. <lang prolog>:- use_module(lambda).

fib(N, _F) :- N < 0, !, write('fib is undefined for negative numbers.'), nl.

fib(N, F) :-

   % code of Fibonacci
   PF     = \Nb^R^Rr1^(Nb < 2 ->

R = Nb

                       ;

N1 is Nb - 1, N2 is Nb - 2, call(Rr1,N1,R1,Rr1), call(Rr1,N2,R2,Rr1), R is R1 + R2 ),

   % The Y combinator.

   Pred = PF +\Nb2^F2^call(PF,Nb2,F2,PF),

   call(Pred,N,F).

</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>

R

R provides Recall() as a wrapper which finds the calling function, with limitations; Recall will not work if passed to another function as an argument.

<lang R>fib2 <- function(n) {

 (n >= 0) || stop("bad argument")
 ( function(n) if (n <= 1) 1 else Recall(n-1)+Recall(n-2) )(n)

}</lang>

Ruby

Ruby has no keyword for anonymous recursion.

We can recurse a block of code, but we must provide the block with a reference to itself. The easiest solution is to use a local variable.

Ruby with local variable

<lang ruby>def fib(n)

 raise RangeError, "fib of negative" if n < 0
 (fib2 = proc { |m| m < 2 ? m : fib2[m - 1] + fib2[m - 2] })[n]

end</lang>

<lang ruby>(-2..12).map { |i| fib i rescue :error } => [:error, :error, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]</lang>

Here 'fib2' is a local variable of the fib() method. Only the fib() method, or a block inside the fib() method, can call this 'fib2'. The rest of this program cannot call this 'fib2', but it can use the name 'fib2' for other things.

• The fib() method has two local variables 'fib2' and 'n'.
• The block has a local variable 'm' and closes on both 'fib2' and 'n'.

---

Caution! The recursive block has a difference from Ruby 1.8 to Ruby 1.9. Here is the same method, except changing the block parameter from 'm' to 'n', so that block 'n' and method 'n' have the same name.

<lang ruby>def fib(n)

 raise RangeError, "fib of negative" if n < 0
 (fib2 = proc { |n| n < 2 ? n : fib2[n - 1] + fib2[n - 2] })[n]

end</lang>

<lang ruby># Ruby 1.9 (-2..12).map { |i| fib i rescue :error } => [:error, :error, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

1. Ruby 1.8

(-2..12).map { |i| fib i rescue :error } => [:error, :error, 0, 1, 0, -3, -8, -15, -24, -35, -48, -63, -80, -99, -120]</lang>

Ruby 1.9 still shows the correct answer, but Ruby 1.8 shows the wrong answer. With Ruby 1.9, 'n' is still a local variable of the block. With Ruby 1.8, 'n' of the block closes on 'n' of the fib() method. All calls to the block share the 'n' of one call to the method. So fib2[n - 1] changes the value of 'n', and fib2[n - 2] uses the wrong value of 'n', thus the wrong answer.

Ruby with Hash

<lang ruby>def fib(n)

 raise RangeError, "fib of negative" if n < 0
 Hash.new { |fib2, m|
   fib2[m] = (m < 2 ? m : fib2[m - 1] + fib2[m - 2]) }[n]

end</lang>

This uses a Hash to memoize the recursion. After fib2[m - 1] returns, fib2[m - 2] uses the value in the Hash, without redoing the calculations.

• The fib() method has one local variable 'n'.
• The block has two local variables 'fib2' and 'm', and closes on 'n'.

Ruby with recur/recurse

Translation of: PicoLisp

Library: continuation

<lang ruby>require 'continuation' unless defined? Continuation

module Kernel

 module_function

 def recur(*args, &block)
   cont = catch(:recur) { return block[*args] }
   cont[block]
 end

 def recurse(*args)
   block = callcc { |cont| throw(:recur, cont) }
   block[*args]
 end

end

def fib(n)

 raise RangeError, "fib of negative" if n < 0
 recur(n) { |m| m < 2 ? m : (recurse m - 1) + (recurse m - 2) }

end</lang>

Our recursive block now lives in the 'block' variable of the Kernel#recur method.

To start, Kernel#recur calls the block once. From inside the block, Kernel#recurse calls the block again. To find the block, recurse() plays a trick. First, Kernel#callcc creates a Continuation. Second, throw(:recur, cont) unwinds the call stack until it finds a matching Kernel#catch(:recur), which returns our Continuation. Third, Kernel#recur uses our Continuation to continue the matching Kernel#callcc, which returns our recursive block.

Ruby with arguments.callee

Translation of: JavaScript

Library: continuation

<lang ruby>require 'continuation' unless defined? Continuation

module Kernel

 module_function

 def function(&block)
   f = (proc do |*args|
          (class << args; self; end).class_eval do
            define_method(:callee) { f }
          end
          ret = nil
          cont = catch(:function) { ret = block.call(*args); nil }
          cont[args] if cont
          ret
        end)
 end

 def arguments
   callcc { |cont| throw(:function, cont) }
 end

end

def fib(n)

 raise RangeError, "fib of negative" if n < 0
 function { |m|
   if m < 2
     m
   else
     arguments.callee[m - 1] + arguments.callee[m - 2]
   end
 }[n]

end</lang>

Our recursive block now lives in the 'block' variable of the Kernel#function method. Another block 'f' wraps our original block and sets up the 'arguments' array. Kernel#function returns this wrapper block. Kernel#arguments plays a trick to get the array of arguments from 'f'; this array has an extra singleton method #callee which returns 'f'.

Scala

Using a Y-combinator: <lang scala> def Y[A, B](f: (A ⇒ B) ⇒ (A ⇒ B)): A ⇒ B = f(Y(f))(_)

def fib(n: Int): Option[Int] =

 if (n < 0) None
 else Some(Y[Int, Int](f ⇒ i ⇒
   if (i < 2) 1
   else f(i - 1) + f(i - 2))(n))
     

-2 to 5 map (n ⇒ (n, fib(n))) foreach println </lang> Prints:

(-2,None)
(-1,None)
(0,Some(1))
(1,Some(1))
(2,Some(2))
(3,Some(3))
(4,Some(5))
(5,Some(8))

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

144

The code above can be written without even using a local variable to hold the lambda term, though this is generally less idiomatic because the code ends up longer and clumsier: <lang tcl>proc fib n {

   if {[incr n 0] < 0} {error "argument may not be negative"}
   apply {x {expr {
       $x < 2
         ? $x
         : [apply [lindex [info level 0] 1] [incr x -1]]
           + [apply [lindex [info level 0] 1] [incr x -1]]
   }}} $n

}</lang> However, we can create a recurse function that makes this much more straight-forward: <lang tcl># Pick the lambda term out of the introspected caller's stack frame proc tcl::mathfunc::recurse args {apply [lindex [info level -1] 1] {*}$args} proc fib n {

   if {[incr n 0] < 0} {error "argument may not be negative"}
   apply {x {expr {
       $x < 2 ? $x : recurse([incr x -1]) + recurse([incr x -1])
   }}} $n

}</lang>

UNIX Shell

The shell does not have anonymous functions. Every function must have a name. However, one can create a subshell such that some function, which has a name in the subshell, is effectively anonymous to the parent shell.

<lang bash>fib() {

 if test 0 -gt "$1"; then
   echo "fib: fib of negative" 1>&2
   return 1
 else
   (
     fib() {
       if test 2 -gt "$1"; then
         echo "$1"
       else
         echo $(( $(fib $(($1 - 1)) ) + $(fib $(($1 - 2)) ) ))
       fi
     }
     fib "$1"
   )
 fi

}</lang>

<lang bash>$ for i in -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12; do > fib $i > done fib: fib of negative fib: fib of negative 0 1 1 2 3 5 8 13 21 34 55 89 144</lang>

Ursala

<lang Ursala>#import nat

fib =

~&izZB?( # test the sign bit of the argument

  <'fib of negative'>!%,   # throw an exception if it's negative
  {0,1}^?<a(               # test the argument to a recursively defined function
     ~&a,                  # if the argument was a member of {0,1}, return it
     sum^|W(               # otherwise return the sum of two recursive calls
        ~&,                # to the function thus defined
        predecessor^~(     # with the respective predecessors of
           ~&,             # the given argument
           predecessor)))) # and the predecessor thereof</lang>

Anonymous recursion is often achieved using the recursive conditional operator, ( _ )^?( _ , _ ), which takes a predicate on the left and a pair of functions on the right, typically one for the base and one for the inductive case in a recursive definition. The form ^?< can be used if the relevant predicate is given by membership of the argument in a constant set, in which case only the set needs to be specified rather than the whole predicate.

The recursive conditional operator ^? differs from the ordinary conditional ? seen at the outermost level by arranging for its predicate and component functions to be given an input of the form $(f,a)$ where $a$ is the original argument, and $f$ is a copy of the whole function. Code within the function body may then access itself anonymously according to all the usual language idioms pertaining to deconstruction of tuples, and call itself by any of several recursion combinators, such as the pairwise recursion form W seen above.