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>
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>
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
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.
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
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'.
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>
REXX
The task was to check for a negative argument before doing the recursion.
Most other solutions assumed (it appears) that no further recursion (computation)
was to be preformed. Instead, this solution performs the check, and then correctly
computes the negative Fibonacci number.
The computation of any Fibonacci number (including negative ones) could be completed
without doing the (negative) check at all,
<lang rexx>
/*REXX program calculates the Nth Fibonacci number, N can be zero or neg*/
numeric digits 210000 /*prepare for some big 'uns. */
parse arg x y . /*allow a single number or range.*/
if x== then do; x=-10; y=-x; end /*no input? Then assume -10-->+10*/
if y== then y=x /*if only one number, show fib(n)*/
do k=x to y /*process each Fibonacci request.*/
say 'Fibonacci' k"="fib(k)
end
exit
/*─────────────────────────────────────FIB subroutine (recursive)───────*/ fib: procedure; parse arg n; na=abs(n) if na<2 then return na /*handle special cases. */ s=1 if n<0 then if n//2==0 then s=-1 return (fib(na-1)+fib(na-2))*s </lang> Output when using the default of no (none) input:
Fibonacci -10=-55 Fibonacci -9=34 Fibonacci -8=-21 Fibonacci -7=13 Fibonacci -6=-8 Fibonacci -5=5 Fibonacci -4=-3 Fibonacci -3=2 Fibonacci -2=-1 Fibonacci -1=1 Fibonacci 0=0 Fibonacci 1=1 Fibonacci 2=1 Fibonacci 3=2 Fibonacci 4=3 Fibonacci 5=5 Fibonacci 6=8 Fibonacci 7=13 Fibonacci 8=21 Fibonacci 9=34 Fibonacci 10=55
Ruby
This fib() method uses a recursive block. We must provide the block with a reference to itself. The simplest way is to use a local variable 'f' of the fib() method. The block is a closure that can access 'f'.
<lang ruby>def fib(n)
raise ArgumentError, "fib of negative" if n < 0
(f = proc { |n| n < 2 && n || f[n - 1] + f[n - 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>
To remove the local variable 'f' from the fib() method, we can use a second block to limit the scope of 'f', or change 'f' to a block parameter.
<lang ruby># Limit the scope of 'f' to a block.
- Kernel#catch calls the block and returns the value of the block.
def fib(n)
raise ArgumentError, "fib of negative" if n < 0
catch { (f = proc { |n| n < 2 && n || f[n - 1] + f[n - 2] })[n] }
# f is undefined here
end
- Change 'f' to a block parameter.
- Notice that f.tap { |f| r } => f
- but f.tap { |f| break r } => r
def fib(n)
raise ArgumentError, "fib of negative" if n < 0
proc { |f, n| n < 2 && n || f[f, n - 1] + f[f, n - 2] }
.tap { |f| break f[f, n] }
# f is undefined here
end</lang>
The problem with Ruby 1.8 is that a block cannot have its own variables. The previous code would only clobber the single varible 'n' of the fib() method. The fix is to define a recursive method. One can define a singleton method on a new object. This works with both Ruby 1.8 and Ruby 1.9.
<lang ruby>def fib(n)
raise ArgumentError, "fib of negative" if n < 0 o = Object.new # This singleton method is not polluting def o.call(n) # the namespace of any other objects. n < 2 && n || call(n - 1) + call(n - 2) end o.call n
end </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
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 where is the original argument, and 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.
- Programming Tasks
- Recursion
- Ada
- Ada examples needing attention
- Examples needing attention
- AutoHotkey
- Clojure
- Clojure examples needing attention
- Forth
- Forth examples needing attention
- Go
- J
- JavaScript
- Mathematica
- Perl
- PicoLisp
- Python
- REXX
- REXX examples needing attention
- Ruby
- Tcl
- UNIX Shell
- UNIX Shell examples needing attention
- Ursala
- PureBasic/Omit