Anonymous recursion: Difference between revisions
jq |
|||
(184 intermediate revisions by 76 users not shown) | |||
Line 1: | Line 1: | ||
{{task|Recursion}} |
{{task|Recursion}} |
||
While implementing a recursive function, it often happens that we must resort to a separate "helper function" to handle the actual 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/or return values. |
|||
This is usually the case when directly calling the current function would waste too many resources (stack space, execution time), causing unwanted side-effects, and/or the function doesn't have the right arguments and/or 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: |
|||
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 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 |
|||
::* You have to think up a name, which then pollutes the namespace |
|||
Some languages allow you to embed recursion directly in-place. This might work via a label, a local ''gosub'' instruction, or some special keyword. |
|||
::* 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]]. |
|||
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. |
|||
;Task: |
|||
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. |
|||
;Related tasks: |
|||
:* [[Y combinator]] |
|||
<br><br> |
|||
=={{header|11l}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="11l">F fib(n) |
|||
F f(Int n) -> Int |
|||
I n < 2 |
|||
R n |
|||
R @f(n - 1) + @f(n - 2) |
|||
R f(n) |
|||
L(i) 0..20 |
|||
print(fib(i), end' ‘ ’)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
Line 20: | Line 43: | ||
Better would be to use type Natural instead of Integer, which lets Ada do the magic of checking the valid range. |
Better would be to use type Natural instead of Integer, which lets Ada do the magic of checking the valid range. |
||
< |
<syntaxhighlight lang="ada"> function Fib (X: in Integer) return Integer is |
||
function Actual_Fib (N: in Integer) return Integer is |
function Actual_Fib (N: in Integer) return Integer is |
||
begin |
begin |
||
Line 35: | Line 58: | ||
return Actual_Fib (X); |
return Actual_Fib (X); |
||
end if; |
end if; |
||
end Fib;</ |
end Fib;</syntaxhighlight> |
||
=={{header|ALGOL 68}}== |
|||
{{Trans|Ada}} |
|||
<syntaxhighlight lang="algol68">PROC fibonacci = ( INT x )INT: |
|||
IF x < 0 |
|||
THEN |
|||
print( ( "negative parameter to fibonacci", newline ) ); |
|||
stop |
|||
ELSE |
|||
PROC actual fibonacci = ( INT n )INT: |
|||
IF n < 2 |
|||
THEN |
|||
n |
|||
ELSE |
|||
actual fibonacci( n - 1 ) + actual fibonacci( n - 2 ) |
|||
FI; |
|||
actual fibonacci( x ) |
|||
FI; |
|||
</syntaxhighlight> |
|||
=={{header|APL}}== |
|||
APL has the symbol <code>∇</code> which calls the current function recursively. |
|||
Functions can be defined and then called in place without ever assigning them a name, |
|||
though they are not quite first-class objects (you can't have an array of functions for example). |
|||
<syntaxhighlight lang="apl">fib←{ ⍝ Outer function |
|||
⍵<0:⎕SIGNAL 11 ⍝ DOMAIN ERROR if argument < 0 |
|||
{ ⍝ Inner (anonymous) function |
|||
⍵<2:⍵ |
|||
(∇⍵-1)+∇⍵-2 ⍝ ∇ = anonymous recursive call |
|||
}⍵ ⍝ Call function in place |
|||
}</syntaxhighlight> |
|||
=={{header|AppleScript}}== |
|||
<syntaxhighlight lang="applescript">on fibonacci(n) -- "Anonymous recursion" task. |
|||
-- For the sake of the task, a needlessly anonymous local script object containing a needlessly recursive handler. |
|||
-- The script could easily (and ideally should) be assigned to a local variable. |
|||
script |
|||
property one : 1 |
|||
property sequence : {} |
|||
on f(n) |
|||
if (n < 2) then |
|||
set end of my sequence to 0 |
|||
if (n is 1) then set end of my sequence to one |
|||
else |
|||
f(n - 1) |
|||
set end of my sequence to (item -2 of my sequence) + (end of my sequence) |
|||
end if |
|||
end f |
|||
end script |
|||
-- Don't insert any additional code here! |
|||
-- Sort out whether the input's positive or negative and tell the object generated above to do the recursive business. |
|||
tell result |
|||
if (n < 0) then |
|||
set its one to -1 |
|||
set n to -n |
|||
end if |
|||
f(n) |
|||
return its sequence |
|||
end tell |
|||
end fibonacci |
|||
fibonacci(15) --> {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610} |
|||
fibonacci(-15) --> {0, -1, -1, -2, -3, -5, -8, -13, -21, -34, -55, -89, -144, -233, -377, -610}</syntaxhighlight> |
|||
Or, as the recursion of an anonymous declarative function, enabled by the Y combinator: |
|||
<syntaxhighlight lang="applescript">------------ ANONYMOUS RECURSION WITH THE Y-COMBINATOR -------- |
|||
on run |
|||
--------------------- FIBONACCI EXAMPLE ------------------- |
|||
script |
|||
on |λ|(f) |
|||
script |
|||
on |λ|(n) |
|||
if 0 > n then return missing value |
|||
if 0 = n then return 0 |
|||
if 1 = n then return 1 |
|||
(f's |λ|(n - 2)) + (f's |λ|(n - 1)) |
|||
end |λ| |
|||
end script |
|||
end |λ| |
|||
end script |
|||
unlines(map(showList, chunksOf(12, ¬ |
|||
map(|Y|(result), enumFromTo(-2, 20))))) |
|||
end run |
|||
------------------------ Y COMBINATOR ---------------------- |
|||
on |Y|(f) |
|||
script |
|||
on |λ|(y) |
|||
script |
|||
on |λ|(x) |
|||
y's |λ|(y)'s |λ|(x) |
|||
end |λ| |
|||
end script |
|||
f's |λ|(result) |
|||
end |λ| |
|||
end script |
|||
result's |λ|(result) |
|||
end |Y| |
|||
----------- GENERIC FUNCTIONS FOR TEST AND DISPLAY --------- |
|||
-- chunksOf :: Int -> [a] -> [[a]] |
|||
on chunksOf(k, xs) |
|||
script |
|||
on go(ys) |
|||
set ab to splitAt(k, ys) |
|||
set a to item 1 of ab |
|||
if {} ≠ a then |
|||
{a} & go(item 2 of ab) |
|||
else |
|||
a |
|||
end if |
|||
end go |
|||
end script |
|||
result's go(xs) |
|||
end chunksOf |
|||
-- enumFromTo :: Int -> Int -> [Int] |
|||
on enumFromTo(m, n) |
|||
if n < m then |
|||
set d to -1 |
|||
else |
|||
set d to 1 |
|||
end if |
|||
set lst to {} |
|||
repeat with i from m to n by d |
|||
set end of lst to i |
|||
end repeat |
|||
return lst |
|||
end enumFromTo |
|||
-- intercalate :: String -> [String] -> String |
|||
on intercalate(delim, xs) |
|||
set {dlm, my text item delimiters} to ¬ |
|||
{my text item delimiters, delim} |
|||
set s to xs as text |
|||
set my text item delimiters to dlm |
|||
s |
|||
end intercalate |
|||
-- map :: (a -> b) -> [a] -> [b] |
|||
on map(f, xs) |
|||
tell mReturn(f) |
|||
set lng to length of xs |
|||
set lst to {} |
|||
repeat with i from 1 to lng |
|||
set end of lst to |λ|(item i of xs, i, xs) |
|||
end repeat |
|||
return lst |
|||
end tell |
|||
end map |
|||
-- Lift 2nd class handler function into 1st class script wrapper |
|||
-- mReturn :: Handler -> Script |
|||
on mReturn(f) |
|||
if class of f is script then |
|||
f |
|||
else |
|||
script |
|||
property |λ| : f |
|||
end script |
|||
end if |
|||
end mReturn |
|||
-- showList :: [a] -> String |
|||
on showList(xs) |
|||
intercalate(", ", map(my str, xs)) |
|||
end showList |
|||
-- splitAt :: Int -> [a] -> ([a], [a]) |
|||
on splitAt(n, xs) |
|||
if n > 0 and n < length of xs then |
|||
if class of xs is text then |
|||
{items 1 thru n of xs as text, ¬ |
|||
items (n + 1) thru -1 of xs as text} |
|||
else |
|||
{items 1 thru n of xs, items (n + 1) thru -1 of xs} |
|||
end if |
|||
else |
|||
if n < 1 then |
|||
{{}, xs} |
|||
else |
|||
{xs, {}} |
|||
end if |
|||
end if |
|||
end splitAt |
|||
-- str :: a -> String |
|||
on str(x) |
|||
x as string |
|||
end str |
|||
-- unlines :: [String] -> String |
|||
on unlines(xs) |
|||
-- A single string formed by the intercalation |
|||
-- of a list of strings with the newline character. |
|||
set {dlm, my text item delimiters} to ¬ |
|||
{my text item delimiters, linefeed} |
|||
set s to xs as text |
|||
set my text item delimiters to dlm |
|||
s |
|||
end unlines</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>missing value, missing value, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 |
|||
55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765</pre> |
|||
=={{header|Arturo}}== |
|||
{{trans|Nim}} |
|||
<syntaxhighlight lang="rebol">fib: function [x][ |
|||
; Using scoped function fibI inside fib |
|||
fibI: function [n][ |
|||
(n<2)? -> n -> add fibI n-2 fibI n-1 |
|||
] |
|||
if x < 0 -> panic "Invalid argument" |
|||
return fibI x |
|||
] |
|||
loop 0..4 'x [ |
|||
print fib x |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0 |
|||
1 |
|||
1 |
|||
2 |
|||
3</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">Fib(n) { |
||
nold1 := 1 |
nold1 := 1 |
||
nold2 := 0 |
nold2 := 0 |
||
Line 60: | Line 336: | ||
} |
} |
||
Return t |
Return t |
||
}</ |
}</syntaxhighlight> |
||
=={{header|AutoIt}}== |
|||
<syntaxhighlight lang="autoit"> |
|||
ConsoleWrite(Fibonacci(10) & @CRLF) ; ## USAGE EXAMPLE |
|||
ConsoleWrite(Fibonacci(20) & @CRLF) ; ## USAGE EXAMPLE |
|||
ConsoleWrite(Fibonacci(30)) ; ## USAGE EXAMPLE |
|||
Func Fibonacci($number) |
|||
If $number < 0 Then Return "Invalid argument" ; No negative numbers |
|||
If $number < 2 Then ; If $number equals 0 or 1 |
|||
Return $number ; then return that $number |
|||
Else ; Else $number equals 2 or more |
|||
Return Fibonacci($number - 1) + Fibonacci($number - 2) ; FIBONACCI! |
|||
EndIf |
|||
EndFunc |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
55 |
|||
6765 |
|||
832040 |
|||
</pre> |
|||
=={{header|Axiom}}== |
=={{header|Axiom}}== |
||
Using the Aldor compiler in Axiom/Fricas: |
Using the Aldor compiler in Axiom/Fricas: |
||
< |
<syntaxhighlight lang="axiom">#include "axiom" |
||
Z ==> Integer; |
Z ==> Integer; |
||
fib(x:Z):Z == { |
fib(x:Z):Z == { |
||
Line 70: | Line 371: | ||
f(n:Z,v1:Z,v2:Z):Z == if n<2 then v2 else f(n-1,v2,v1+v2); |
f(n:Z,v1:Z,v2:Z):Z == if n<2 then v2 else f(n-1,v2,v1+v2); |
||
f(x,1,1); |
f(x,1,1); |
||
}</ |
}</syntaxhighlight>The old Axiom compiler has scope issues with calling a local function recursively. One solution is to use the Reference (pointer) domain and initialise the local function with a dummy value: |
||
< |
<syntaxhighlight lang="axiom">)abbrev package TESTP TestPackage |
||
Z ==> Integer |
Z ==> Integer |
||
TestPackage : with |
TestPackage : with |
||
Line 80: | Line 381: | ||
f : Reference((Z,Z,Z) -> Z) := ref((n, v1, v2) +-> 0) |
f : Reference((Z,Z,Z) -> Z) := ref((n, v1, v2) +-> 0) |
||
f() := (n, v1, v2) +-> if n<2 then v2 else f()(n-1,v2,v1+v2) |
f() := (n, v1, v2) +-> if n<2 then v2 else f()(n-1,v2,v1+v2) |
||
f()(x,1,1)</ |
f()(x,1,1)</syntaxhighlight> |
||
=={{header| |
=={{header|BASIC}}== |
||
==={{header|BaCon}}=== |
|||
<syntaxhighlight lang="freebasic"> |
|||
DEF FN fib(x) = FIB(x) |
|||
'============================ |
|||
FUNCTION FIB(int n) TYPE int |
|||
'============================ |
|||
IF n < 2 THEN |
|||
PRINT n |
|||
ELSE |
|||
n1 = 0 |
|||
n2 = 1 |
|||
FOR i = 1 TO n |
|||
sum = n1 + n2 |
|||
n1 = n2 |
|||
n2 = sum |
|||
NEXT |
|||
PRINT n1 |
|||
END IF |
|||
END FUNCTION |
|||
'--- less than 2 |
|||
FIB(0) |
|||
FIB(1) |
|||
'--- greater than or equal to 2 |
|||
FIB(2) |
|||
FIB(3) |
|||
FIB(4) |
|||
FIB(5) |
|||
FIB(6) |
|||
FIB(7) |
|||
FIB(8) |
|||
FIB(9) |
|||
'--- using an alias |
|||
'fib(9) |
|||
</syntaxhighlight> |
|||
==={{header|BASIC256}}=== |
|||
{{trans|AutoIt}} |
|||
<syntaxhighlight lang="basic256">print Fibonacci(20) |
|||
print Fibonacci(30) |
|||
print Fibonacci(-10) |
|||
print Fibonacci(10) |
|||
end |
|||
function Fibonacci(num) |
|||
if num < 0 then |
|||
print "Invalid argument: "; |
|||
return num |
|||
end if |
|||
if num < 2 then |
|||
return num |
|||
else |
|||
return Fibonacci(num - 1) + Fibonacci(num - 2) |
|||
end If |
|||
end function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>6765 |
|||
832040 |
|||
Invalid argument: -10 |
|||
55</pre> |
|||
==={{header|Chipmunk Basic}}=== |
|||
{{works with|Chipmunk Basic|3.6.4}} |
|||
<syntaxhighlight lang="qbasic">100 cls |
|||
110 sub fib(num) |
|||
120 if num < 0 then print "Invalid argument: "; : fib = num |
|||
130 if num < 2 then fib = num else fib = fib(num-1)+fib(num-2) |
|||
140 end sub |
|||
190 print fib(20) |
|||
200 print fib(30) |
|||
210 print fib(-10) |
|||
220 print fib(10) |
|||
230 end</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as BASIC256 entry.</pre> |
|||
==={{header|BBC BASIC}}=== |
|||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
This works by finding a pointer to the 'anonymous' function and calling it indirectly: |
This works by finding a pointer to the 'anonymous' function and calling it indirectly: |
||
< |
<syntaxhighlight lang="bbcbasic"> PRINT FNfib(10) |
||
END |
END |
||
DEF FNfib(n%) IF n%<0 THEN ERROR 100, "Must not be negative" |
DEF FNfib(n%) IF n%<0 THEN ERROR 100, "Must not be negative" |
||
LOCAL P% : P% = !384 + LEN$!384 + 4 : REM Function pointer |
LOCAL P% : P% = !384 + LEN$!384 + 4 : REM Function pointer |
||
(n%) IF n%<2 THEN = n% ELSE = FN(^P%)(n%-1) + FN(^P%)(n%-2)</ |
(n%) IF n%<2 THEN = n% ELSE = FN(^P%)(n%-1) + FN(^P%)(n%-2)</syntaxhighlight> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
55 |
55 |
||
</pre> |
</pre> |
||
==={{header|IS-BASIC}}=== |
|||
<syntaxhighlight lang="is-basic">100 PROGRAM "Fibonacc.bas" |
|||
110 FOR I=0 TO 10 |
|||
120 PRINT FIB(I); |
|||
130 NEXT |
|||
140 DEF FIB(K) |
|||
150 SELECT CASE K |
|||
160 CASE IS<0 |
|||
170 PRINT "Negative parameter to Fibonacci.":STOP |
|||
180 CASE 0,1 |
|||
190 LET FIB=K |
|||
200 CASE ELSE |
|||
210 LET FIB=FIB(K-1)+FIB(K-2) |
|||
220 END SELECT |
|||
230 END DEF </syntaxhighlight> |
|||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
===lambda 'light'=== |
===lambda 'light'=== |
||
The first solution uses macro substitution. In an expression headed by an apostrophe operator with an empty lhs all subexpressions headed by a dollar operator with empty lhs are replaced by the values that the rhs are bound to, without otherwise evaluating the expression. Example: if <code>(x=7) & (y=4)</code> then <code>'($x+3+$y)</code> becomes <code>=7+3+4</code>. Notice that the solution below utilises no other names than <code>arg</code>, the keyword that always denotes a function's argument. The test for negative or non-numeric arguments is outside the recursive part. The function fails if given negative input. |
The first solution uses macro substitution. In an expression headed by an apostrophe operator with an empty lhs all subexpressions headed by a dollar operator with empty lhs are replaced by the values that the rhs are bound to, without otherwise evaluating the expression. Example: if <code>(x=7) & (y=4)</code> then <code>'($x+3+$y)</code> becomes <code>=7+3+4</code>. Notice that the solution below utilises no other names than <code>arg</code>, the keyword that always denotes a function's argument. The test for negative or non-numeric arguments is outside the recursive part. The function fails if given negative input. |
||
< |
<syntaxhighlight lang="bracmat">( ( |
||
= |
= |
||
. !arg:#:~<0 |
. !arg:#:~<0 |
||
Line 117: | Line 518: | ||
$ 30 |
$ 30 |
||
) |
) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Answer: |
Answer: |
||
<pre>832040</pre> |
<pre>832040</pre> |
||
===pure lambda calculus=== |
===pure lambda calculus=== |
||
(See http://en.wikipedia.org/wiki/Lambda_calculus). The following solution works almost the same way as the previous solution, but uses lambda calculus |
(See http://en.wikipedia.org/wiki/Lambda_calculus). The following solution works almost the same way as the previous solution, but uses lambda calculus |
||
< |
<syntaxhighlight lang="bracmat">( /( |
||
' ( x |
' ( x |
||
. $x:#:~<0 |
. $x:#:~<0 |
||
Line 142: | Line 543: | ||
) |
) |
||
$ 30 |
$ 30 |
||
)</ |
)</syntaxhighlight> |
||
Answer: |
Answer: |
||
<pre>832040</pre> |
<pre>832040</pre> |
||
=={{header|BQN}}== |
|||
<code>𝕊</code> is a useful symbol in BQN which references the function it is currently in. This can be used to perform anonymous recursion without the need of naming the function block. |
|||
The following code calls an anonymous recursive Fibonacci function on each number of the range 0-9. |
|||
<syntaxhighlight lang="bqn">{ |
|||
(𝕩<2)◶⟨+´𝕊¨,𝕏⟩𝕩-1‿2 |
|||
}¨↕10</syntaxhighlight> |
|||
<syntaxhighlight lang="bqn">⟨ 0 1 1 2 3 5 8 13 21 34 ⟩</syntaxhighlight> |
|||
[https://mlochbaum.github.io/BQN/try.html#code=ewogICjwnZWpPDIp4pe24p+oK8K08J2VisKoLPCdlY/in6nwnZWpLTHigL8yCn3CqOKGlTEw Try It!] |
|||
Recursion can also be performed using an internal name defined by a header such as <code>Fact:</code> or <code>Fact 𝕩:</code>. This header is visible inside the block but not outside of it, so from the outside the function is anonymous. The named form allows the outer function to be called within nested blocks, while <code>𝕊</code> can only refer to the immediately containing one. |
|||
<syntaxhighlight lang="bqn">{Fact 𝕩: |
|||
(𝕩<2)◶⟨+´Fact¨,𝕏⟩𝕩-1‿2 |
|||
}¨↕10</syntaxhighlight> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
Using scoped function fib_i inside fib, with GCC: |
Using scoped function fib_i inside fib, with GCC (required version 3.2 or higher): |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
long fib(long x) |
long fib(long x) |
||
Line 176: | Line 593: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Bad argument: fib(-1) |
<pre>Bad argument: fib(-1) |
||
Line 186: | Line 603: | ||
calling fib_i from outside fib: |
calling fib_i from outside fib: |
||
This is not the fib you are looking for</pre> |
This is not the fib you are looking for</pre> |
||
Recursive functions can be defined within [https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html statement expressions]: |
|||
<syntaxhighlight lang="c"> |
|||
#include <stdio.h> |
|||
int main(){ |
|||
int n = 3; |
|||
printf("%d",({ |
|||
int fib(int n){ |
|||
if (n <= 1) |
|||
return n; |
|||
return fib(n-1) + fib(n-2); |
|||
} |
|||
fib(n); |
|||
})); |
|||
return 0; |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|C sharp|C#}}== |
|||
The inner recursive function (delegate/lambda) has to be named. |
|||
<syntaxhighlight lang="csharp"> |
|||
static int Fib(int n) |
|||
{ |
|||
if (n < 0) throw new ArgumentException("Must be non negativ", "n"); |
|||
Func<int, int> fib = null; // Must be known, before we can assign recursively to it. |
|||
fib = p => p > 1 ? fib(p - 2) + fib(p - 1) : p; |
|||
return fib(n); |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|C++}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="cpp">double fib(double n) |
||
{ |
{ |
||
if(n < 0) |
if(n < 0) |
||
Line 214: | Line 662: | ||
return actual_fib::calc(n); |
return actual_fib::calc(n); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{works with|C++11}} |
{{works with|C++11}} |
||
< |
<syntaxhighlight lang="cpp">#include <functional> |
||
using namespace std; |
using namespace std; |
||
Line 231: | Line 679: | ||
return actual_fib(n); |
return actual_fib(n); |
||
}</ |
}</syntaxhighlight> |
||
Using a local function object that calls itself using <code>this</code>: |
Using a local function object that calls itself using <code>this</code>: |
||
< |
<syntaxhighlight lang="cpp">double fib(double n) |
||
{ |
{ |
||
if(n < 0) |
if(n < 0) |
||
Line 243: | Line 691: | ||
else |
else |
||
{ |
{ |
||
struct |
struct |
||
{ |
{ |
||
double operator()(double n) |
double operator()(double n) |
||
Line 256: | Line 704: | ||
} |
} |
||
} |
} |
||
}; |
} actual_fib; |
||
return actual_fib |
return actual_fib(n); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Clio}}== |
|||
Simple anonymous recursion to print from 9 to 0. |
|||
<syntaxhighlight lang="clio">10 -> (@eager) fn n: |
|||
if n: |
|||
n - 1 -> print -> recall</syntaxhighlight> |
|||
=={{header|C sharp|C#}}== |
|||
The inner recursive function (delegate/lambda) has to be named. |
|||
<lang csharp> |
|||
static int Fib(int n) |
|||
{ |
|||
if (n < 0) throw new ArgumentException("Must be non negativ", "n"); |
|||
Func<int, int> fib = null; // Must be known, before we can assign recursively to it. |
|||
fib = p => p > 1 ? fib(p - 2) + fib(p - 1) : p; |
|||
return fib(n); |
|||
} |
|||
</lang> |
|||
=={{header|Clojure}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="clojure"> |
||
(defn fib [n] |
(defn fib [n] |
||
(when (neg? n) |
(when (neg? n) |
||
Line 284: | Line 726: | ||
v2 |
v2 |
||
(recur (dec n) v2 (+ v1 v2))))) |
(recur (dec n) v2 (+ v1 v2))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Using an anonymous function |
Using an anonymous function |
||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
< |
<syntaxhighlight lang="coffeescript"># This is a rather obscure technique to have an anonymous |
||
# function call itself. |
# function call itself. |
||
fibonacci = (n) -> |
fibonacci = (n) -> |
||
Line 305: | Line 747: | ||
recurse(n-2) + recurse(n-1) |
recurse(n-2) + recurse(n-1) |
||
recurse(n) |
recurse(n) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
Line 312: | Line 754: | ||
This version uses the anaphoric <code>lambda</code> from [http://dunsmor.com/lisp/onlisp/onlisp_18.html Paul Graham's On Lisp]. |
This version uses the anaphoric <code>lambda</code> from [http://dunsmor.com/lisp/onlisp/onlisp_18.html Paul Graham's On Lisp]. |
||
< |
<syntaxhighlight lang="lisp">(defmacro alambda (parms &body body) |
||
`(labels ((self ,parms ,@body)) |
`(labels ((self ,parms ,@body)) |
||
#'self))</ |
#'self))</syntaxhighlight> |
||
The Fibonacci function can then be defined as |
The Fibonacci function can then be defined as |
||
< |
<syntaxhighlight lang="lisp">(defun fib (n) |
||
(assert (>= n 0) nil "'~a' is a negative number" n) |
(assert (>= n 0) nil "'~a' is a negative number" n) |
||
(funcall |
(funcall |
||
Line 325: | Line 767: | ||
n |
n |
||
(+ (self (- n 1)) (self (- n 2))))) |
(+ (self (- n 1)) (self (- n 2))))) |
||
n))</ |
n))</syntaxhighlight> |
||
===Using labels=== |
===Using labels=== |
||
This puts a function in a local label. The function is not anonymous, but |
This puts a function in a local label. The function is not anonymous, but not only is it local, so that its name does not pollute the global namespace, but the name can be chosen to be identical to that of the surrounding function, so it is not a newly invented name |
||
<lang lisp>(defun fib (number) |
|||
<syntaxhighlight lang="lisp">(defun fib (number) |
|||
"Fibonacci sequence function." |
"Fibonacci sequence function." |
||
(if (< number 0) |
(if (< number 0) |
||
(error "Error. The number entered: ~A is negative" number) |
(error "Error. The number entered: ~A is negative" number) |
||
(labels (( |
(labels ((fib (n a b) |
||
(if (= n 0) |
(if (= n 0) |
||
a |
a |
||
( |
(fib (- n 1) b (+ a b))))) |
||
( |
(fib number 0 1))))</syntaxhighlight> |
||
Although name space polution isn't an issue, in recognition of the obvious convenience of anonymous recursive helpers, here is another solution: add the language feature for anonymously recursive blocks: the operator RECURSIVE, with a built-in local operator RECURSE to make recursive calls. |
Although name space polution isn't an issue, in recognition of the obvious convenience of anonymous recursive helpers, here is another solution: add the language feature for anonymously recursive blocks: the operator RECURSIVE, with a built-in local operator RECURSE to make recursive calls. |
||
Here is <code>fib</code> rewritten to use RECURSIVE: |
Here is <code>fib</code> rewritten to use RECURSIVE: |
||
< |
<syntaxhighlight lang="lisp">(defun fib (number) |
||
"Fibonacci sequence function." |
"Fibonacci sequence function." |
||
(if (< number 0) |
(if (< number 0) |
||
Line 349: | Line 792: | ||
(if (= n 0) |
(if (= n 0) |
||
a |
a |
||
(recurse (- n 1) b (+ a b))))))</ |
(recurse (- n 1) b (+ a b))))))</syntaxhighlight> |
||
Implementation of RECURSIVE: |
Implementation of RECURSIVE: |
||
< |
<syntaxhighlight lang="lisp">(defmacro recursive ((&rest parm-init-pairs) &body body) |
||
(let ((hidden-name (gensym "RECURSIVE-"))) |
(let ((hidden-name (gensym "RECURSIVE-"))) |
||
`(macrolet ((recurse (&rest args) `(,',hidden-name ,@args))) |
`(macrolet ((recurse (&rest args) `(,',hidden-name ,@args))) |
||
(labels ((,hidden-name (,@(mapcar #'first parm-init-pairs)) ,@body)) |
(labels ((,hidden-name (,@(mapcar #'first parm-init-pairs)) ,@body)) |
||
(,hidden-name ,@(mapcar #'second parm-init-pairs))))))</ |
(,hidden-name ,@(mapcar #'second parm-init-pairs))))))</syntaxhighlight> |
||
RECURSIVE works by generating a local function with LABELS, but with a machine-generated unique name. Furthermore, it provides syntactic sugar so that the initial call to the recursive function takes place implicitly, and the initial values are specified using LET-like syntax. Of course, if RECURSIVE blocks are nested, each RECURSE refers to its own function. There is no way for an inner RECURSIVE to specify recursion to an other RECURSIVE. That is what names are for! |
RECURSIVE works by generating a local function with LABELS, but with a machine-generated unique name. Furthermore, it provides syntactic sugar so that the initial call to the recursive function takes place implicitly, and the initial values are specified using LET-like syntax. Of course, if RECURSIVE blocks are nested, each RECURSE refers to its own function. There is no way for an inner RECURSIVE to specify recursion to an other RECURSIVE. That is what names are for! |
||
Line 366: | Line 809: | ||
===Using the Y combinator=== |
===Using the Y combinator=== |
||
< |
<syntaxhighlight lang="lisp">(setf (symbol-function '!) (symbol-function 'funcall) |
||
(symbol-function '!!) (symbol-function 'apply)) |
(symbol-function '!!) (symbol-function 'apply)) |
||
Line 429: | Line 872: | ||
(1 1) |
(1 1) |
||
(otherwise (+ (fib (- n 1)) |
(otherwise (+ (fib (- n 1)) |
||
(fib (- n 2))))))</ |
(fib (- n 2))))))</syntaxhighlight> |
||
===Using optional function parameters=== |
|||
We can use optional parameters to get tail recursive functions without a helper. |
|||
<syntaxhighlight lang="lisp">(defun fib (n &optional (f1 0) (f2 1)) |
|||
(if (< n 0) |
|||
(format t "Parameter must be >= 0") |
|||
(if (zerop n) |
|||
f1 |
|||
(fib (1- n) f2 (+ f1 f2)))))</syntaxhighlight> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">int fib(in uint arg) pure nothrow @safe @nogc { |
||
assert(arg >= 0); |
assert(arg >= 0); |
||
return function |
return function uint(in uint n) pure nothrow @safe @nogc { |
||
static immutable self = &__traits(parent, {}); |
|||
return (n < 2) ? n : self(n - 1) + self(n - 2); |
return (n < 2) ? n : self(n - 1) + self(n - 2); |
||
}(arg); |
}(arg); |
||
Line 445: | Line 897: | ||
39.fib.writeln; |
39.fib.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>63245986</pre> |
<pre>63245986</pre> |
||
Line 451: | Line 903: | ||
===With Anonymous Class=== |
===With Anonymous Class=== |
||
In this version 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. |
In this version 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. |
||
< |
<syntaxhighlight lang="d">import std.stdio; |
||
int fib(in int n) pure nothrow { |
int fib(in int n) pure nothrow { |
||
Line 468: | Line 920: | ||
void main() { |
void main() { |
||
writeln(fib(39)); |
writeln(fib(39)); |
||
}</ |
}</syntaxhighlight> |
||
The output is the same. |
The output is the same. |
||
=={{header|Dylan}}== |
|||
This puts a function in a local method binding. The function is not anonymous, but the name fib1 is local and never pollutes the outside namespace. |
|||
<syntaxhighlight lang="dylan"> |
|||
define function fib (n) |
|||
when (n < 0) |
|||
error("Can't take fibonacci of negative integer: %d\n", n) |
|||
end; |
|||
local method fib1 (n, a, b) |
|||
if (n = 0) |
|||
a |
|||
else |
|||
fib1(n - 1, b, a + b) |
|||
end |
|||
end; |
|||
fib1(n, 0, 1) |
|||
end |
|||
</syntaxhighlight> |
|||
=={{header|Déjà Vu}}== |
=={{header|Déjà Vu}}== |
||
===With Y combinator=== |
===With Y combinator=== |
||
< |
<syntaxhighlight lang="dejavu">Y f: |
||
labda y: |
labda y: |
||
labda: |
labda: |
||
Line 490: | Line 961: | ||
for j range 0 10: |
for j range 0 10: |
||
!print fibo j</ |
!print fibo j</syntaxhighlight> |
||
===With <code>recurse</code>=== |
===With <code>recurse</code>=== |
||
< |
<syntaxhighlight lang="dejavu">fibo-2 n: |
||
n 0 1 |
n 0 1 |
||
labda times back-2 back-1: |
labda times back-2 back-1: |
||
Line 506: | Line 977: | ||
for j range 0 10: |
for j range 0 10: |
||
!print fibo-2 j</ |
!print fibo-2 j</syntaxhighlight> |
||
Note that this method starts from 0, while the previous starts from 1. |
Note that this method starts from 0, while the previous starts from 1. |
||
=={{header| |
=={{header|Delphi}}== |
||
<syntaxhighlight lang="delphi"> |
|||
This puts a function in a local method binding. The function is not anonymous, but the name fib1 is local and never pollutes the outside namespace. |
|||
program AnonymousRecursion; |
|||
{$APPTYPE CONSOLE} |
|||
uses |
|||
<lang dylan> |
|||
SysUtils; |
|||
define function fib (n) |
|||
when (n < 0) |
|||
function Fib(X: Integer): integer; |
|||
error("Can't take fibonacci of negative integer: %d\n", n) |
|||
end; |
|||
function DoFib(N: Integer): Integer; |
|||
local method fib1 (n, a, b) |
|||
begin |
|||
if (n = 0) |
|||
if N < 2 then Result:=N |
|||
else Result:=DoFib(N-1) + DoFib(N-2); |
|||
else |
|||
end; |
|||
fib1(n - 1, b, a + b) |
|||
end |
|||
begin |
|||
end; |
|||
if X < 0 then raise Exception.Create('Argument < 0') |
|||
fib1(n, 0, 1) |
|||
else Result:=DoFib(X); |
|||
end |
|||
end; |
|||
</lang> |
|||
var I: integer; |
|||
begin |
|||
for I:=-1 to 15 do |
|||
begin |
|||
try |
|||
WriteLn(I:3,' - ',Fib(I):3); |
|||
except WriteLn(I,' - Error'); end; |
|||
end; |
|||
WriteLn('Hit Any Key'); |
|||
ReadLn; |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
-1 - -1 - Error |
|||
0 - 0 |
|||
1 - 1 |
|||
2 - 1 |
|||
3 - 2 |
|||
4 - 3 |
|||
5 - 5 |
|||
6 - 8 |
|||
7 - 13 |
|||
8 - 21 |
|||
9 - 34 |
|||
10 - 55 |
|||
11 - 89 |
|||
12 - 144 |
|||
13 - 233 |
|||
14 - 377 |
|||
15 - 610 |
|||
Hit Any Key |
|||
</pre> |
|||
=={{header|EchoLisp}}== |
|||
A '''named let''' provides a local lambda via a label. |
|||
<syntaxhighlight lang="scheme"> |
|||
(define (fib n) |
|||
(let _fib ((a 1) (b 1) (n n)) |
|||
(if |
|||
(<= n 1) a |
|||
(_fib b (+ a b) (1- n))))) |
|||
</syntaxhighlight> |
|||
=={{header|Ela}}== |
=={{header|Ela}}== |
||
Using fix-point combinator: |
Using fix-point combinator: |
||
< |
<syntaxhighlight lang="ela">fib n | n < 0 = fail "Negative n" |
||
| else = fix (\f n -> if n < 2 then n else f (n - 1) + f (n - 2)) n</ |
| else = fix (\f n -> if n < 2 then n else f (n - 1) + f (n - 2)) n</syntaxhighlight> |
||
Function 'fix' is defined in standard Prelude as follows: |
Function 'fix' is defined in standard Prelude as follows: |
||
< |
<syntaxhighlight lang="ela">fix f = f (& fix f)</syntaxhighlight> |
||
=={{header|Elena}}== |
=={{header|Elena}}== |
||
ELENA 6.x: |
|||
<lang elena>#define system. |
|||
<syntaxhighlight lang="elena">import extensions; |
|||
fib(n) |
|||
#symbol fibo = (:n) |
|||
{ |
|||
[ |
|||
n < 0 |
if (n < 0) |
||
{ InvalidArgumentException.raise() }; |
|||
^ { eval:n [ ^ (n > 1) ? [ ($self:(n - 2)) + ($self:(n - 1)) ] ! [ n ]. ] }:n. |
|||
]. |
|||
#symbol program = |
|||
[ |
|||
control forrange &int:-1 &int:10 &do: (&int:i) |
|||
[ |
|||
console << "fib(" << i << ")=". |
|||
^ (n) { |
|||
console writeLine:(fibo:i) | onInvalidArgumentError: e |
|||
if (n > 1) |
|||
{ |
|||
console writeLine:"invalid". |
|||
^ this self(n - 2) + (this self(n - 1)) |
|||
} |
|||
else |
|||
{ |
|||
^ n |
|||
} |
|||
}(n) |
|||
} |
|||
public program() |
|||
{ |
|||
for (int i := -1; i <= 10; i += 1) |
|||
{ |
|||
console.print("fib(",i,")="); |
|||
try |
|||
{ |
|||
console.printLine(fib(i)) |
|||
} |
|||
catch(Exception e) |
|||
{ |
|||
console.printLine("invalid") |
|||
} |
|||
}; |
|||
console.readChar() |
|||
}</syntaxhighlight> |
|||
].</lang> |
|||
{{out}} |
|||
<pre> |
|||
fib(-1)=invalid |
|||
fib(0)=0 |
|||
fib(1)=1 |
|||
fib(2)=1 |
|||
fib(3)=2 |
|||
fib(4)=3 |
|||
fib(5)=5 |
|||
fib(6)=8 |
|||
fib(7)=13 |
|||
fib(8)=21 |
|||
fib(9)=34 |
|||
fib(10)=55 |
|||
</pre> |
|||
=={{header|Elixir}}== |
|||
With Y-Combinator: |
|||
<syntaxhighlight lang="elixir"> |
|||
fib = fn f -> ( |
|||
fn x -> if x == 0, do: 0, else: (if x == 1, do: 1, else: f.(x - 1) + f.(x - 2)) end |
|||
) |
|||
end |
|||
y = fn x -> ( |
|||
fn f -> f.(f) |
|||
end).( |
|||
fn g -> x.(fn z ->(g.(g)).(z) end) |
|||
end) |
|||
end |
|||
IO.inspect y.(&(fib.(&1))).(40) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
102334155 |
|||
=={{header|EMal}}== |
|||
<syntaxhighlight lang="emal"> |
|||
fun fibonacci = int by int n |
|||
if n < 0 do |
|||
logLine("Invalid argument: " + n) # logs on standard error |
|||
return -1 ^| it should be better to raise an error, |
|||
| but the task is about recursive functions |
|||
|^ |
|||
end |
|||
fun actualFibonacci = int by int n |
|||
return when(n < 2, n, actualFibonacci(n - 1) + actualFibonacci(n - 2)) |
|||
end |
|||
return actualFibonacci(n) |
|||
end |
|||
writeLine("F(0) = " + fibonacci(0)) |
|||
writeLine("F(20) = " + fibonacci(20)) |
|||
writeLine("F(-10) = " + fibonacci(-10)) |
|||
writeLine("F(30) = " + fibonacci(30)) |
|||
writeLine("F(10) = " + fibonacci(10)) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
F(0) = 0 |
|||
F(20) = 6765 |
|||
Invalid argument: -10 |
|||
F(-10) = -1 |
|||
F(30) = 832040 |
|||
F(10) = 55 |
|||
</pre> |
|||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
Two solutions. First fib that use the module to hide its helper. The helper also is called fib so there is no naming problem. Then fib_internal which has the helper function inside itself. |
Two solutions. First fib that use the module to hide its helper. The helper also is called fib so there is no naming problem. Then fib_internal which has the helper function inside itself. |
||
<syntaxhighlight lang="erlang"> |
|||
<lang Erlang> |
|||
-module( anonymous_recursion ). |
-module( anonymous_recursion ). |
||
-export( [fib/1, fib_internal/1] ). |
-export( [fib/1, fib_internal/1] ). |
||
Line 582: | Line 1,182: | ||
fib( N, Next, Acc ) -> fib( N - 1, Acc+Next, Next ). |
fib( N, Next, Acc ) -> fib( N - 1, Acc+Next, Next ). |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|F Sharp|F#}}== |
=={{header|F Sharp|F#}}== |
||
Line 588: | Line 1,188: | ||
The function 'fib2' is only visible inside the 'fib' function. |
The function 'fib2' is only visible inside the 'fib' function. |
||
< |
<syntaxhighlight lang="fsharp">let fib = function |
||
| n when n < 0 -> None |
| n when n < 0 -> None |
||
| n -> let rec fib2 = function |
| n -> let rec fib2 = function |
||
| 0 | 1 -> 1 |
| 0 | 1 -> 1 |
||
| n -> fib2 (n-1) + fib2 (n-2) |
| n -> fib2 (n-1) + fib2 (n-2) |
||
in Some (fib2 n)</ |
in Some (fib2 n)</syntaxhighlight> |
||
'''Using a fixed point combinator:''' |
'''Using a fixed point combinator:''' |
||
< |
<syntaxhighlight lang="fsharp">let rec fix f x = f (fix f) x |
||
let fib = function |
let fib = function |
||
| n when n < 0 -> None |
| n when n < 0 -> None |
||
| n -> Some (fix (fun f -> (function | 0 | 1 -> 1 | n -> f (n-1) + f (n-2))) n)</ |
| n -> Some (fix (fun f -> (function | 0 | 1 -> 1 | n -> f (n-1) + f (n-2))) n)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Both functions have the same output. |
Both functions have the same output. |
||
< |
<syntaxhighlight lang="fsharp">[-1..5] |> List.map fib |> printfn "%A" |
||
[null; Some 1; Some 1; Some 2; Some 3; Some 5; Some 8]</ |
[null; Some 1; Some 1; Some 2; Some 3; Some 5; Some 8]</syntaxhighlight> |
||
=={{header|FBSL}}== |
|||
<lang qbasic>#APPTYPE CONSOLE |
|||
FUNCTION Fibonacci(n) |
|||
IF n < 0 THEN |
|||
RETURN "Nuts!" |
|||
ELSE |
|||
RETURN Fib(n) |
|||
END IF |
|||
FUNCTION Fib(m) |
|||
IF m < 2 THEN |
|||
Fib = m |
|||
ELSE |
|||
Fib = Fib(m - 1) + Fib(m - 2) |
|||
END IF |
|||
END FUNCTION |
|||
END FUNCTION |
|||
PRINT Fibonacci(-1.5) |
|||
PRINT Fibonacci(1.5) |
|||
PRINT Fibonacci(13.666) |
|||
PAUSE</lang> |
|||
'''Output:''' |
|||
Nuts! |
|||
1.5 |
|||
484.082 |
|||
Press any key to continue... |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
Line 639: | Line 1,209: | ||
To achieve anonymous recursion, this solution has a recursive quotation. |
To achieve anonymous recursion, this solution has a recursive quotation. |
||
< |
<syntaxhighlight lang="factor">USING: kernel math ; |
||
IN: rosettacode.fibonacci.ar |
IN: rosettacode.fibonacci.ar |
||
Line 650: | Line 1,220: | ||
[ [ 2 - ] dip dup call ] 2bi + |
[ [ 2 - ] dip dup call ] 2bi + |
||
] if |
] if |
||
] dup call( n q -- m ) ;</ |
] dup call( n q -- m ) ;</syntaxhighlight> |
||
The name ''q'' in the stack effect has no significance; <code>call( x x -- x )</code> would still work. |
The name ''q'' in the stack effect has no significance; <code>call( x x -- x )</code> would still work. |
||
Line 660: | Line 1,230: | ||
=={{header|Falcon}}== |
=={{header|Falcon}}== |
||
Falcon allows a function to refer to itself by use of the fself keyword which is always set to the currently executing function. |
Falcon allows a function to refer to itself by use of the fself keyword which is always set to the currently executing function. |
||
< |
<syntaxhighlight lang="falcon">function fib(x) |
||
if x < 0 |
if x < 0 |
||
raise ParamError(description|"Negative argument invalid", extra|"Fibbonacci sequence is undefined for negative numbers") |
raise ParamError(description|"Negative argument invalid", extra|"Fibbonacci sequence is undefined for negative numbers") |
||
Line 684: | Line 1,254: | ||
catch in e |
catch in e |
||
> e |
> e |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 696: | Line 1,266: | ||
"/home/uDTVwo/prog.fam" prog.__main__:22(PC:132) |
"/home/uDTVwo/prog.fam" prog.__main__:22(PC:132) |
||
</pre> |
</pre> |
||
=={{header|FBSL}}== |
|||
<syntaxhighlight lang="qbasic">#APPTYPE CONSOLE |
|||
FUNCTION Fibonacci(n) |
|||
IF n < 0 THEN |
|||
RETURN "Nuts!" |
|||
ELSE |
|||
RETURN Fib(n) |
|||
END IF |
|||
FUNCTION Fib(m) |
|||
IF m < 2 THEN |
|||
Fib = m |
|||
ELSE |
|||
Fib = Fib(m - 1) + Fib(m - 2) |
|||
END IF |
|||
END FUNCTION |
|||
END FUNCTION |
|||
PRINT Fibonacci(-1.5) |
|||
PRINT Fibonacci(1.5) |
|||
PRINT Fibonacci(13.666) |
|||
PAUSE</syntaxhighlight> |
|||
'''Output:''' |
|||
Nuts! |
|||
1.5 |
|||
484.082 |
|||
Press any key to continue... |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
Recursion is always anonymous in Forth, allowing it to be used in anonymous functions. However, definitions can't be defined during a definition (there are no 'local functions'), and the data stack can't be portably used to get data into a definition being defined. |
Recursion is always anonymous in Forth, allowing it to be used in anonymous functions. However, definitions can't be defined during a definition (there are no 'local functions'), and the data stack can't be portably used to get data into a definition being defined. |
||
{{works with|SwiftForth}} - and any Forth in which colon-sys consumes zero cells on the data stack. |
{{works with|SwiftForth}} - and any Forth in which colon-sys consumes zero cells on the data stack. |
||
< |
<syntaxhighlight lang="forth">:noname ( n -- n' ) |
||
dup 2 < ?exit |
dup 2 < ?exit |
||
1- dup recurse swap 1- recurse + ; ( xt ) |
1- dup recurse swap 1- recurse + ; ( xt ) |
||
Line 706: | Line 1,306: | ||
: fib ( +n -- n' ) |
: fib ( +n -- n' ) |
||
dup 0< abort" Negative numbers don't exist." |
dup 0< abort" Negative numbers don't exist." |
||
[ ( xt from the :NONAME above ) compile, ] ;</ |
[ ( xt from the :NONAME above ) compile, ] ;</syntaxhighlight> |
||
Portability is achieved with a once-off variable (or any temporary-use space with a constant address - i.e., not PAD): |
Portability is achieved with a once-off variable (or any temporary-use space with a constant address - i.e., not PAD): |
||
< |
<syntaxhighlight lang="forth">( xt from :noname in the previous example ) |
||
variable pocket pocket ! |
variable pocket pocket ! |
||
: fib ( +n -- n' ) |
: fib ( +n -- n' ) |
||
dup 0< abort" Negative numbers don't exist." |
dup 0< abort" Negative numbers don't exist." |
||
[ pocket @ compile, ] ;</ |
[ pocket @ compile, ] ;</syntaxhighlight> |
||
Currently, most Forths have started to support embedded definitions (shown here for iForth): |
Currently, most Forths have started to support embedded definitions (shown here for iForth): |
||
< |
<syntaxhighlight lang="forth">: fib ( +n -- ) |
||
dup 0< abort" Negative numbers don't exist" |
dup 0< abort" Negative numbers don't exist" |
||
[: dup 2 < ?exit 1- dup MYSELF swap 1- MYSELF + ;] execute . ;</ |
[: dup 2 < ?exit 1- dup MYSELF swap 1- MYSELF + ;] execute . ;</syntaxhighlight> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
Since a hidden named function instead of an anonymous one seems to be ok with implementors, here is the Fortran version: |
Since a hidden named function instead of an anonymous one seems to be ok with implementors, here is the Fortran version: |
||
< |
<syntaxhighlight lang="fortran">integer function fib(n) |
||
integer, intent(in) :: n |
integer, intent(in) :: n |
||
if (n < 0 ) then |
if (n < 0 ) then |
||
Line 737: | Line 1,337: | ||
end if |
end if |
||
end function purefib |
end function purefib |
||
end function fib</ |
end function fib</syntaxhighlight> |
||
=={{header|FreeBASIC}}== |
|||
FreeBASIC does not support nested functions, lambda expressions, functions inside nested types or even (in the default dialect) gosub. |
|||
However, for compatibility with old QB code, gosub can be used if one specifies the 'fblite', 'qb' or 'deprecated dialects: |
|||
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
|||
#Lang "fblite" |
|||
Option Gosub '' enables Gosub to be used |
|||
' Using gosub to simulate a nested function |
|||
Function fib(n As UInteger) As UInteger |
|||
Gosub nestedFib |
|||
Exit Function |
|||
nestedFib: |
|||
fib = IIf(n < 2, n, fib(n - 1) + fib(n - 2)) |
|||
Return |
|||
End Function |
|||
' This function simulates (rather messily) gosub by using 2 gotos and would therefore work |
|||
' even in the default dialect |
|||
Function fib2(n As UInteger) As UInteger |
|||
Goto nestedFib |
|||
exitFib: |
|||
Exit Function |
|||
nestedFib: |
|||
fib2 = IIf(n < 2, n, fib2(n - 1) + fib2(n - 2)) |
|||
Goto exitFib |
|||
End Function |
|||
For i As Integer = 1 To 12 |
|||
Print fib(i); " "; |
|||
Next |
|||
Print |
|||
For j As Integer = 1 To 12 |
|||
Print fib2(j); " "; |
|||
Next |
|||
Print |
|||
Print "Press any key to quit" |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
1 1 2 3 5 8 13 21 34 55 89 144 |
|||
1 1 2 3 5 8 13 21 34 55 89 144 |
|||
</pre> |
|||
=={{header|Fōrmulæ}}== |
|||
{{FormulaeEntry|page=https://formulae.org/?script=examples/Anonymous_recursion}} |
|||
'''Solution.''' |
|||
It consists in having a local function inside the main function, so it is neither visible nor available outside. The local function is defined after the validation, so if the input is invalid, neither the definition nor its invocation is performed. |
|||
[[File:Fōrmulæ - Anonymous recursion 01.png]] |
|||
'''Test cases''' |
|||
[[File:Fōrmulæ - Anonymous recursion 02.png]] |
|||
[[File:Fōrmulæ - Anonymous recursion 03.png]] |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
===Y combinator=== |
|||
Y combinator solution. Go has no special support for anonymous recursion. |
Y combinator solution. Go has no special support for anonymous recursion. |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 779: | Line 1,449: | ||
func yc(f ff) fn { |
func yc(f ff) fn { |
||
return func(x fx) fn { |
return func(x fx) fn { |
||
return |
return x(x) |
||
return x(x)(a1, a2, a3) |
|||
}) |
|||
}(func(x fx) fn { |
}(func(x fx) fn { |
||
return f(func(a1, a2, a3 int) int { |
return f(func(a1, a2, a3 int) int { |
||
Line 787: | Line 1,455: | ||
}) |
}) |
||
}) |
}) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 799: | Line 1,467: | ||
fib 40 = 102334155 |
fib 40 = 102334155 |
||
fib undefined for negative numbers |
fib undefined for negative numbers |
||
</pre> |
|||
===Closure=== |
|||
<syntaxhighlight lang="go"> |
|||
package main |
|||
import ( |
|||
"errors" |
|||
"fmt" |
|||
) |
|||
func fib(n int) (result int, err error) { |
|||
var fib func(int) int // Must be declared first so it can be called in the closure |
|||
fib = func(n int) int { |
|||
if n < 2 { |
|||
return n |
|||
} |
|||
return fib(n-1) + fib(n-2) |
|||
} |
|||
if n < 0 { |
|||
err = errors.New("negative n is forbidden") |
|||
return |
|||
} |
|||
result = fib(n) |
|||
return |
|||
} |
|||
func main() { |
|||
for i := -1; i <= 10; i++ { |
|||
if result, err := fib(i); err != nil { |
|||
fmt.Printf("fib(%d) returned error: %s\n", i, err) |
|||
} else { |
|||
fmt.Printf("fib(%d) = %d\n", i, result) |
|||
} |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
fib(-1) returned error: negative n is forbidden |
|||
fib(0) = 0 |
|||
fib(1) = 1 |
|||
fib(2) = 1 |
|||
fib(3) = 2 |
|||
fib(4) = 3 |
|||
fib(5) = 5 |
|||
fib(6) = 8 |
|||
fib(7) = 13 |
|||
fib(8) = 21 |
|||
fib(9) = 34 |
|||
fib(10) = 55 |
|||
</pre> |
</pre> |
||
=={{header|Groovy}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="groovy">def fib = { |
||
assert it > -1 |
assert it > -1 |
||
{i -> i < 2 ? i : {j -> owner.call(j)}(i-1) + {k -> owner.call(k)}(i-2)}(it) |
{i -> i < 2 ? i : {j -> owner.call(j)}(i-1) + {k -> owner.call(k)}(i-2)}(it) |
||
}</ |
}</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="groovy">def fib0to20 = (0..20).collect(fib) |
||
println fib0to20 |
println fib0to20 |
||
Line 816: | Line 1,537: | ||
println "KABOOM!!" |
println "KABOOM!!" |
||
println e.message |
println e.message |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765] |
<pre>[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765] |
||
Line 831: | Line 1,552: | ||
We're defining a function 'real' which is only available from within the fib function. |
We're defining a function 'real' which is only available from within the fib function. |
||
< |
<syntaxhighlight lang="haskell">fib :: Integer -> Maybe Integer |
||
fib n |
fib n |
||
| n < 0 = Nothing |
| n < 0 = Nothing |
||
Line 837: | Line 1,558: | ||
where real 0 = 1 |
where real 0 = 1 |
||
real 1 = 1 |
real 1 = 1 |
||
real n = real (n-1) + real (n-2)</ |
real n = real (n-1) + real (n-2)</syntaxhighlight> |
||
'''Anonymous function:''' |
'''Anonymous function:''' |
||
This uses the 'fix' function to find the fixed point of the anonymous function. |
This uses the 'fix' function to find the fixed point of the anonymous function. |
||
< |
<syntaxhighlight lang="haskell">import Data.Function (fix) |
||
fib :: Integer -> Maybe Integer |
fib :: Integer -> Maybe Integer |
||
fib n |
fib n |
||
| n < 0 = Nothing |
| n < 0 = Nothing |
||
| otherwise = Just $ fix (\f -> (\n -> if n > 1 then f (n-1) + f (n-2) else 1)) n</ |
| otherwise = Just $ fix (\f -> (\n -> if n > 1 then f (n-1) + f (n-2) else 1)) n</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Both functions provide the same output when run in GHCI. |
Both functions provide the same output when run in GHCI. |
||
< |
<syntaxhighlight 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]</ |
[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]</syntaxhighlight> |
||
Or, without imports (inlining an anonymous fix) |
|||
<syntaxhighlight lang="haskell">fib :: Integer -> Maybe Integer |
|||
fib n |
|||
| n < 0 = Nothing |
|||
| otherwise = |
|||
Just $ |
|||
(\f -> |
|||
let x = f x |
|||
in x) |
|||
(\f n -> |
|||
if n > 1 |
|||
then f (n - 1) + f (n - 2) |
|||
else 1) |
|||
n |
|||
-- TEST ---------------------------------------------------------------------- |
|||
main :: IO () |
|||
main = |
|||
print $ |
|||
fib <$> [-4 .. 10] >>= |
|||
\m -> |
|||
case m of |
|||
Just x -> [x] |
|||
_ -> []</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>[1,1,2,3,5,8,13,21,34,55,89]</pre> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
Line 859: | Line 1,608: | ||
This example does accomplish the goals of hiding the procedure inside ''fib'' so that the type and value checking is outside the recursion. It also does not require an identifier to reference the inner procedure; but, it requires a local variable to remember our return point. Also, each recursion will result in the current co-expression being refreshed, essentially copied, placing a heavy demand on co-expression resources. |
This example does accomplish the goals of hiding the procedure inside ''fib'' so that the type and value checking is outside the recursion. It also does not require an identifier to reference the inner procedure; but, it requires a local variable to remember our return point. Also, each recursion will result in the current co-expression being refreshed, essentially copied, placing a heavy demand on co-expression resources. |
||
< |
<syntaxhighlight lang="icon">procedure main(A) |
||
every write("fib(",a := numeric(!A),")=",fib(a)) |
every write("fib(",a := numeric(!A),")=",fib(a)) |
||
end |
end |
||
Line 882: | Line 1,631: | ||
A := if type(A) == "list" then A[1] |
A := if type(A) == "list" then A[1] |
||
return (@A, A) # prime and return |
return (@A, A) # prime and return |
||
end</ |
end</syntaxhighlight> |
||
Some of the code requires some explaining: |
Some of the code requires some explaining: |
||
* The double curly brace syntax after ''makeProc'' serves two different purposes, the outer set is used in the call to create a co-expression. The inner one binds all the expressions together as a single unit. |
* The double curly brace syntax after ''makeProc'' serves two different purposes, the outer set is used in the call to create a co-expression. The inner one binds all the expressions together as a single unit. |
||
Line 891: | Line 1,640: | ||
For reference, here is the non-cached version: |
For reference, here is the non-cached version: |
||
< |
<syntaxhighlight lang="icon">procedure fib(n) |
||
local source, i |
local source, i |
||
if type(n) == "integer" & n >= 0 then |
if type(n) == "integer" & n >= 0 then |
||
Line 899: | Line 1,648: | ||
((i-1)@makeProc(^¤t) + (i-2)@makeProc(^¤t)) @ source |
((i-1)@makeProc(^¤t) + (i-2)@makeProc(^¤t)) @ source |
||
}} |
}} |
||
end</ |
end</syntaxhighlight> |
||
The performance of this second version is 'truly impressive'. And I mean that in a really bad way. By way of example, using default memory settings on a current laptop, a simple recursive non-cached ''fib'' out distanced the non-cached ''fib'' above by a factor of 20,000. And a simple recursive cached version out distanced the cached version above by a factor of 2,000. |
The performance of this second version is 'truly impressive'. And I mean that in a really bad way. By way of example, using default memory settings on a current laptop, a simple recursive non-cached ''fib'' out distanced the non-cached ''fib'' above by a factor of 20,000. And a simple recursive cached version out distanced the cached version above by a factor of 2,000. |
||
=={{header|Io}}== |
|||
The most natural way to solve this task is to use a nested function whose scope is limited to the helper function. |
|||
<syntaxhighlight lang="io">fib := method(x, |
|||
if(x < 0, Exception raise("Negative argument not allowed!")) |
|||
fib2 := method(n, |
|||
if(n < 2, n, fib2(n-1) + fib2(n-2)) |
|||
) |
|||
fib2(x floor) |
|||
)</syntaxhighlight> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Copied directly from the [[Fibonacci_sequence#J|fibonacci sequence]] task, which in turn copied from one of several implementations in an [[j:Essays/Fibonacci_Sequence|essay]] on the J Wiki: |
Copied directly from the [[Fibonacci_sequence#J|fibonacci sequence]] task, which in turn copied from one of several implementations in an [[j:Essays/Fibonacci_Sequence|essay]] on the J Wiki: |
||
< |
<syntaxhighlight lang="j"> fibN=: (-&2 +&$: -&1)^:(1&<) M."0</syntaxhighlight> |
||
Note that this is an identity function for arguments less than 1 (and 1 (and 5)). |
Note that this is an identity function for arguments less than 1 (and 1 (and 5)). |
||
'''Examples:''' |
'''Examples:''' |
||
< |
<syntaxhighlight lang="j"> fibN 12 |
||
144 |
144 |
||
fibN i.31 |
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</ |
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</syntaxhighlight> |
||
(This implementation is doubly recursive except that results are cached across function calls.) |
(This implementation is doubly recursive except that results are cached across function calls.) |
||
<code>$:</code> is an anonymous reference to the largest containing verb in the sentence. |
<code>$:</code> is an anonymous reference to the largest containing verb in the sentence. |
||
------------- |
|||
Note also http://www.jsoftware.com/pipermail/general/2003-August/015571.html which points out that the form |
|||
<syntaxhighlight lang="j">basis ` ($: @: g) @. test</syntaxhighlight> which is an anonymous form matches the "tail recursion" pattern is not automatically transformed to satisfy the classic "tail recursion optimization". That optimization would be implemented as transforming this particular example of recursion to the non-recursive <syntaxhighlight lang="j">basis @: (g^:test^:_)</syntaxhighlight> |
|||
Of course, that won't work here, because we are adding two recursively obtained results where tail recursion requires that the recursive result is the final result. |
|||
------------- |
|||
See also [[Y_combinator#J|Y combinator]] but note that that approach is less efficient (has higher costs). |
|||
Also, note that J's "implicit mapping" is primitive recursive (as is arithmetic in general), and thus in some contexts a "more efficient approach to recursion". |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
Creates an anonymous inner class to do the dirty work. While it does keep the recursive function out of the namespace of the class, it does seem to violate the spirit of the task in that the function is still named. |
Creates an anonymous inner class to do the dirty work. While it does keep the recursive function out of the namespace of the class, it does seem to violate the spirit of the task in that the function is still named. |
||
< |
<syntaxhighlight lang="java">public static long fib(int n) { |
||
if (n < 0) |
|||
{ |
|||
throw new IllegalArgumentException("n can not be a negative number"); |
|||
if (n < 0) |
|||
throw new IllegalArgumentException("n can not be a negative number"); |
|||
return new Object() { |
return new Object() { |
||
private long fibInner(int n) |
private long fibInner(int n) { |
||
return (n < 2) ? n : (fibInner(n - 1) + fibInner(n - 2)); |
|||
} |
|||
}.fibInner(n); |
|||
}.fibInner(n); |
|||
}</lang> |
|||
}</syntaxhighlight> |
|||
Another way is to use the Java Y combinator implementation (the following uses the Java 8 version for better readability). |
Another way is to use the Java Y combinator implementation (the following uses the Java 8 version for better readability). |
||
Note that the fib method below is practically the same as that of the version above, with less fibInner. |
Note that the fib method below is practically the same as that of the version above, with less fibInner. |
||
< |
<syntaxhighlight lang="java5">import java.util.function.Function; |
||
@FunctionalInterface |
@FunctionalInterface |
||
interface SelfApplicable<OUTPUT> { |
interface SelfApplicable<OUTPUT> { |
||
OUTPUT apply(SelfApplicable<OUTPUT> input); |
OUTPUT apply(SelfApplicable<OUTPUT> input); |
||
} |
} |
||
class Utils { |
class Utils { |
||
public static <INPUT, OUTPUT> SelfApplicable<Function<Function<Function<INPUT, OUTPUT>, Function<INPUT, OUTPUT>>, Function<INPUT, OUTPUT>>> y() { |
public static <INPUT, OUTPUT> SelfApplicable<Function<Function<Function<INPUT, OUTPUT>, Function<INPUT, OUTPUT>>, Function<INPUT, OUTPUT>>> y() { |
||
return y -> f -> x -> f.apply(y.apply(y).apply(f)).apply(x); |
return y -> f -> x -> f.apply(y.apply(y).apply(f)).apply(x); |
||
} |
} |
||
public static <INPUT, OUTPUT> Function<Function<Function<INPUT, OUTPUT>, Function<INPUT, OUTPUT>>, Function<INPUT, OUTPUT>> fix() { |
public static <INPUT, OUTPUT> Function<Function<Function<INPUT, OUTPUT>, Function<INPUT, OUTPUT>>, Function<INPUT, OUTPUT>> fix() { |
||
return Utils.<INPUT, OUTPUT>y().apply(Utils.<INPUT, OUTPUT>y()); |
return Utils.<INPUT, OUTPUT>y().apply(Utils.<INPUT, OUTPUT>y()); |
||
} |
} |
||
public static long fib(int m) { |
public static long fib(int m) { |
||
if (m < 0) |
if (m < 0) |
||
throw new IllegalArgumentException("n can not be a negative number"); |
throw new IllegalArgumentException("n can not be a negative number"); |
||
return Utils.<Integer, Long>fix().apply( |
|||
return Utils.<Integer, Long>fix().apply( |
|||
f -> n -> (n < 2) ? n : (f.apply(n - 1) + f.apply(n - 2)) |
|||
).apply(m); |
|||
).apply(m); |
|||
} |
|||
} |
|||
}</lang> |
|||
}</syntaxhighlight> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
< |
<syntaxhighlight lang="javascript">function fibo(n) { |
||
if (n < 0) |
if (n < 0) { throw "Argument cannot be negative"; } |
||
throw "Argument cannot be negative"; |
|||
return (function(n) { |
|||
else |
|||
return ( |
return (n < 2) ? n : arguments.callee(n-1) + arguments.callee(n-2); |
||
})(n); |
|||
}</syntaxhighlight> |
|||
return 1; |
|||
else |
|||
return arguments.callee(n-1) + arguments.callee(n-2); |
|||
})(n); |
|||
}</lang> |
|||
Note that <code>arguments.callee</code> will not be available in ES5 Strict mode. Instead, you are expected to "name" function (the name is only visible inside function however). |
Note that <code>arguments.callee</code> will not be available in ES5 Strict mode. Instead, you are expected to "name" function (the name is only visible inside function however). |
||
< |
<syntaxhighlight lang="javascript">function fibo(n) { |
||
if (n < 0) |
if (n < 0) { throw "Argument cannot be negative"; } |
||
throw "Argument cannot be negative"; |
|||
return (function fib(n) { |
|||
else |
|||
return ( |
return (n < 2) ? n : fib(n-1) + fib(n-2); |
||
})(n); |
|||
}</syntaxhighlight> |
|||
return 1; |
|||
else |
|||
=={{header|Joy}}== |
|||
return fib(n-1) + fib(n-2); |
|||
This definition is taken from "Recursion Theory and Joy" by Manfred von Thun. |
|||
})(n); |
|||
<syntaxhighlight lang="joy">fib == [small] [] [pred dup pred] [+] binrec;</syntaxhighlight> |
|||
}</lang> |
|||
=={{header|jq}}== |
=={{header|jq}}== |
||
The "recurse" filter supports a type of anonymous recursion, e.g. to generate a stream of integers starting at 0: |
|||
As is the case, for example, with Julia, jq allows you to define an inner/nested function (here, <code>aux</code>) that is only defined within the surrounding function <code>fib</code> scope. Thus using such auxiliary functions does not cause name space pollution. |
|||
<syntaxhighlight lang="jq">0 | recurse(. + 1)</syntaxhighlight> |
|||
<lang jq>def fib(n): |
|||
Also, as is the case for example with Julia, jq allows you to define an inner/nested function (in the follow example, <code>aux</code>) that is only defined within the scope of the surrounding function (here <code>fib</code>). It is thus invisible outside the function: |
|||
<syntaxhighlight lang="jq">def fib(n): |
|||
def aux: if . == 0 then 0 |
def aux: if . == 0 then 0 |
||
elif . == 1 then 1 |
elif . == 1 then 1 |
||
Line 991: | Line 1,765: | ||
if n < 0 then error("negative arguments not allowed") |
if n < 0 then error("negative arguments not allowed") |
||
else n | aux |
else n | aux |
||
end ;</ |
end ;</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Julia allows you to define an inner/nested function (here, <code>aux</code>) that is only defined within the surrounding function <code>fib</code> scope. |
Julia allows you to define an inner/nested function (here, <code>aux</code>) that is only defined within the surrounding function <code>fib</code> scope. |
||
< |
<syntaxhighlight lang="julia">function fib(n) |
||
if n < 0 |
if n < 0 |
||
throw(ArgumentError("negative arguments not allowed")) |
throw(ArgumentError("negative arguments not allowed")) |
||
Line 1,001: | Line 1,775: | ||
aux(m) = m < 2 ? one(m) : aux(m-1) + aux(m-2) |
aux(m) = m < 2 ? one(m) : aux(m-1) + aux(m-2) |
||
aux(n) |
aux(n) |
||
end</ |
end</syntaxhighlight> |
||
=={{header|K}}== |
=={{header|K}}== |
||
{{works with|Kona}} |
|||
<lang k>fib: {:[x<0; "Error Negative Number"; {:[x<2;x;_f[x-2]+_f[x-1]]}x]}</lang> |
|||
<syntaxhighlight lang="k">fib: {:[x<0; "Error Negative Number"; {:[x<2;x;_f[x-2]+_f[x-1]]}x]}</syntaxhighlight> |
|||
{{works with|ngn/k}}: |
|||
<syntaxhighlight lang=K>fib: {:[x<0; "Error Negative Number"; {:[x<2;x;o[x-2]+o[x-1]]}x]}</syntaxhighlight> |
|||
'''Examples:''' |
'''Examples:''' |
||
< |
<syntaxhighlight lang="k"> fib'!10 |
||
0 1 1 2 3 5 8 13 21 34 |
0 1 1 2 3 5 8 13 21 34 |
||
fib -1 |
fib -1 |
||
"Error Negative Number"</ |
"Error Negative Number"</syntaxhighlight> |
||
=={{header|Klingphix}}== |
|||
<syntaxhighlight lang="text">include ..\Utilitys.tlhy |
|||
:fib %f !f |
|||
%fr |
|||
[ %n !n |
|||
$n 2 < |
|||
( [$n] |
|||
[$n 1 - $fr eval $n 2 - $fr eval +] ) |
|||
if |
|||
] !fr |
|||
$f 0 < |
|||
( ["Error: number is negative"] |
|||
[$f true $fr if] ) |
|||
if |
|||
; |
|||
25 fib ? |
|||
msec ? |
|||
"End " input</syntaxhighlight> |
|||
=={{header|Klong}}== |
|||
<syntaxhighlight lang="k"> |
|||
fib::{:[x<0;"error: negative":|x<2;x;.f(x-1)+.f(x-2)]} |
|||
</syntaxhighlight> |
|||
=={{header|Kotlin}}== |
|||
{{trans|Dylan}} |
|||
<syntaxhighlight lang="kotlin">fun fib(n: Int): Int { |
|||
require(n >= 0) |
|||
fun fib(k: Int, a: Int, b: Int): Int = |
|||
if (k == 0) a else fib(k - 1, b, a + b) |
|||
return fib(n, 0, 1) |
|||
} |
|||
fun main(args: Array<String>) { |
|||
for (i in 0..20) print("${fib(i)} ") |
|||
println() |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 |
|||
</pre> |
|||
=={{header|Lambdatalk}}== |
|||
<syntaxhighlight lang="scheme"> |
|||
1) defining a quasi-recursive function combined with a simple Ω-combinator: |
|||
{def fibo {lambda {:n} |
|||
{{{lambda {:f} {:f :f}} |
|||
{lambda {:f :n :a :b} |
|||
{if {< :n 0} |
|||
then the number must be positive! |
|||
else {if {< :n 1} |
|||
then :a |
|||
else {:f :f {- :n 1} {+ :a :b} :a}}}}} :n 1 0}}} |
|||
-> fibo |
|||
2) testing: |
|||
{fibo -1} -> the number must be positive! |
|||
{fibo 0} -> 1 |
|||
{fibo 8} -> 34 |
|||
{fibo 1000} -> 7.0330367711422765e+208 |
|||
{S.map fibo {S.serie 1 20}} |
|||
-> 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 |
|||
We could also avoid any name and write an IIFE |
|||
{{lambda {:n} |
|||
{{{lambda {:f} {:f :f}} |
|||
{lambda {:f :n :a :b} |
|||
{if {< :n 0} |
|||
then the number must be positive! |
|||
else {if {< :n 1} |
|||
then :a |
|||
else {:f :f {- :n 1} {+ :a :b} :a}}}}} :n 1 0}} |
|||
8} |
|||
-> 34 |
|||
</syntaxhighlight> |
|||
=={{header|Lang}}== |
|||
<syntaxhighlight lang="lang"> |
|||
fp.fib = ($n) -> { |
|||
if($n < 0) { |
|||
throw fn.withErrorMessage($LANG_ERROR_INVALID_ARGUMENTS, n must be >= 0) |
|||
} |
|||
fp.innerFib = ($n) -> { |
|||
if($n < 2) { |
|||
return $n |
|||
} |
|||
return parser.op(fp.innerFib($n - 1) + fp.innerFib($n - 2)) |
|||
} |
|||
return fp.innerFib($n) |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|Lingo}}== |
|||
Lingo does not support anonymous functions. But what comes close: you can create and instantiate an "anonymous class": |
|||
<syntaxhighlight lang="lingo">on fib (n) |
|||
if n<0 then return _player.alert("negative arguments not allowed") |
|||
-- create instance of unnamed class in memory only (does not pollute namespace) |
|||
m = new(#script) |
|||
r = RETURN |
|||
m.scriptText = "on fib (me,n)"&r&"if n<2 then return n"&r&"return me.fib(n-1)+me.fib(n-2)"&r&"end" |
|||
aux = m.script.new() |
|||
m.erase() |
|||
return aux.fib(n) |
|||
end</syntaxhighlight> |
|||
<syntaxhighlight lang="lingo">put fib(10) |
|||
-- 55</syntaxhighlight> |
|||
=={{header|LOLCODE}}== |
=={{header|LOLCODE}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="lolcode">HAI 1.3 |
||
HOW IZ I fib YR x |
HOW IZ I fib YR x |
||
Line 1,044: | Line 1,941: | ||
I IZ fib_i YR 3 MKAY |
I IZ fib_i YR 3 MKAY |
||
KTHXBYE</ |
KTHXBYE</syntaxhighlight> |
||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Using a [[Y combinator]]. |
Using a [[Y combinator]]. |
||
< |
<syntaxhighlight 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 Y(function(fibs) |
||
Line 1,054: | Line 1,951: | ||
return n < 2 and 1 or fibs(n - 1) + fibs(n - 2) |
return n < 2 and 1 or fibs(n - 1) + fibs(n - 2) |
||
end |
end |
||
end)</ |
end)</syntaxhighlight> |
||
using a metatable (also achieves memoization) |
using a metatable (also achieves memoization) |
||
< |
<syntaxhighlight lang="lua">return setmetatable({1,1},{__index = function(self, n) |
||
self[n] = self[n-1] + self[n-2] |
self[n] = self[n-1] + self[n-2] |
||
return self[n] |
return self[n] |
||
end})</ |
end})</syntaxhighlight> |
||
=={{header|M2000 Interpreter}}== |
|||
We can use a function in string. We can named it so the error say about "Fibonacci" |
|||
To exclude first check for negative we have to declare a function in anonymous function, which may have a name (a local name) |
|||
<syntaxhighlight lang="m2000 interpreter"> |
|||
A$={{ Module "Fibonacci" : Read X :If X<0 then {Error {X<0}} Else Fib=Lambda (x)->if(x>1->fib(x-1)+fib(x-2), x) : =fib(x)}} |
|||
Try Ok { |
|||
Print Function(A$, -12) |
|||
} |
|||
If Error or Not Ok Then Print Error$ |
|||
Print Function(A$, 12)=144 ' true |
|||
</syntaxhighlight> |
|||
For recursion we can use Lambda() or Lambda$() (for functions which return string) and not name of function so we can use it in a referenced function. Here in k() if we have the fib() we get an error, but with lambda(), interpreter use current function's name. |
|||
<syntaxhighlight lang="m2000 interpreter"> |
|||
Function fib(x) { |
|||
If x<0 then Error "argument outside of range" |
|||
If x<2 then =x : exit |
|||
Def fib1(x)=If(x>1->lambda(x-1)+lambda(x-2), x) |
|||
=fib1(x) |
|||
} |
|||
Module CheckIt (&k()) { |
|||
Print k(12) |
|||
} |
|||
CheckIt &Fib() |
|||
Print fib(-2) ' error |
|||
</syntaxhighlight> |
|||
Using lambda function |
|||
<syntaxhighlight lang="m2000 interpreter"> |
|||
fib=lambda -> { |
|||
fib1=lambda (x)->If(x>1->lambda(x-1)+lambda(x-2), x) |
|||
=lambda fib1 (x) -> { |
|||
If x<0 then Error "argument outside of range" |
|||
If x<2 then =x : exit |
|||
=fib1(x) |
|||
} |
|||
}() ' using () execute this lambda so fib get the returned lambda |
|||
Module CheckIt (&k()) { |
|||
Print k(12) |
|||
} |
|||
CheckIt &Fib() |
|||
Try { |
|||
Print fib(-2) |
|||
} |
|||
Print Error$ |
|||
Z=Fib |
|||
Print Z(12) |
|||
Dim a(10) |
|||
a(3)=Z |
|||
Print a(3)(12)=144 |
|||
Inventory Alfa = "key1":=Z |
|||
Print Alfa("key1")(12)=144 |
|||
</syntaxhighlight> |
|||
Using a Group (object in M2000) like a function |
|||
A Group may have a name like k (which hold a unique group), or can be unnamed like item in A(4), or can be pointed by a variable (or an array item) (we can use many pointers for the same group) |
|||
<syntaxhighlight lang="m2000 interpreter"> |
|||
Class Something { |
|||
\\ this class is a global function |
|||
\\ return a group with a value with one parameter |
|||
private: |
|||
\\ we can use lambda(), but here we use .fib1() as This.fib1() |
|||
fib1=lambda (x)->If(x>1->.fib1(x-1)+.fib1(x-2), x) |
|||
public: |
|||
Value (x) { |
|||
If x<0 then Error "argument outside of range" |
|||
If x<2 then =x : exit |
|||
=This.fib1(x) \\ we can omit This using .fib1(x) |
|||
} |
|||
} |
|||
K=Something() ' K is a static group here |
|||
Print k(12)=144 |
|||
Dim a(10) |
|||
a(4)=Group(K) |
|||
Print a(4)(12)=144 |
|||
pk->Something() ' pk is a pointer to group (object in M2000) |
|||
\\ pointers need Eval to process arguments |
|||
Print Eval(pk, 12)=144 |
|||
Inventory Alfa = "Key2":=Group(k), 10*10:=pk |
|||
Print Alfa("Key2")(12)=144 |
|||
Print Eval(Alfa("100"),12)=144, Eval(Alfa(100),12)=144 |
|||
</syntaxhighlight> |
|||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
In Maple, the keyword thisproc refers to the currently executing procedure (closure), which need not be named. The following defines a procedure Fib, which uses a recursive, anonymous (unnamed) procedure to implement the Fibonacci sequence. For better efficiency, we use Maple's facility for automatic memoisation ("option remember"). |
In Maple, the keyword thisproc refers to the currently executing procedure (closure), which need not be named. The following defines a procedure Fib, which uses a recursive, anonymous (unnamed) procedure to implement the Fibonacci sequence. For better efficiency, we use Maple's facility for automatic memoisation ("option remember"). |
||
<syntaxhighlight lang="maple"> |
|||
<lang Maple> |
|||
Fib := proc( n :: nonnegint ) |
Fib := proc( n :: nonnegint ) |
||
proc( k ) |
proc( k ) |
||
Line 1,077: | Line 2,062: | ||
end( n ) |
end( n ) |
||
end proc: |
end proc: |
||
</syntaxhighlight> |
|||
</lang> |
|||
For example: |
For example: |
||
<syntaxhighlight lang="maple"> |
|||
<lang Maple> |
|||
> seq( Fib( i ), i = 0 .. 10 ); |
> seq( Fib( i ), i = 0 .. 10 ); |
||
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 |
||
Line 1,086: | Line 2,071: | ||
Error, invalid input: Fib expects its 1st argument, n, to be of type |
Error, invalid input: Fib expects its 1st argument, n, to be of type |
||
nonnegint, but received -1 |
nonnegint, but received -1 |
||
</syntaxhighlight> |
|||
</lang> |
|||
The check for a negative argument could be put either on the outer Fib procedure, or the anonymous inner procedure (or both). As it wasn't completely clear what was intended, I put it on Fib, which results in a slightly better error message in that it does not reveal how the procedure was actually implemented. |
The check for a negative argument could be put either on the outer Fib procedure, or the anonymous inner procedure (or both). As it wasn't completely clear what was intended, I put it on Fib, which results in a slightly better error message in that it does not reveal how the procedure was actually implemented. |
||
=={{header|Mathematica}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
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 [http://reference.wolfram.com/mathematica/tutorial/PureFunctions.html pure functions] in 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 [http://reference.wolfram.com/mathematica/tutorial/PureFunctions.html pure functions] in Mathematica. |
||
< |
<syntaxhighlight lang="mathematica">check := #<0& |
||
fib := If[check[#],Throw["Negative Argument"],If[#<=1,1,#0[#-2]+#0[#-1]]&[#]]& |
fib := If[check[#],Throw["Negative Argument"],If[#<=1,1,#0[#-2]+#0[#-1]]&[#]]& |
||
fib /@ Range[0,10] |
fib /@ Range[0,10] |
||
{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}</ |
{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}</syntaxhighlight> |
||
Making sure that the check is only performed once. |
Making sure that the check is only performed once. |
||
< |
<syntaxhighlight lang="mathematica">check := (Print[#];#<0)& |
||
fib /@ Range[0,4] |
fib /@ Range[0,4] |
||
0 |
0 |
||
Line 1,105: | Line 2,090: | ||
4 |
4 |
||
{1, 1, 2, 3, 5}</ |
{1, 1, 2, 3, 5}</syntaxhighlight> |
||
=={{header|MATLAB}}== |
|||
Not anonymous exactly, but using a nested function solves all the problems stated in the task description. |
|||
* does not exist outside of parent function |
|||
* does not need a new name, can reuse the parent name |
|||
* a nested function can be defined in the place where it is needed |
|||
<syntaxhighlight lang="matlab"> |
|||
function v = fibonacci(n) |
|||
assert(n >= 0) |
|||
v = fibonacci(n,0,1); |
|||
% nested function |
|||
function a = fibonacci(n,a,b) |
|||
if n ~= 0 |
|||
a = fibonacci(n-1,b,a+b); |
|||
end |
|||
end |
|||
end |
|||
</syntaxhighlight> |
|||
=={{header|Nemerle}}== |
=={{header|Nemerle}}== |
||
Line 1,112: | Line 2,115: | ||
* inner function not expected to be called from anywhere else |
* inner function not expected to be called from anywhere else |
||
* nesting maintains program flow in source code |
* nesting maintains program flow in source code |
||
< |
<syntaxhighlight lang="nemerle">using System; |
||
using System.Console; |
using System.Console; |
||
Line 1,141: | Line 2,144: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header| |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim"># Using scoped function fibI inside fib |
||
proc fib(x): int = |
proc fib(x: int): int = |
||
proc fibI(n): int = |
proc fibI(n: int): int = |
||
if n < 2: n else: fibI(n-2) + fibI(n-1) |
if n < 2: n else: fibI(n-2) + fibI(n-1) |
||
if x < 0: |
if x < 0: |
||
raise newException( |
raise newException(ValueError, "Invalid argument") |
||
return fibI(x) |
return fibI(x) |
||
Line 1,155: | Line 2,158: | ||
echo fib(i) |
echo fib(i) |
||
# fibI(10) # undeclared identifier 'fibI'</ |
# fibI(10) # undeclared identifier 'fibI'</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>0 |
<pre>0 |
||
Line 1,165: | Line 2,168: | ||
=={{header|Objective-C}}== |
=={{header|Objective-C}}== |
||
This shows how a method (not regular function) can recursively call itself without explicitly putting its name in the code. |
This shows how a method (not regular function) can recursively call itself without explicitly putting its name in the code. |
||
< |
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h> |
||
@interface AnonymousRecursion : NSObject { } |
@interface AnonymousRecursion : NSObject { } |
||
Line 1,196: | Line 2,199: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
;With internal named recursive block: |
;With internal named recursive block: |
||
{{works with|Mac OS X|10.6+}} |
{{works with|Mac OS X|10.6+}} |
||
< |
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h> |
||
int fib(int n) { |
int fib(int n) { |
||
Line 1,225: | Line 2,228: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
When ARC is disabled, the above should be: |
When ARC is disabled, the above should be: |
||
< |
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h> |
||
int fib(int n) { |
int fib(int n) { |
||
Line 1,252: | Line 2,255: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
Line 1,261: | Line 2,264: | ||
We're defining a function 'real' which is only available from within the fib function. |
We're defining a function 'real' which is only available from within the fib function. |
||
< |
<syntaxhighlight lang="ocaml">let fib n = |
||
let rec real = function |
let rec real = function |
||
0 -> 1 |
0 -> 1 |
||
Line 1,270: | Line 2,273: | ||
None |
None |
||
else |
else |
||
Some (real n)</ |
Some (real n)</syntaxhighlight> |
||
'''Anonymous function:''' |
'''Anonymous function:''' |
||
This uses the 'fix' function to find the fixed point of the anonymous function. |
This uses the 'fix' function to find the fixed point of the anonymous function. |
||
< |
<syntaxhighlight lang="ocaml">let rec fix f x = f (fix f) x |
||
let fib n = |
let fib n = |
||
Line 1,281: | Line 2,284: | ||
None |
None |
||
else |
else |
||
Some (fix (fun f -> fun n -> if n <= 1 then 1 else f (n-1) + f (n-2)) n)</ |
Some (fix (fun f -> fun n -> if n <= 1 then 1 else f (n-1) + f (n-2)) n)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre># fib 8;; |
<pre># fib 8;; |
||
- : int option = Some 34</pre> |
- : int option = Some 34</pre> |
||
=={{header|Ol}}== |
|||
This uses named let to create a local function (loop) that only exists inside of function fibonacci. |
|||
<syntaxhighlight lang="scheme"> |
|||
(define (fibonacci n) |
|||
(if (> 0 n) |
|||
"error: negative argument." |
|||
(let loop ((a 1) (b 0) (count n)) |
|||
(if (= count 0) |
|||
b |
|||
(loop (+ a b) a (- count 1)))))) |
|||
(print |
|||
(map fibonacci '(1 2 3 4 5 6 7 8 9 10))) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>'(1 1 2 3 5 8 13 21 34 55)</pre> |
|||
=={{header|OxygenBasic}}== |
=={{header|OxygenBasic}}== |
||
An inner function keeps the name-space clean: |
An inner function keeps the name-space clean: |
||
< |
<syntaxhighlight lang="oxygenbasic"> |
||
function fiboRatio() as double |
function fiboRatio() as double |
||
function fibo( double i, j ) as double |
function fibo( double i, j ) as double |
||
Line 1,299: | Line 2,319: | ||
print fiboRatio |
print fiboRatio |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
This version uses a Y combinator to get a self-reference. |
|||
<lang parigp>Fib(n)={ |
|||
<syntaxhighlight lang="parigp">Fib(n)={ |
|||
my(F=(k,f)->if(k<2,k,f(k-1,f)+f(k-2,f))); |
my(F=(k,f)->if(k<2,k,f(k-1,f)+f(k-2,f))); |
||
if(n<0,(-1)^(n+1),1)*F(abs(n),F) |
if(n<0,(-1)^(n+1),1)*F(abs(n),F) |
||
};</ |
};</syntaxhighlight> |
||
{{works with|PARI/GP|2.8.1+}} |
|||
This version gets a self-reference from <code>self()</code>. |
|||
<syntaxhighlight lang="parigp">Fib(n)={ |
|||
my(F=k->my(f=self());if(k<2,k,f(k-1)+f(k-2))); |
|||
if(n<0,(-1)^(n+1),1)*F(abs(n)) |
|||
};</syntaxhighlight> |
|||
=={{header|Pascal}}== |
|||
<syntaxhighlight lang="pascal"> |
|||
program AnonymousRecursion; |
|||
function Fib(X: Integer): integer; |
|||
function DoFib(N: Integer): Integer; |
|||
begin |
|||
if N < 2 then DoFib:=N |
|||
else DoFib:=DoFib(N-1) + DoFib(N-2); |
|||
end; |
|||
begin |
|||
if X < 0 then Fib:=X |
|||
else Fib:=DoFib(X); |
|||
end; |
|||
var I,V: integer; |
|||
begin |
|||
for I:=-1 to 15 do |
|||
begin |
|||
V:=Fib(I); |
|||
Write(I:3,' - ',V:3); |
|||
if V<0 then Write(' - Error'); |
|||
WriteLn; |
|||
end; |
|||
WriteLn('Hit Any Key'); |
|||
ReadLn; |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
-1 - -1 - Error |
|||
0 - 0 |
|||
1 - 1 |
|||
2 - 1 |
|||
3 - 2 |
|||
4 - 3 |
|||
5 - 5 |
|||
6 - 8 |
|||
7 - 13 |
|||
8 - 21 |
|||
9 - 34 |
|||
10 - 55 |
|||
11 - 89 |
|||
12 - 144 |
|||
13 - 233 |
|||
14 - 377 |
|||
15 - 610 |
|||
Hit Any Key |
|||
</pre> |
|||
=={{header|PascalABC.NET}}== |
|||
<syntaxhighlight lang="pascal"> |
|||
function Fib(n: integer): integer; |
|||
begin |
|||
if n <= 0 then |
|||
raise new System.ArgumentOutOfRangeException('Must be > 0','n'); |
|||
var fibHelper: (integer,integer,integer) -> integer; |
|||
fibHelper := (n,a,b) -> n = 1 ? a : fibHelper(n-1, b, a + b); |
|||
Result := fibHelper(n,1,1); |
|||
end; |
|||
begin |
|||
for var i:=1 to 10 do |
|||
Fib(i).Print; |
|||
end. |
|||
</syntaxhighlight> |
|||
or |
|||
<syntaxhighlight lang="pascal"> |
|||
function Fib(n: integer): integer; |
|||
function fibHelper(n,a,b: integer): integer := |
|||
n = 1 ? a : fibHelper(n-1, b, a + b); |
|||
begin |
|||
if n <= 0 then |
|||
raise new System.ArgumentOutOfRangeException('Must be > 0','n'); |
|||
Result := fibHelper(n,1,1); |
|||
end; |
|||
begin |
|||
for var i:=1 to 10 do |
|||
Fib(i).Print; |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
1 1 2 3 5 8 13 21 34 55 |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|PicoLisp}} |
{{trans|PicoLisp}} |
||
<code>recur</code> isn't built into Perl, but it's easy to implement. |
<code>recur</code> isn't built into Perl, but it's easy to implement. |
||
< |
<syntaxhighlight lang="perl">sub recur :prototype(&@) { |
||
my $f = shift; |
my $f = shift; |
||
local *recurse = $f; |
local *recurse = $f; |
||
Line 1,323: | Line 2,444: | ||
$m < 3 ? 1 : recurse($m - 1) + recurse($m - 2); |
$m < 3 ? 1 : recurse($m - 1) + recurse($m - 2); |
||
} $n; |
} $n; |
||
}</ |
}</syntaxhighlight> |
||
Although for this task, it would be fine to use a lexical variable (closure) to hold an anonymous sub reference, we can also just push it onto the args stack and use it from there: |
Although for this task, it would be fine to use a lexical variable (closure) to hold an anonymous sub reference, we can also just push it onto the args stack and use it from there: |
||
< |
<syntaxhighlight lang="perl">sub fib { |
||
my ($n) = @_; |
my ($n) = @_; |
||
die "negative arg $n" if $n < 0; |
die "negative arg $n" if $n < 0; |
||
Line 1,337: | Line 2,458: | ||
} |
} |
||
print(fib($_), " ") for (0 .. 10);</ |
print(fib($_), " ") for (0 .. 10);</syntaxhighlight> |
||
One can also use <code>caller</code> 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: <code>caller</code> will just return <code>'__ANON__'</code> 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 <code>no strict 'refs';</code> is needed to permit using a string as a subroutine. |
One can also use <code>caller</code> 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: <code>caller</code> will just return <code>'__ANON__'</code> 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 <code>no strict 'refs';</code> is needed to permit using a string as a subroutine. |
||
< |
<syntaxhighlight lang="perl">sub fibo { |
||
my $n = shift; |
my $n = shift; |
||
$n < 0 and die 'Negative argument'; |
$n < 0 and die 'Negative argument'; |
||
no strict 'refs'; |
no strict 'refs'; |
||
$n < 3 ? 1 : (caller(0))[3]->($n - 1) + (caller(0))[3]->($n - 2); |
$n < 3 ? 1 : (caller(0))[3]->($n - 1) + (caller(0))[3]->($n - 2); |
||
}</ |
}</syntaxhighlight> |
||
===Perl 5.16 and __SUB__=== |
===Perl 5.16 and __SUB__=== |
||
Perl 5.16 introduced __SUB__ which refers to the current subroutine. |
Perl 5.16 introduced __SUB__ which refers to the current subroutine. |
||
< |
<syntaxhighlight lang="perl">use v5.16; |
||
say sub { |
say sub { |
||
my $n = shift; |
my $n = shift; |
||
$n < 2 ? $n : __SUB__->($n-2) + __SUB__->($n-1) |
$n < 2 ? $n : __SUB__->($n-2) + __SUB__->($n-1) |
||
}->($_) for 0..10</ |
}->($_) for 0..10</syntaxhighlight> |
||
=={{header| |
=={{header|Phix}}== |
||
{{libheader|Phix/Class}} |
|||
In addition to the methods in the [[Perl]] entry above, and the Y-combinator described in [[Y_combinator]], you may also refer to an anonymous block or function from the inside: |
|||
===using classes=== |
|||
<lang perl6>sub fib($n) { |
|||
With proof that the private fib_i() does not pollute the outer namespace. |
|||
die "Naughty fib" if $n < 0; |
|||
<!--<syntaxhighlight lang="phix">(notonline)--> |
|||
return { |
|||
<span style="color: #008080;">without</span> <span style="color: #008080;">js</span> <span style="color: #000080;font-style:italic;">-- (no class yet)</span> |
|||
$_ < 2 |
|||
<span style="color: #008080;">class</span> <span style="color: #000000;">Fib</span> |
|||
?? $_ |
|||
<span style="color: #008080;">private</span> <span style="color: #008080;">function</span> <span style="color: #000000;">fib_i</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
!! &?BLOCK($_-1) + &?BLOCK($_-2); |
|||
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span><span style="color: #0000FF;">?</span><span style="color: #000000;">n</span><span style="color: #0000FF;">:</span><span style="color: #7060A8;">this</span><span style="color: #0000FF;">.</span><span style="color: #000000;">fib_i</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">this</span><span style="color: #0000FF;">.</span><span style="color: #000000;">fib_i</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">))</span> |
|||
}($n); |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
} |
|||
<span style="color: #008080;">public</span> <span style="color: #008080;">function</span> <span style="color: #000000;">fib</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">throw</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"constraint error"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
say fib(10);</lang> |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">this</span><span style="color: #0000FF;">.</span><span style="color: #000000;">fib_i</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
However, using any of these methods is insane, when Perl 6 provides a sort of inside-out combinator that lets you define lazy infinite constants, where the demand for a particular value is divorced from dependencies on more primitive values. This operator, known as the sequence operator, does in a sense provide anonymous recursion to a closure that refers to more primitive values. |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<lang perl6>constant @fib = 0, 1, *+* ... *; |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">class</span> |
|||
say @fib[10];</lang> |
|||
<span style="color: #000000;">Fib</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new</span><span style="color: #0000FF;">()</span> |
|||
Here the closure, <tt>*+*</tt>, is just a quick way to write a lambda, <tt>-> $a, $b { $a + $b }</tt>. The sequence operator implicitly maps the two arguments to the -2nd and -1st elements of the sequence. So the sequence operator certainly applies an anonymous lambda, but whether it's recursion or not depends on whether you view a sequence as iteration or as simply a convenient way of memoizing a recursion. Either view is justifiable. |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">fib_i</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
At this point someone may complain that the solution is doesn't fit the specified task because the sequence operator doesn't do the check for negative. True, but the sequence operator is not the whole of the solution; this check is supplied by the subscripting operator itself when you ask for <tt>@fib[-1]</tt>. Instead of scattering all kinds of arbitrary boundary conditions throughout your functions, the sequence operator maps them quite naturally to the boundary of definedness at the start of a list. |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"this is not the fib_i(%d) you are looking for\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">f</span><span style="color: #0000FF;">.</span><span style="color: #000000;">fib</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">--?f.fib_i(10) -- illegal</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">fib_i</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
55 |
|||
"this is not the fib_i(10) you are looking for\n" |
|||
</pre> |
|||
===using a lambda expression=== |
|||
Make of this what you will...<br> |
|||
Obviously the inner function does not have to and in fact is not allowed to have a name itself, but it needs to be stored in something with a name before it can be called, |
|||
and in being anonymous, in order to effect recursion it must be passed to itself, repeatedly and not really anonymous at all anymore. |
|||
<!--<syntaxhighlight lang="phix">(notonline)--> |
|||
<span style="color: #008080;">without</span> <span style="color: #008080;">js</span> <span style="color: #000080;font-style:italic;">-- (no lambda yet)</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">erm</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">fib</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">throw</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"constraint error"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">erm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #008080;">function</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span><span style="color: #0000FF;">?</span><span style="color: #000000;">n</span><span style="color: #0000FF;">:</span><span style="color: #000000;">f</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">f</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">fib</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
55 |
|||
</pre> |
|||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
In this solution, the function is always called using <code>call_user_func()</code> rather than using function call syntax directly. Inside the function, we get the function itself (without having to refer to the function by name) by relying on the fact that this function must have been passed as the first argument to <code>call_user_func()</code> one call up on the call stack. We can then use <code>debug_backtrace()</code> to get this out. |
|||
Don't know if this counts, but... |
|||
{{works with|PHP|5.3+}} |
|||
<lang php><?php |
|||
<syntaxhighlight lang="php"><?php |
|||
function fib($n) { |
function fib($n) { |
||
if ($n < 0) |
if ($n < 0) |
||
throw new Exception('Negative numbers not allowed'); |
throw new Exception('Negative numbers not allowed'); |
||
$f = function($n) { // This function must be called using call_user_func() only |
|||
else if ($n < 2) |
|||
if ($n < 2) |
|||
return 1; |
|||
else { |
|||
else { |
|||
$g = debug_backtrace()[1]['args'][0]; |
|||
return call_user_func($g, $n-1) + call_user_func($g, $n-2); |
|||
} |
|||
} |
|||
}; |
|||
return call_user_func($f, $n); |
|||
} |
} |
||
echo fib(8), "\n"; |
echo fib(8), "\n"; |
||
?></ |
?></syntaxhighlight> |
||
However, <tt>__FUNCTION__</tt> won't work for anonymous functions created with <tt>create_function()</tt> or closures in PHP 5.3+. |
|||
;With internal named recursive function: |
;With internal named recursive function: |
||
{{works with|PHP|5.3+}} |
{{works with|PHP|5.3+}} |
||
< |
<syntaxhighlight lang="php"><?php |
||
function fib($n) { |
function fib($n) { |
||
if ($n < 0) |
if ($n < 0) |
||
Line 1,404: | Line 2,561: | ||
} |
} |
||
echo fib(8), "\n"; |
echo fib(8), "\n"; |
||
?></ |
?></syntaxhighlight> |
||
;With a function object that can call itself using <code>$this</code>: |
;With a function object that can call itself using <code>$this</code>: |
||
{{works with|PHP|5.3+}} |
{{works with|PHP|5.3+}} |
||
< |
<syntaxhighlight lang="php"><?php |
||
class fib_helper { |
class fib_helper { |
||
function __invoke($n) { |
function __invoke($n) { |
||
Line 1,425: | Line 2,582: | ||
} |
} |
||
echo fib(8), "\n"; |
echo fib(8), "\n"; |
||
?></ |
?></syntaxhighlight> |
||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de fibo (N) |
||
(if (lt0 N) |
(if (lt0 N) |
||
(quit "Illegal argument" N) ) |
(quit "Illegal argument" N) ) |
||
Line 1,434: | Line 2,591: | ||
(if (> 2 N) |
(if (> 2 N) |
||
1 |
1 |
||
(+ (recurse (dec N)) (recurse (- N 2))) ) ) )</ |
(+ (recurse (dec N)) (recurse (- N 2))) ) ) )</syntaxhighlight> |
||
Explanation: The above uses the '[http://software-lab.de/doc/refR.html#recur recur]' / '[http://software-lab.de/doc/refR.html#recurse recurse]' function pair, which is defined as a standard language extensions as |
Explanation: The above uses the '[http://software-lab.de/doc/refR.html#recur recur]' / '[http://software-lab.de/doc/refR.html#recurse recurse]' function pair, which is defined as a standard language extensions as |
||
< |
<syntaxhighlight lang="picolisp">(de recur recurse |
||
(run (cdr recurse)) )</ |
(run (cdr recurse)) )</syntaxhighlight> |
||
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'. |
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'. |
||
Line 1,443: | Line 2,600: | ||
{{libheader|initlib}} |
{{libheader|initlib}} |
||
Postscript can make use of the higher order combinators to provide recursion. |
Postscript can make use of the higher order combinators to provide recursion. |
||
< |
<syntaxhighlight lang="postscript">% primitive recursion |
||
/pfact { |
/pfact { |
||
{1} {*} primrec}. |
{1} {*} primrec}. |
||
Line 1,465: | Line 2,622: | ||
% binary recursion |
% binary recursion |
||
/fib { |
/fib { |
||
{2 lt} {} {pred dup pred} {+} binrec}.</ |
{2 lt} {} {pred dup pred} {+} binrec}.</syntaxhighlight> |
||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Works with SWI-Prolog and module <b>lambda</b>, written by <b>Ulrich Neumerkel</b> found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl |
Works with SWI-Prolog and module <b>lambda</b>, written by <b>Ulrich Neumerkel</b> 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. |
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. |
||
< |
<syntaxhighlight lang="prolog">:- use_module(lambda). |
||
fib(N, _F) :- |
fib(N, _F) :- |
||
Line 1,492: | Line 2,649: | ||
Pred = PF +\Nb2^F2^call(PF,Nb2,F2,PF), |
Pred = PF +\Nb2^F2^call(PF,Nb2,F2,PF), |
||
call(Pred,N,F).</ |
call(Pred,N,F).</syntaxhighlight> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight 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))) |
>>> 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) ] |
>>> [ Y(fib)(i) for i in range(-2, 10) ] |
||
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</ |
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</syntaxhighlight> |
||
Same thing as the above, but modified so that the function is uncurried: |
Same thing as the above, but modified so that the function is uncurried: |
||
< |
<syntaxhighlight lang="python">>>>from functools import partial |
||
>>> Y = lambda f: (lambda x: x(x))(lambda y: partial(f, lambda *args: y(y)(*args))) |
>>> Y = lambda f: (lambda x: x(x))(lambda y: partial(f, lambda *args: y(y)(*args))) |
||
>>> fib = lambda f, n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2))) |
>>> fib = lambda f, 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) ] |
>>> [ Y(fib)(i) for i in range(-2, 10) ] |
||
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</ |
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</syntaxhighlight> |
||
A different approach: the function always receives itself as the first argument, and when recursing, makes sure to pass the called function as the first argument also |
A different approach: the function always receives itself as the first argument, and when recursing, makes sure to pass the called function as the first argument also |
||
< |
<syntaxhighlight lang="python">>>> from functools import partial |
||
>>> Y = lambda f: partial(f, f) |
>>> Y = lambda f: partial(f, f) |
||
>>> fib = lambda f, n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(f, n-1) + f(f, n-2))) |
>>> fib = lambda f, n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(f, n-1) + f(f, n-2))) |
||
>>> [ Y(fib)(i) for i in range(-2, 10) ] |
>>> [ Y(fib)(i) for i in range(-2, 10) ] |
||
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</ |
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</syntaxhighlight> |
||
An interesting approach using introspection (from http://metapython.blogspot.com/2010/11/recursive-lambda-functions.html) |
An interesting approach using introspection (from http://metapython.blogspot.com/2010/11/recursive-lambda-functions.html) |
||
< |
<syntaxhighlight lang="python"> |
||
>>> from inspect import currentframe |
>>> from inspect import currentframe |
||
>>> from types import FunctionType |
>>> from types import FunctionType |
||
Line 1,525: | Line 2,682: | ||
>>> print "factorial(5) =", |
>>> print "factorial(5) =", |
||
>>> print (lambda n:1 if n<=1 else n*myself(n-1)) ( 5 ) |
>>> print (lambda n:1 if n<=1 else n*myself(n-1)) ( 5 ) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Another way of implementing the "Y" function is given in this post: https://stackoverflow.com/questions/481692/can-a-lambda-function-call-itself-recursively-in-python. The main problem to solve is that the function "fib" can't call itself. Therefore, the function "Y" is used to help "fib" call itself. |
|||
<syntaxhighlight lang="python"> |
|||
>>> Y = lambda f: lambda n: f(f,n) |
|||
>>> fib = lambda f, n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(f,n-1) + f(f,n-2))) #same as the first three implementations |
|||
>>> [ Y(fib)(i) for i in range(-2, 10) ] |
|||
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34] |
|||
</syntaxhighlight> |
|||
All in one line: |
|||
<syntaxhighlight lang="python"> |
|||
>>> fib_func = (lambda f: lambda n: f(f,n))(lambda f, n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(f,n-1) + f(f,n-2)))) |
|||
>>> [ fib_func(i) for i in range(-2, 10) ] |
|||
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34] |
|||
</syntaxhighlight> |
|||
=={{header|QBasic}}== |
|||
{{works with|QBasic}} |
|||
{{trans|BASIC256}} |
|||
<syntaxhighlight lang="qbasic">DECLARE FUNCTION Fibonacci! (num!) |
|||
PRINT Fibonacci(20) |
|||
PRINT Fibonacci(30) |
|||
PRINT Fibonacci(-10) |
|||
PRINT Fibonacci(10) |
|||
END |
|||
FUNCTION Fibonacci (num) |
|||
IF num < 0 THEN |
|||
PRINT "Invalid argument: "; |
|||
Fibonacci = num |
|||
END IF |
|||
IF num < 2 THEN |
|||
Fibonacci = num |
|||
ELSE |
|||
Fibonacci = Fibonacci(num - 1) + Fibonacci(num - 2) |
|||
END IF |
|||
END FUNCTION</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Igual que la entrada de BASIC256. |
|||
</pre> |
|||
=={{header|Qi}}== |
=={{header|Qi}}== |
||
Line 1,534: | Line 2,737: | ||
However, it can be done, for instance like this: |
However, it can be done, for instance like this: |
||
<syntaxhighlight lang="qi"> |
|||
<lang Qi> |
|||
(define fib |
(define fib |
||
N -> (let A (/. A N |
N -> (let A (/. A N |
||
Line 1,542: | Line 2,745: | ||
(A A (- N 1))))) |
(A A (- N 1))))) |
||
(A A N))) |
(A A N))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Quackery}}== |
|||
Quackery can do anonymous recursion via the word <code>recurse</code>. |
|||
<pre>[ dup 0 < iff |
|||
$ "negative argument passed to fibonacci" |
|||
fail |
|||
[ dup 2 < if done |
|||
dup 1 - recurse |
|||
swap 2 - recurse + ] ] is fibonacci ( n --> n )</pre> |
|||
<code>recurse</code> causes the current nest (i.e. the on that starts <code>[ dup</code> and ends <code>+ ]</code> to be evaluated recursively. This means that if, for example, the first recursive call was inside one or more nested nests, it would not work as desired. So the first instance of <code>recurse</code> in: |
|||
<pre>( *** faulty code *** ) |
|||
[ dup 0 < iff |
|||
$ "negative argument passed to fibonacci" |
|||
fail |
|||
[ dup 2 < if done |
|||
[ [ [ [ [ [ |
|||
[ dup 1 - recurse ] |
|||
] ] ] ] ] ] |
|||
swap 2 - recurse + ] ] is fibonacci ( n --> n )</pre> |
|||
would cause the nest <code>[ dup 1 - recurse ]</code>to be evaluated, and the program would go into a tailspin, recursively evaluating that nest until the return stack overflowed. |
|||
This limitation can be overcome with the understanding that recursion can be factored out into two ideas, i.e. self-reference and evaluation. The self-reference word in Quackery is <code>this</code>, which puts a pointer to the current nest on the data stack (usually just called "the stack") and the evaluation word is <code>do</code>, which takes an item from the stack and evaluates it. So <code>this do</code> is equivalent to <code>recurse</code>. |
|||
The final example fixes the previous example by using <code>this</code> and <code>do</code> to put the pointer to the current nest on the stack at the correct level of nesting and evaluate it within the nested nests. See also [http://rosettacode.org/wiki/Even_or_odd#Quackery:_With_Anonymous_Mutual_Recursion Even or Odd#Quackery: With Anonymous Mutual recursion]. |
|||
<pre>[ dup 0 < iff |
|||
$ "negative argument passed to fibonacci" |
|||
fail |
|||
[ dup 2 < if done |
|||
this |
|||
[ [ [ [ [ [ |
|||
[ dip [ dup 1 - ] do ] |
|||
] ] ] ] ] ] |
|||
swap 2 - recurse + ] ] is fibonacci ( n --> n ) |
|||
</pre> |
|||
Quackery also provides named recursion with <code>forward</code> and <code>resolves</code>, so this is usually not ''necessary'' but can be useful in unusual circumstances. |
|||
=={{header|R}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="r">fib2 <- function(n) { |
||
(n >= 0) || stop("bad argument") |
(n >= 0) || stop("bad argument") |
||
( function(n) if (n <= 1) 1 else Recall(n-1)+Recall(n-2) )(n) |
( function(n) if (n <= 1) 1 else Recall(n-1)+Recall(n-2) )(n) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
Line 1,555: | Line 2,800: | ||
In Racket, local helper function definitions inside of a function are only visible locally and do not pollute the module or global scope. |
In Racket, local helper function definitions inside of a function are only visible locally and do not pollute the module or global scope. |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
Line 1,574: | Line 2,819: | ||
(check-equal? (fact 0) 1) |
(check-equal? (fact 0) 1) |
||
(check-equal? (fact 5) 120)) |
(check-equal? (fact 5) 120)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
This calculates the slightly more complex Fibonacci funciton: |
This calculates the slightly more complex Fibonacci funciton: |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
;; Natural -> Natural |
;; Natural -> Natural |
||
Line 1,598: | Line 2,843: | ||
'(0 1 1 2 3 5 8 13 21 34 55 89 144 233 |
'(0 1 1 2 3 5 8 13 21 34 55 89 144 233 |
||
377 610 987 1597 2584 4181 6765))) |
377 610 987 1597 2584 4181 6765))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Also with the help of first-class functions in Racket, anonymous recursion can be implemented using fixed-points operators: |
Also with the help of first-class functions in Racket, anonymous recursion can be implemented using fixed-points operators: |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
;; We use Z combinator (applicative order fixed-point operator) |
;; We use Z combinator (applicative order fixed-point operator) |
||
Line 1,617: | Line 2,862: | ||
(+ (fibo (- n 1)) |
(+ (fibo (- n 1)) |
||
(fibo (- n 2)))))))) |
(fibo (- n 2)))))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
Line 1,627: | Line 2,872: | ||
55 |
55 |
||
</pre> |
</pre> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2015.12}} |
|||
In addition to the methods in the [[Perl]] entry above, and the Y-combinator described in [[Y_combinator]], you may also refer to an anonymous block or function from the inside: |
|||
<syntaxhighlight lang="raku" line>sub fib($n) { |
|||
die "Naughty fib" if $n < 0; |
|||
return { |
|||
$_ < 2 |
|||
?? $_ |
|||
!! &?BLOCK($_-1) + &?BLOCK($_-2); |
|||
}($n); |
|||
} |
|||
say fib(10);</syntaxhighlight> |
|||
However, using any of these methods is insane, when Raku provides a sort of inside-out combinator that lets you define lazy infinite constants, where the demand for a particular value is divorced from dependencies on more primitive values. This operator, known as the sequence operator, does in a sense provide anonymous recursion to a closure that refers to more primitive values. |
|||
<syntaxhighlight lang="raku" line>constant @fib = 0, 1, *+* ... *; |
|||
say @fib[10];</syntaxhighlight> |
|||
Here the closure, <tt>*+*</tt>, is just a quick way to write a lambda, <tt>-> $a, $b { $a + $b }</tt>. The sequence operator implicitly maps the two arguments to the -2nd and -1st elements of the sequence. So the sequence operator certainly applies an anonymous lambda, but whether it's recursion or not depends on whether you view a sequence as iteration or as simply a convenient way of memoizing a recursion. Either view is justifiable. |
|||
At this point someone may complain that the solution is doesn't fit the specified task because the sequence operator doesn't do the check for negative. True, but the sequence operator is not the whole of the solution; this check is supplied by the subscripting operator itself when you ask for <tt>@fib[-1]</tt>. Instead of scattering all kinds of arbitrary boundary conditions throughout your functions, the sequence operator maps them quite naturally to the boundary of definedness at the start of a list. |
|||
=={{header|REBOL}}== |
|||
<syntaxhighlight lang="rebol"> |
|||
fib: func [n /f][ do f: func [m] [ either m < 2 [m][(f m - 1) + f m - 2]] n] |
|||
</syntaxhighlight> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
[Modeled after the Fortran example.] |
[Modeled after the Fortran example.] |
||
<br><br>Since a hidden named function instead of an anonymous function seems |
<br><br>Since a hidden named function (instead of an anonymous function) seems |
||
to be OK with |
to be OK with the implementers, here are the REXX versions. |
||
===simplistic=== |
|||
<lang rexx>/*REXX program to show anonymous recursion (of a function/subroutine). */ |
|||
<syntaxhighlight lang="rexx">/*REXX program to show anonymous recursion (of a function or subroutine). */ |
|||
numeric digits 1e6 /*in case the user goes kaa-razy.*/ |
|||
numeric digits 1e6 /*in case the user goes ka-razy with X.*/ |
|||
parse arg x . /*obtain the optional argument from CL.*/ |
|||
if x=='' | x=="," then x= 12 /*Not specified? Then use the default.*/ |
|||
say 'fibonacci('j") =" fib(j) /*show Fibonacci sequence: 0──►x */ |
|||
w= length(x) /*W: used for formatting the output. */ |
|||
end /*j*/ |
|||
do j=0 for x+1 /*use the argument as an upper limit.*/ |
|||
say 'fibonacci('right(j, w)") =" fib(j) |
|||
/*──────────────────────────────────subroutines─────────────────────────*/ |
|||
end /*j*/ /* [↑] show Fibonacci sequence: 0 ──► X*/ |
|||
fib: procedure; if arg(1)>=0 then return .(arg(1)) |
|||
exit 0 /*stick a fork in it, we're all done. */ |
|||
say "***error!*** argument can't be negative."; exit |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
.:procedure; arg _; if _<2 then return _; return .(_-1)+.(_-2)</lang> |
|||
fib: procedure; parse arg z; if z>=0 then return .(z) |
|||
'''output''' when using the default input (<tt> 12 </tt>): |
|||
say "***error*** argument can't be negative."; exit |
|||
<pre style="overflow:scroll"> |
|||
.: procedure; parse arg #; if #<2 then return #; return .(#-1) + .(#-2)</syntaxhighlight> |
|||
fibonacci(0) = 0 |
|||
{{out|output|text= when using the input of: <tt> 12 </tt>}} |
|||
fibonacci(1) = 1 |
|||
<pre> |
|||
fibonacci(2) = 1 |
|||
fibonacci( |
fibonacci( 0) = 0 |
||
fibonacci( |
fibonacci( 1) = 1 |
||
fibonacci( |
fibonacci( 2) = 1 |
||
fibonacci( |
fibonacci( 3) = 2 |
||
fibonacci( |
fibonacci( 4) = 3 |
||
fibonacci( |
fibonacci( 5) = 5 |
||
fibonacci( |
fibonacci( 6) = 8 |
||
fibonacci( 7) = 13 |
|||
fibonacci( 8) = 21 |
|||
fibonacci( 9) = 34 |
|||
fibonacci(10) = 55 |
fibonacci(10) = 55 |
||
fibonacci(11) = 89 |
fibonacci(11) = 89 |
||
fibonacci(12) = 144 |
fibonacci(12) = 144 |
||
</pre> |
</pre> |
||
===memoization=== |
|||
Since the above REXX version is ''very'' slow for larger numbers, the following version was added that incorporates memoization. |
|||
<br>It's many orders of magnitude faster for larger values. |
|||
<syntaxhighlight lang="rexx">/*REXX program to show anonymous recursion of a function or subroutine with memoization.*/ |
|||
numeric digits 1e6 /*in case the user goes ka-razy with X.*/ |
|||
parse arg x . /*obtain the optional argument from CL.*/ |
|||
if x=='' | x=="," then x= 12 /*Not specified? Then use the default.*/ |
|||
@.= .; @.0= 0; @.1= 1 /*used to implement memoization for FIB*/ |
|||
w= length(x) /*W: used for formatting the output. */ |
|||
do j=0 for x+1 /*use the argument as an upper limit.*/ |
|||
say 'fibonacci('right(j, w)") =" fib(j) |
|||
end /*j*/ /* [↑] show Fibonacci sequence: 0 ──► X*/ |
|||
exit 0 /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
fib: procedure expose @.; arg z; if z>=0 then return .(z) |
|||
say "***error*** argument can't be negative."; exit |
|||
.: procedure expose @.; arg #; if @.#\==. then return @.#; @.#=.(#-1)+.(#-2); return @.#</syntaxhighlight> |
|||
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br> |
|||
=={{header|Ring}}== |
|||
<syntaxhighlight lang="ring"> |
|||
# Project : Anonymous recursion |
|||
t=0 |
|||
for x = -2 to 12 |
|||
n = x |
|||
recursion() |
|||
if x > -1 |
|||
see t + nl |
|||
ok |
|||
next |
|||
func recursion() |
|||
nold1=1 |
|||
nold2=0 |
|||
if n < 0 |
|||
see "positive argument required!" + nl |
|||
return |
|||
ok |
|||
if n=0 |
|||
t=nold2 |
|||
return t |
|||
ok |
|||
if n=1 |
|||
t=nold1 |
|||
return t |
|||
ok |
|||
while n |
|||
t=nold2+nold1 |
|||
if n>2 |
|||
n=n-1 |
|||
nold2=nold1 |
|||
nold1=t |
|||
loop |
|||
ok |
|||
return t |
|||
end |
|||
return t |
|||
</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
positive argument required! |
|||
positive argument required! |
|||
0 |
|||
1 |
|||
1 |
|||
2 |
|||
3 |
|||
5 |
|||
8 |
|||
13 |
|||
21 |
|||
34 |
|||
55 |
|||
89 |
|||
144 |
|||
</pre> |
|||
=={{header|RPL}}== |
|||
===Hidden variable=== |
|||
The recursive part of the function is stored in a local variable, which is made accessible to all the recursive instances by starting its name with the <code>←</code> character. |
|||
{{works with|HP|48G}} |
|||
≪ ≪ '''IF''' DUP 1 > '''THEN''' |
|||
DUP 1 - ←fib EVAL |
|||
SWAP 2 - ←fib EVAL + |
|||
'''END''' ≫ → ←fib |
|||
≪ '''IF''' DUP 0 < |
|||
'''THEN''' DROP "Negative value" DOERR |
|||
'''ELSE''' ←fib EVAL '''END''' |
|||
≫ ≫ '<span style="color:blue">FIBAR</span>' STO |
|||
-2 <span style="color:blue">FIBAR</span> |
|||
10 <span style="color:blue">FIBAR</span> |
|||
{{out}} |
|||
<pre> |
|||
1: 55 |
|||
</pre> |
|||
===Truly anonymous=== |
|||
Both the recursive block and the argument are pushed onto the stack, without any naming. This meets the requirements of the task perfectly and works on any RPL machine, but it is far from idiomatic and uses a lot of stack space. |
|||
{{works with|HP|28}} |
|||
≪ '''IF''' DUP 0 < |
|||
'''THEN''' DROP "Negative value" |
|||
'''ELSE''' |
|||
≪ '''IF''' DUP 1 > '''THEN''' |
|||
DUP2 1 - OVER EVAL |
|||
ROT ROT 2 - OVER EVAL + |
|||
'''ELSE''' SWAP DROP '''END''' |
|||
≫ |
|||
SWAP OVER EVAL |
|||
'''END''' |
|||
≫ '<span style="color:blue">FIBAR</span>' STO |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Line 1,665: | Line 3,053: | ||
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. |
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=== |
===Ruby with local variable=== |
||
< |
<syntaxhighlight lang="ruby">def fib(n) |
||
raise RangeError, "fib of negative" if n < 0 |
raise RangeError, "fib of negative" if n < 0 |
||
(fib2 = proc { |m| m < 2 ? m : fib2[m - 1] + fib2[m - 2] })[n] |
(fib2 = proc { |m| m < 2 ? m : fib2[m - 1] + fib2[m - 2] })[n] |
||
end</ |
end</syntaxhighlight> |
||
< |
<syntaxhighlight 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]</ |
=> [:error, :error, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]</syntaxhighlight> |
||
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. |
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. |
||
Line 1,679: | Line 3,067: | ||
'''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. |
'''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. |
||
< |
<syntaxhighlight lang="ruby">def fib(n) |
||
raise RangeError, "fib of negative" if n < 0 |
raise RangeError, "fib of negative" if n < 0 |
||
(fib2 = proc { |n| n < 2 ? n : fib2[n - 1] + fib2[n - 2] })[n] |
(fib2 = proc { |n| n < 2 ? n : fib2[n - 1] + fib2[n - 2] })[n] |
||
end</ |
end</syntaxhighlight> |
||
< |
<syntaxhighlight lang="ruby"># Ruby 1.9 |
||
(-2..12).map { |i| fib i rescue :error } |
(-2..12).map { |i| fib i rescue :error } |
||
=> [:error, :error, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144] |
=> [:error, :error, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144] |
||
Line 1,689: | Line 3,077: | ||
# Ruby 1.8 |
# Ruby 1.8 |
||
(-2..12).map { |i| fib i rescue :error } |
(-2..12).map { |i| fib i rescue :error } |
||
=> [:error, :error, 0, 1, 0, -3, -8, -15, -24, -35, -48, -63, -80, -99, -120]</ |
=> [:error, :error, 0, 1, 0, -3, -8, -15, -24, -35, -48, -63, -80, -99, -120]</syntaxhighlight> |
||
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 <tt>fib2[n - 1]</tt> changes the value of 'n', and <tt>fib2[n - 2]</tt> uses the wrong value of 'n', thus the wrong answer. |
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 <tt>fib2[n - 1]</tt> changes the value of 'n', and <tt>fib2[n - 2]</tt> uses the wrong value of 'n', thus the wrong answer. |
||
===Ruby with Hash=== |
===Ruby with Hash=== |
||
< |
<syntaxhighlight lang="ruby">def fib(n) |
||
raise RangeError, "fib of negative" if n < 0 |
raise RangeError, "fib of negative" if n < 0 |
||
Hash.new { |fib2, m| |
Hash.new { |fib2, m| |
||
fib2[m] = (m < 2 ? m : fib2[m - 1] + fib2[m - 2]) }[n] |
fib2[m] = (m < 2 ? m : fib2[m - 1] + fib2[m - 2]) }[n] |
||
end</ |
end</syntaxhighlight> |
||
This uses a Hash to memoize the recursion. After <tt>fib2[m - 1]</tt> returns, <tt>fib2[m - 2]</tt> uses the value in the Hash, without redoing the calculations. |
This uses a Hash to memoize the recursion. After <tt>fib2[m - 1]</tt> returns, <tt>fib2[m - 2]</tt> uses the value in the Hash, without redoing the calculations. |
||
Line 1,704: | Line 3,092: | ||
{{trans|PicoLisp}} |
{{trans|PicoLisp}} |
||
{{libheader|continuation}} |
{{libheader|continuation}} |
||
< |
<syntaxhighlight lang="ruby">require 'continuation' unless defined? Continuation |
||
module Kernel |
module Kernel |
||
Line 1,723: | Line 3,111: | ||
raise RangeError, "fib of negative" if n < 0 |
raise RangeError, "fib of negative" if n < 0 |
||
recur(n) { |m| m < 2 ? m : (recurse m - 1) + (recurse m - 2) } |
recur(n) { |m| m < 2 ? m : (recurse m - 1) + (recurse m - 2) } |
||
end</ |
end</syntaxhighlight> |
||
Our recursive block now lives in the 'block' variable of the Kernel#recur method. |
Our recursive block now lives in the 'block' variable of the Kernel#recur method. |
||
Line 1,732: | Line 3,120: | ||
{{trans|JavaScript}} |
{{trans|JavaScript}} |
||
{{libheader|continuation}} |
{{libheader|continuation}} |
||
< |
<syntaxhighlight lang="ruby">require 'continuation' unless defined? Continuation |
||
module Kernel |
module Kernel |
||
Line 1,763: | Line 3,151: | ||
end |
end |
||
}[n] |
}[n] |
||
end</ |
end</syntaxhighlight> |
||
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'. |
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'. |
||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust">fn fib(n: i64) -> Option<i64> { |
|||
// A function declared inside another function does not pollute the outer namespace. |
|||
fn actual_fib(n: i64) -> i64 { |
|||
if n < 2 { |
|||
n |
|||
} else { |
|||
actual_fib(n - 1) + actual_fib(n - 2) |
|||
} |
|||
} |
|||
if n < 0 { |
|||
None |
|||
} else { |
|||
Some(actual_fib(n)) |
|||
} |
|||
} |
|||
fn main() { |
|||
println!("Fib(-1) = {:?}", fib(-1)); |
|||
println!("Fib(0) = {:?}", fib(0)); |
|||
println!("Fib(1) = {:?}", fib(1)); |
|||
println!("Fib(2) = {:?}", fib(2)); |
|||
println!("Fib(3) = {:?}", fib(3)); |
|||
println!("Fib(4) = {:?}", fib(4)); |
|||
println!("Fib(5) = {:?}", fib(5)); |
|||
println!("Fib(10) = {:?}", fib(10)); |
|||
} |
|||
#[test] |
|||
fn test_fib() { |
|||
assert_eq!(fib(0).unwrap(), 0); |
|||
assert_eq!(fib(1).unwrap(), 1); |
|||
assert_eq!(fib(2).unwrap(), 1); |
|||
assert_eq!(fib(3).unwrap(), 2); |
|||
assert_eq!(fib(4).unwrap(), 3); |
|||
assert_eq!(fib(5).unwrap(), 5); |
|||
assert_eq!(fib(10).unwrap(), 55); |
|||
} |
|||
#[test] |
|||
fn test_invalid_argument() { |
|||
assert_eq!(fib(-1), None); |
|||
}</syntaxhighlight> |
|||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
Using a Y-combinator: |
Using a Y-combinator: |
||
< |
<syntaxhighlight lang="scala">def Y[A, B](f: (A ⇒ B) ⇒ (A ⇒ B)): A ⇒ B = f(Y(f))(_) |
||
def fib(n: Int): Option[Int] = |
def fib(n: Int): Option[Int] = |
||
Line 1,776: | Line 3,209: | ||
else f(i - 1) + f(i - 2))(n)) |
else f(i - 1) + f(i - 2))(n)) |
||
-2 to 5 map (n ⇒ (n, fib(n))) foreach println</ |
-2 to 5 map (n ⇒ (n, fib(n))) foreach println</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,791: | Line 3,224: | ||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
This uses named let to create a function (aux) that only exists inside of fibonacci: |
This uses named let to create a function (aux) that only exists inside of fibonacci: |
||
< |
<syntaxhighlight lang="scheme">(define (fibonacci n) |
||
(if (> 0 n) |
(if (> 0 n) |
||
"Error: argument must not be negative." |
"Error: argument must not be negative." |
||
Line 1,799: | Line 3,232: | ||
(aux (+ a b) a (- count 1)))))) |
(aux (+ a b) a (- count 1)))))) |
||
(map fibonacci '(1 2 3 4 5 6 7 8 9 10))</ |
(map fibonacci '(1 2 3 4 5 6 7 8 9 10))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>'(1 1 2 3 5 8 13 21 34 55)</pre> |
<pre>'(1 1 2 3 5 8 13 21 34 55)</pre> |
||
Line 1,805: | Line 3,238: | ||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
Uses a local function to do the dirty work. The local function has a name, but it is not in the global namespace. |
Uses a local function to do the dirty work. The local function has a name, but it is not in the global namespace. |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const func integer: fib (in integer: x) is func |
const func integer: fib (in integer: x) is func |
||
Line 1,836: | Line 3,269: | ||
writeln(fib(i)); |
writeln(fib(i)); |
||
end for; |
end for; |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,849: | Line 3,282: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
__FUNC__ refers to the current function. |
__FUNC__ refers to the current function. |
||
<syntaxhighlight lang="ruby">func fib(n) { |
|||
<lang ruby>{ |i| |
|||
return NaN if (n < 0) |
|||
func (n) { |
func (n) { |
||
if (n < 0) { return }; |
|||
n < 2 ? n |
n < 2 ? n |
||
: (__FUNC__(n- |
: (__FUNC__(n-1) + __FUNC__(n-2)) |
||
}( |
}(n) |
||
}</syntaxhighlight> |
|||
} * 10;</lang> |
|||
__BLOCK__ refers to the current block. |
__BLOCK__ refers to the current block. |
||
<syntaxhighlight lang="ruby">func fib(n) { |
|||
<lang ruby>{ |i| |
|||
return NaN if (n < 0) |
|||
if (n < 0) { return }; |
|||
{|n| |
|||
n < 2 ? n |
n < 2 ? n |
||
: (__BLOCK__(n- |
: (__BLOCK__(n-1) + __BLOCK__(n-2)) |
||
}( |
}(n) |
||
}</syntaxhighlight> |
|||
} * 10;</lang> |
|||
=={{header|Smalltalk}}== |
|||
In Smalltalk, things are referred to by a name, so the following may not fully qualify as solutions. |
|||
<br>Also: doing things like this is not considered "good style" (''give things a good name to make the meaning obvious''). |
|||
Notice, that none of the two solutions below ''pollutes any namespace''; |
|||
in (a), the variable introduced is strictly local to the method, in (b) not even a method-local is introduced (so maybe (b) does qualify, after all). |
|||
a) Use a funny local name (in this case: "_"). |
|||
Here the closure is defined as "_", and then evaluated (by sending it a <tt>value:</tt> message). |
|||
<syntaxhighlight lang="smalltalk"> |
|||
myMethodComputingFib:arg |
|||
|_| |
|||
^ (_ := [:n | n <= 1 |
|||
ifTrue:[n] |
|||
ifFalse:[(_ value:(n - 1))+(_ value:(n - 2))]] |
|||
) value:arg.</syntaxhighlight> |
|||
b) Define it in a local scope to not infect the outer scopes. |
|||
<br>Here, a separate closure is defined (and evaluated with <tt>value</tt>), in which fib is defined and evaluated with the argument. |
|||
This is semantically equivalent to the named let solution of Scheme. |
|||
<syntaxhighlight lang="smalltalk"> |
|||
myMethodComputingFib2:arg |
|||
^ [ |
|||
|fib| |
|||
[:n | n <= 1 |
|||
ifTrue:[1] |
|||
ifFalse:[(fib value:(n - 1))+(fun value:(n - 2))]] value:arg. |
|||
] value.</syntaxhighlight> |
|||
To completely make it anonymous, we could use reflection to get at the current executed block (via thisContext), |
|||
but that is too ugly and obfuscating to be shown here. |
|||
=={{header|Sparkling}}== |
|||
As a function expression: |
|||
<syntaxhighlight lang="sparkling">function(n, f) { |
|||
return f(n, f); |
|||
}(10, function(n, f) { |
|||
return n < 2 ? 1 : f(n - 1, f) + f(n - 2, f); |
|||
}) |
|||
</syntaxhighlight> |
|||
When typed into the REPL: |
|||
<syntaxhighlight lang="sparkling">spn:1> function(n, f) { return f(n, f); }(10, function(n, f) { return n < 2 ? 1 : f(n - 1, f) + f(n - 2, f); }) |
|||
= 89</syntaxhighlight> |
|||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
ML does not have a built-in construct for anonymous recursion, but you can easily write your own fix-point combinator: |
ML does not have a built-in construct for anonymous recursion, but you can easily write your own fix-point combinator: |
||
< |
<syntaxhighlight lang="sml">fun fix f x = f (fix f) x |
||
fun fib n = |
fun fib n = |
||
Line 1,877: | Line 3,357: | ||
(fn 0 => 0 |
(fn 0 => 0 |
||
| 1 => 1 |
| 1 => 1 |
||
| n => fib (n-1) + fib (n-2))) n</ |
| n => fib (n-1) + fib (n-2))) n</syntaxhighlight> |
||
Instead of using a fix-point, the more common approach is to locally define a recursive function and call it once: |
Instead of using a fix-point, the more common approach is to locally define a recursive function and call it once: |
||
< |
<syntaxhighlight lang="sml">fun fib n = |
||
let |
let |
||
fun fib 0 = 0 |
fun fib 0 = 0 |
||
Line 1,890: | Line 3,370: | ||
else |
else |
||
fib n |
fib n |
||
end</ |
end</syntaxhighlight> |
||
In this example the local function has the same name as the outer function. This is fine: the local definition shadows |
In this example the local function has the same name as the outer function. This is fine: the local definition shadows |
||
Line 1,896: | Line 3,376: | ||
Another variation is possible. Instead, we could define the recursive "fib" at top-level, then shadow it with a non-recursive wrapper. To force the wrapper to be non-recursive, we use the "val" syntax instead of "fun": |
Another variation is possible. Instead, we could define the recursive "fib" at top-level, then shadow it with a non-recursive wrapper. To force the wrapper to be non-recursive, we use the "val" syntax instead of "fun": |
||
< |
<syntaxhighlight lang="sml">fun fib 0 = 0 |
||
| fib 1 = 1 |
| fib 1 = 1 |
||
| fib n = fib (n-1) + fib (n-2) |
| fib n = fib (n-1) + fib (n-2) |
||
val fib = fn n => if n < 0 then raise Fail "Negative" |
val fib = fn n => if n < 0 then raise Fail "Negative" |
||
else fib n</ |
else fib n</syntaxhighlight> |
||
=={{header|SuperCollider}}== |
|||
SuperCollider has a keyword "thisFunction", which refers to the current function context. The example below uses this for anonymous recursion. One may think that "thisFunction" would refer to the second branch of the if statement, but because if statements are inlined, the function is the outer one. |
|||
<syntaxhighlight lang="supercollider"> |
|||
( |
|||
f = { |n| |
|||
if(n >= 0) { |
|||
if(n < 2) { n } { thisFunction.(n-1) + thisFunction.(n-2) } |
|||
} |
|||
}; |
|||
(0..20).collect(f) |
|||
) |
|||
</syntaxhighlight> |
|||
=={{header|Swift}}== |
|||
;With internal named recursive closure: |
|||
{{works with|Swift|2.x}} |
|||
<syntaxhighlight lang="swift">let fib: Int -> Int = { |
|||
func f(n: Int) -> Int { |
|||
assert(n >= 0, "fib: no negative numbers") |
|||
return n < 2 ? 1 : f(n-1) + f(n-2) |
|||
} |
|||
return f |
|||
}() |
|||
print(fib(8))</syntaxhighlight> |
|||
{{works with|Swift|1.x}} |
|||
<syntaxhighlight lang="swift">let fib: Int -> Int = { |
|||
var f: (Int -> Int)! |
|||
f = { n in |
|||
assert(n >= 0, "fib: no negative numbers") |
|||
return n < 2 ? 1 : f(n-1) + f(n-2) |
|||
} |
|||
return f |
|||
}() |
|||
println(fib(8))</syntaxhighlight> |
|||
;Using Y combinator: |
|||
<syntaxhighlight lang="swift">struct RecursiveFunc<F> { |
|||
let o : RecursiveFunc<F> -> F |
|||
} |
|||
func y<A, B>(f: (A -> B) -> A -> B) -> A -> B { |
|||
let r = RecursiveFunc<A -> B> { w in f { w.o(w)($0) } } |
|||
return r.o(r) |
|||
} |
|||
func fib(n: Int) -> Int { |
|||
assert(n >= 0, "fib: no negative numbers") |
|||
return y {f in {n in n < 2 ? 1 : f(n-1) + f(n-2)}} (n) |
|||
} |
|||
println(fib(8))</syntaxhighlight> |
|||
=={{header|Tailspin}}== |
|||
See the actual fibonacci solution [[Fibonacci_sequence#State_machine]] |
|||
=={{header|Tcl}}== |
=={{header|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 <code>apply</code> command. |
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 <code>apply</code> command. |
||
< |
<syntaxhighlight lang="tcl">proc fib n { |
||
# sanity checks |
# sanity checks |
||
if {[incr n 0] < 0} {error "argument may not be negative"} |
if {[incr n 0] < 0} {error "argument may not be negative"} |
||
Line 1,914: | Line 3,453: | ||
expr {[apply $f [incr x -1]] + [apply $f [incr x -1]]} |
expr {[apply $f [incr x -1]] + [apply $f [incr x -1]]} |
||
}} $n |
}} $n |
||
}</ |
}</syntaxhighlight> |
||
Demonstrating: |
Demonstrating: |
||
<lang |
<syntaxhighlight lang="tcl">puts [fib 12]</syntaxhighlight> |
||
{{out}}} |
{{out}}} |
||
<pre>144</pre> |
<pre>144</pre> |
||
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: |
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: |
||
< |
<syntaxhighlight lang="tcl">proc fib n { |
||
if {[incr n 0] < 0} {error "argument may not be negative"} |
if {[incr n 0] < 0} {error "argument may not be negative"} |
||
apply {x {expr { |
apply {x {expr { |
||
Line 1,928: | Line 3,467: | ||
+ [apply [lindex [info level 0] 1] [incr x -1]] |
+ [apply [lindex [info level 0] 1] [incr x -1]] |
||
}}} $n |
}}} $n |
||
}</ |
}</syntaxhighlight> |
||
However, we can create a <code>recurse</code> function that makes this much more straight-forward: |
However, we can create a <code>recurse</code> function that makes this much more straight-forward: |
||
< |
<syntaxhighlight 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 tcl::mathfunc::recurse args {apply [lindex [info level -1] 1] {*}$args} |
||
proc fib n { |
proc fib n { |
||
Line 1,937: | Line 3,476: | ||
$x < 2 ? $x : recurse([incr x -1]) + recurse([incr x -1]) |
$x < 2 ? $x : recurse([incr x -1]) + recurse([incr x -1]) |
||
}}} $n |
}}} $n |
||
}</ |
}</syntaxhighlight> |
||
=={{header|True BASIC}}== |
|||
{{trans|BASIC256}} |
|||
{{works with|QBasic}} |
|||
<syntaxhighlight lang="qbasic">FUNCTION Fibonacci (num) |
|||
IF num < 0 THEN |
|||
PRINT "Invalid argument: "; |
|||
LET Fibonacci = num |
|||
END IF |
|||
IF num < 2 THEN |
|||
LET Fibonacci = num |
|||
ELSE |
|||
LET Fibonacci = Fibonacci(num - 1) + Fibonacci(num - 2) |
|||
END IF |
|||
END FUNCTION |
|||
PRINT Fibonacci(20) |
|||
PRINT Fibonacci(30) |
|||
PRINT Fibonacci(-10) |
|||
PRINT Fibonacci(10) |
|||
END</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Igual que la entrada de BASIC256. |
|||
</pre> |
|||
=={{header|TXR}}== |
|||
For the Y combinator approach in TXR, see the Y combinator task. |
|||
The following easy transliteration of one of the Common Lisp solutions shows the conceptual and cultural compatibility between TXR Lisp macros and CL macros: |
|||
{{trans|Common_Lisp}} |
|||
<syntaxhighlight lang="txrlisp">(defmacro recursive ((. parm-init-pairs) . body) |
|||
(let ((hidden-name (gensym "RECURSIVE-"))) |
|||
^(macrolet ((recurse (. args) ^(,',hidden-name ,*args))) |
|||
(labels ((,hidden-name (,*[mapcar first parm-init-pairs]) ,*body)) |
|||
(,hidden-name ,*[mapcar second parm-init-pairs]))))) |
|||
(defun fib (number) |
|||
(if (< number 0) |
|||
(error "Error. The number entered: ~a is negative" number) |
|||
(recursive ((n number) (a 0) (b 1)) |
|||
(if (= n 0) |
|||
a |
|||
(recurse (- n 1) b (+ a b)))))) |
|||
(put-line `fib(10) = @(fib 10)`) |
|||
(put-line `fib(-1) = @(fib -1)`))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>$ txr anonymous-recursion.txr |
|||
fib(10) = 55 |
|||
txr: unhandled exception of type error: |
|||
txr: possibly triggered by anonymous-recursion.txr:9 |
|||
txr: Error. The number entered: -1 is negative |
|||
Aborted (core dumped)</pre> |
|||
=={{header|UNIX Shell}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="bash">fib() { |
||
if test 0 -gt "$1"; then |
if test 0 -gt "$1"; then |
||
echo "fib: fib of negative" 1>&2 |
echo "fib: fib of negative" 1>&2 |
||
Line 1,957: | Line 3,557: | ||
) |
) |
||
fi |
fi |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="bash">$ for i in -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12; do |
||
> fib $i |
> fib $i |
||
> done |
> done |
||
Line 1,975: | Line 3,575: | ||
55 |
55 |
||
89 |
89 |
||
144</ |
144</syntaxhighlight> |
||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
< |
<syntaxhighlight lang="ursala">#import nat |
||
fib = |
fib = |
||
Line 1,990: | Line 3,590: | ||
predecessor^~( # with the respective predecessors of |
predecessor^~( # with the respective predecessors of |
||
~&, # the given argument |
~&, # the given argument |
||
predecessor)))) # and the predecessor thereof</ |
predecessor)))) # and the predecessor thereof</syntaxhighlight> |
||
Anonymous recursion is often achieved using the recursive conditional operator, <code>( _ )^?( _ , _ )</code>, 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 <code>^?<</code> 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. |
Anonymous recursion is often achieved using the recursive conditional operator, <code>( _ )^?( _ , _ )</code>, 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 <code>^?<</code> 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 <code>^?</code> differs from the ordinary conditional <code>?</code> seen at the outermost level by arranging for its predicate and component functions to be given an input of the form <math>(f,a)</math> where <math>a</math> is the original argument, and <math>f</math> 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 <code>W</code> seen above. |
The recursive conditional operator <code>^?</code> differs from the ordinary conditional <code>?</code> seen at the outermost level by arranging for its predicate and component functions to be given an input of the form <math>(f,a)</math> where <math>a</math> is the original argument, and <math>f</math> 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 <code>W</code> seen above. |
||
=={{header|UTFool}}== |
|||
'''Solution with anonymous class''' |
|||
<syntaxhighlight lang="utfool"> |
|||
··· |
|||
http://rosettacode.org/wiki/Anonymous_recursion |
|||
··· |
|||
⟦import java.util.function.UnaryOperator;⟧ |
|||
■ AnonymousRecursion |
|||
§ static |
|||
▶ main |
|||
• args⦂ String[] |
|||
if 0 > Integer.valueOf args[0] |
|||
System.out.println "negative argument" |
|||
else |
|||
System.out.println *UnaryOperator⟨Integer⟩° ■ |
|||
▶ apply⦂ Integer |
|||
• n⦂ Integer |
|||
⏎ n ≤ 1 ? n ! (apply n - 1) + (apply n - 2) |
|||
°.apply Integer.valueOf args[0] |
|||
</syntaxhighlight> |
|||
=={{header|VBA}}== |
|||
<syntaxhighlight lang="vb"> |
|||
Sub Main() |
|||
Debug.Print F(-10) |
|||
Debug.Print F(10) |
|||
End Sub |
|||
Private Function F(N As Long) As Variant |
|||
If N < 0 Then |
|||
F = "Error. Negative argument" |
|||
ElseIf N <= 1 Then |
|||
F = N |
|||
Else |
|||
F = F(N - 1) + F(N - 2) |
|||
End If |
|||
End Function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Error. Negative argument |
|||
55</pre> |
|||
=={{header|Wart}}== |
=={{header|Wart}}== |
||
< |
<syntaxhighlight lang="wart">def (fib n) |
||
if (n >= 0) |
if (n >= 0) |
||
(transform n :thru (afn (n) |
(transform n :thru (afn (n) |
||
Line 2,002: | Line 3,646: | ||
n |
n |
||
(+ (self n-1) |
(+ (self n-1) |
||
(self n-2)))))</ |
(self n-2)))))</syntaxhighlight> |
||
<code>afn</code> creates an anonymous function that can be recursed by calling <code>self</code>. |
<code>afn</code> creates an anonymous function that can be recursed by calling <code>self</code>. |
||
=={{header|WDTE}}== |
|||
<syntaxhighlight lang="wdte">let str => 'strings'; |
|||
let fib n => switch n { |
|||
< 0 => str.format 'Bad argument: {q}' n; |
|||
default => n -> (@ memo s n => switch n { |
|||
== 0 => 0; == 1 => 1; |
|||
default => + (s (- n 1)) (s (- n 2)); |
|||
}); |
|||
};</syntaxhighlight> |
|||
In WDTE, a lambda, defined in a block delineated by <code>(@)</code>, gets passed itself as its first argument, allowing for recursion. |
|||
=={{header|Wren}}== |
|||
<syntaxhighlight lang="wren">class Fibonacci { |
|||
static compute(n) { |
|||
var fib |
|||
fib = Fn.new {|n| |
|||
if (n < 2) return n |
|||
return fib.call(n - 1) + fib.call(n - 2) |
|||
} |
|||
if (n < 0) return null |
|||
return fib.call(n) |
|||
} |
|||
} |
|||
System.print(Fibonacci.compute(36))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
14930352 |
|||
</pre> |
|||
=={{header|x86 Assembly}}== |
|||
{{works with|NASM}} |
|||
{{works with|Linux}} |
|||
32 bit |
|||
Fakes the actual first call to the function that generates Fibonacci numbers. |
|||
The address of the instructions after the function get put on the stack and then execution continues into the actual function. |
|||
When the recursion is complete, instead of returning to the location of the call it goes to the end of the loop. |
|||
<syntaxhighlight lang="asm"> |
|||
; Calculates and prints Fibonacci numbers (Fn) |
|||
; Prints numbers 1 - 47 (largest 32bit Fn that fits) |
|||
; Build: |
|||
; nasm -felf32 fib.asm |
|||
; ld -m elf32_i386 fib.o -o fib |
|||
global _start |
|||
section .text |
|||
_start: |
|||
mov ecx, 48 ; Initialize loop counter |
|||
.loop: |
|||
mov ebx, 48 ; Calculate which Fn will be computed |
|||
sub ebx, ecx ; Takes into account the reversed nature |
|||
push ebx ; Pass the parameter in on the stack |
|||
push .done ; Emulate a call but "return" to end of loop |
|||
; The return adress is manually set on the stack |
|||
; int fib (int n) |
|||
; Returns the n'th Fn |
|||
; fib(n) = 0 if n <= 0 |
|||
; 1 if n == 1 |
|||
; fib(n-1) + fib(n-2) otherwise |
|||
.fib: |
|||
push ebp ; Setup stack frame |
|||
mov ebp, esp |
|||
push ebx ; Save needed registers |
|||
xor eax, eax |
|||
mov ebx, [ebp + 8] ; Get the parameter |
|||
cmp ebx, 1 ; Test for base cases |
|||
jl .return |
|||
mov eax, 1 |
|||
je .return |
|||
dec ebx ; Calculate fib(n-1) |
|||
push ebx |
|||
call .fib |
|||
mov [esp], eax ; Save result on top of parameter in stack |
|||
dec ebx ; Calculate fib(n-2) |
|||
push ebx |
|||
call .fib |
|||
add eax, [esp + 4] ; Add the first to the second |
|||
add esp, 8 ; Reset local stack |
|||
.return: |
|||
pop ebx ; Restore modified registers |
|||
mov esp, ebp ; Tear down stack frame and return |
|||
pop ebp |
|||
ret |
|||
.done: |
|||
mov [esp], ecx ; Save the counter between calls |
|||
push eax ; Print the number |
|||
call print_num |
|||
add esp, 4 |
|||
pop ecx ; Restore the loop counter |
|||
loop .loop ; Loop until 0 |
|||
mov eax, 0x01 ; sys_exit(int error) |
|||
xor ebx, ebx ; error = 0 (success) |
|||
int 0x80 ; syscall |
|||
; void print_num (int n) |
|||
; Prints an integer and newline |
|||
print_num: |
|||
push ebp |
|||
mov ebp, esp |
|||
sub esp, 11 ; Save space for digits and newline |
|||
lea ecx, [ebp - 1] ; Save a pointer to after the buffer |
|||
mov BYTE [ecx], 0x0A ; Set the newline at the end |
|||
mov eax, [ebp + 8] ; Get the parameter |
|||
mov ebx, DWORD 10 ; Divisor |
|||
.loop: |
|||
dec ecx ; Move pointer to next digit |
|||
xor edx, edx |
|||
div ebx ; Extract one digit, quot in eax, rem in edx |
|||
add dl, 0x30 ; Convert remainder to ascii |
|||
mov [ecx], dl ; Save the ascii form |
|||
cmp eax, 0 ; Loop until all digits have been converted |
|||
jg .loop |
|||
mov eax, 0x04 ; sys_write(int fd, char **buf, int len) |
|||
mov ebx, 1 ; stdout |
|||
mov edx, ebp ; Calculate the length |
|||
sub edx, ecx ; address after newline - address of first digit |
|||
int 0x80 |
|||
mov esp, ebp |
|||
pop ebp |
|||
ret |
|||
</syntaxhighlight> |
|||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
In XPL0 you can nest functions/procedures inside other |
In XPL0 you can nest functions/procedures inside other |
||
functions/procedures up to eight levels deep. |
functions/procedures up to eight levels deep. |
||
functions invisible to the outside, thus preventing namespace pollution. |
This makes those nested functions invisible to the outside, thus preventing namespace pollution. |
||
< |
<syntaxhighlight lang="xpl0">include c:\cxpl\codes; |
||
func Fib(X); |
func Fib(X); |
||
Line 2,027: | Line 3,804: | ||
[IntOut(0, Fib(8)); CrLf(0); |
[IntOut(0, Fib(8)); CrLf(0); |
||
IntOut(0, Fib(-2)); CrLf(0); |
IntOut(0, Fib(-2)); CrLf(0); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
21 |
21 |
||
Error 0 |
Error 0 |
||
</pre> |
</pre> |
||
=={{header|Yabasic}}== |
|||
{{trans|AutoIt}} |
|||
<syntaxhighlight lang="yabasic">print Fibonacci(-10) |
|||
print Fibonacci(10) |
|||
sub Fibonacci(number) |
|||
If number < 0 print "Invalid argument: "; : return number |
|||
If number < 2 Then |
|||
Return number |
|||
Else |
|||
Return Fibonacci(number - 1) + Fibonacci(number - 2) |
|||
EndIf |
|||
end sub</syntaxhighlight> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">fcn fib(n){ |
||
if (n<0) throw(Exception.ValueError); |
if (n<0) throw(Exception.ValueError); |
||
fcn(n){ |
fcn(n){ |
||
Line 2,045: | Line 3,840: | ||
fib(8) .println(); |
fib(8) .println(); |
||
fib(-8).println(); |
fib(-8).println(); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,051: | Line 3,846: | ||
ValueError thrown |
ValueError thrown |
||
</pre> |
</pre> |
||
=={{header|ZX Spectrum Basic}}== |
|||
{{trans|AutoHotkey}} |
|||
<syntaxhighlight lang="zxbasic">10 INPUT "Enter a number: ";n |
|||
20 LET t=0 |
|||
30 GO SUB 60 |
|||
40 PRINT t |
|||
50 STOP |
|||
60 LET nold1=1: LET nold2=0 |
|||
70 IF n<0 THEN PRINT "Positive argument required!": RETURN |
|||
80 IF n=0 THEN LET t=nold2: RETURN |
|||
90 IF n=1 THEN LET t=nold1: RETURN |
|||
100 LET t=nold2+nold1 |
|||
110 IF n>2 THEN LET n=n-1: LET nold2=nold1: LET nold1=t: GO SUB 100 |
|||
120 RETURN |
|||
</syntaxhighlight> |
|||
{{omit from|ACL2}} |
{{omit from|ACL2}} |
||
{{omit from|Euphoria}} |
{{omit from|Euphoria}} |
||
{{omit from|PureBasic}} |
{{omit from|PureBasic}} |
||
{{omit from|Stata}} |
Latest revision as of 12:09, 24 July 2024
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), causing unwanted side-effects, and/or the function doesn't have the right arguments and/or 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 some disadvantages:
- You have to think up a name, which then pollutes the namespace
- 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.
- Task
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.
- Related tasks
11l
F fib(n)
F f(Int n) -> Int
I n < 2
R n
R @f(n - 1) + @f(n - 2)
R f(n)
L(i) 0..20
print(fib(i), end' ‘ ’)
- Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
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.
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;
ALGOL 68
PROC fibonacci = ( INT x )INT:
IF x < 0
THEN
print( ( "negative parameter to fibonacci", newline ) );
stop
ELSE
PROC actual fibonacci = ( INT n )INT:
IF n < 2
THEN
n
ELSE
actual fibonacci( n - 1 ) + actual fibonacci( n - 2 )
FI;
actual fibonacci( x )
FI;
APL
APL has the symbol ∇
which calls the current function recursively.
Functions can be defined and then called in place without ever assigning them a name,
though they are not quite first-class objects (you can't have an array of functions for example).
fib←{ ⍝ Outer function
⍵<0:⎕SIGNAL 11 ⍝ DOMAIN ERROR if argument < 0
{ ⍝ Inner (anonymous) function
⍵<2:⍵
(∇⍵-1)+∇⍵-2 ⍝ ∇ = anonymous recursive call
}⍵ ⍝ Call function in place
}
AppleScript
on fibonacci(n) -- "Anonymous recursion" task.
-- For the sake of the task, a needlessly anonymous local script object containing a needlessly recursive handler.
-- The script could easily (and ideally should) be assigned to a local variable.
script
property one : 1
property sequence : {}
on f(n)
if (n < 2) then
set end of my sequence to 0
if (n is 1) then set end of my sequence to one
else
f(n - 1)
set end of my sequence to (item -2 of my sequence) + (end of my sequence)
end if
end f
end script
-- Don't insert any additional code here!
-- Sort out whether the input's positive or negative and tell the object generated above to do the recursive business.
tell result
if (n < 0) then
set its one to -1
set n to -n
end if
f(n)
return its sequence
end tell
end fibonacci
fibonacci(15) --> {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}
fibonacci(-15) --> {0, -1, -1, -2, -3, -5, -8, -13, -21, -34, -55, -89, -144, -233, -377, -610}
Or, as the recursion of an anonymous declarative function, enabled by the Y combinator:
------------ ANONYMOUS RECURSION WITH THE Y-COMBINATOR --------
on run
--------------------- FIBONACCI EXAMPLE -------------------
script
on |λ|(f)
script
on |λ|(n)
if 0 > n then return missing value
if 0 = n then return 0
if 1 = n then return 1
(f's |λ|(n - 2)) + (f's |λ|(n - 1))
end |λ|
end script
end |λ|
end script
unlines(map(showList, chunksOf(12, ¬
map(|Y|(result), enumFromTo(-2, 20)))))
end run
------------------------ Y COMBINATOR ----------------------
on |Y|(f)
script
on |λ|(y)
script
on |λ|(x)
y's |λ|(y)'s |λ|(x)
end |λ|
end script
f's |λ|(result)
end |λ|
end script
result's |λ|(result)
end |Y|
----------- GENERIC FUNCTIONS FOR TEST AND DISPLAY ---------
-- chunksOf :: Int -> [a] -> [[a]]
on chunksOf(k, xs)
script
on go(ys)
set ab to splitAt(k, ys)
set a to item 1 of ab
if {} ≠ a then
{a} & go(item 2 of ab)
else
a
end if
end go
end script
result's go(xs)
end chunksOf
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if n < m then
set d to -1
else
set d to 1
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end enumFromTo
-- intercalate :: String -> [String] -> String
on intercalate(delim, xs)
set {dlm, my text item delimiters} to ¬
{my text item delimiters, delim}
set s to xs as text
set my text item delimiters to dlm
s
end intercalate
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- showList :: [a] -> String
on showList(xs)
intercalate(", ", map(my str, xs))
end showList
-- splitAt :: Int -> [a] -> ([a], [a])
on splitAt(n, xs)
if n > 0 and n < length of xs then
if class of xs is text then
{items 1 thru n of xs as text, ¬
items (n + 1) thru -1 of xs as text}
else
{items 1 thru n of xs, items (n + 1) thru -1 of xs}
end if
else
if n < 1 then
{{}, xs}
else
{xs, {}}
end if
end if
end splitAt
-- str :: a -> String
on str(x)
x as string
end str
-- unlines :: [String] -> String
on unlines(xs)
-- A single string formed by the intercalation
-- of a list of strings with the newline character.
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set s to xs as text
set my text item delimiters to dlm
s
end unlines
- Output:
missing value, missing value, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
Arturo
fib: function [x][
; Using scoped function fibI inside fib
fibI: function [n][
(n<2)? -> n -> add fibI n-2 fibI n-1
]
if x < 0 -> panic "Invalid argument"
return fibI x
]
loop 0..4 'x [
print fib x
]
- Output:
0 1 1 2 3
AutoHotkey
Fib(n) {
nold1 := 1
nold2 := 0
If n < 0
{
MsgBox, Positive argument required!
Return
}
Else If n = 0
Return nold2
Else If n = 1
Return nold1
Fib_Label:
t := nold2+nold1
If n > 2
{
n--
nold2:=nold1
nold1:=t
GoSub Fib_Label
}
Return t
}
AutoIt
ConsoleWrite(Fibonacci(10) & @CRLF) ; ## USAGE EXAMPLE
ConsoleWrite(Fibonacci(20) & @CRLF) ; ## USAGE EXAMPLE
ConsoleWrite(Fibonacci(30)) ; ## USAGE EXAMPLE
Func Fibonacci($number)
If $number < 0 Then Return "Invalid argument" ; No negative numbers
If $number < 2 Then ; If $number equals 0 or 1
Return $number ; then return that $number
Else ; Else $number equals 2 or more
Return Fibonacci($number - 1) + Fibonacci($number - 2) ; FIBONACCI!
EndIf
EndFunc
- Output:
55 6765 832040
Axiom
Using the Aldor compiler in Axiom/Fricas:
#include "axiom"
Z ==> Integer;
fib(x:Z):Z == {
x <= 0 => error "argument outside of range";
f(n:Z,v1:Z,v2:Z):Z == if n<2 then v2 else f(n-1,v2,v1+v2);
f(x,1,1);
}
The old Axiom compiler has scope issues with calling a local function recursively. One solution is to use the Reference (pointer) domain and initialise the local function with a dummy value:
)abbrev package TESTP TestPackage
Z ==> Integer
TestPackage : with
fib : Z -> Z
== add
fib x ==
x <= 0 => error "argument outside of range"
f : Reference((Z,Z,Z) -> Z) := ref((n, v1, v2) +-> 0)
f() := (n, v1, v2) +-> if n<2 then v2 else f()(n-1,v2,v1+v2)
f()(x,1,1)
BASIC
BaCon
DEF FN fib(x) = FIB(x)
'============================
FUNCTION FIB(int n) TYPE int
'============================
IF n < 2 THEN
PRINT n
ELSE
n1 = 0
n2 = 1
FOR i = 1 TO n
sum = n1 + n2
n1 = n2
n2 = sum
NEXT
PRINT n1
END IF
END FUNCTION
'--- less than 2
FIB(0)
FIB(1)
'--- greater than or equal to 2
FIB(2)
FIB(3)
FIB(4)
FIB(5)
FIB(6)
FIB(7)
FIB(8)
FIB(9)
'--- using an alias
'fib(9)
BASIC256
print Fibonacci(20)
print Fibonacci(30)
print Fibonacci(-10)
print Fibonacci(10)
end
function Fibonacci(num)
if num < 0 then
print "Invalid argument: ";
return num
end if
if num < 2 then
return num
else
return Fibonacci(num - 1) + Fibonacci(num - 2)
end If
end function
- Output:
6765 832040 Invalid argument: -10 55
Chipmunk Basic
100 cls
110 sub fib(num)
120 if num < 0 then print "Invalid argument: "; : fib = num
130 if num < 2 then fib = num else fib = fib(num-1)+fib(num-2)
140 end sub
190 print fib(20)
200 print fib(30)
210 print fib(-10)
220 print fib(10)
230 end
- Output:
Same as BASIC256 entry.
BBC BASIC
This works by finding a pointer to the 'anonymous' function and calling it indirectly:
PRINT FNfib(10)
END
DEF FNfib(n%) IF n%<0 THEN ERROR 100, "Must not be negative"
LOCAL P% : P% = !384 + LEN$!384 + 4 : REM Function pointer
(n%) IF n%<2 THEN = n% ELSE = FN(^P%)(n%-1) + FN(^P%)(n%-2)
- Output:
55
IS-BASIC
100 PROGRAM "Fibonacc.bas"
110 FOR I=0 TO 10
120 PRINT FIB(I);
130 NEXT
140 DEF FIB(K)
150 SELECT CASE K
160 CASE IS<0
170 PRINT "Negative parameter to Fibonacci.":STOP
180 CASE 0,1
190 LET FIB=K
200 CASE ELSE
210 LET FIB=FIB(K-1)+FIB(K-2)
220 END SELECT
230 END DEF
Bracmat
lambda 'light'
The first solution uses macro substitution. In an expression headed by an apostrophe operator with an empty lhs all subexpressions headed by a dollar operator with empty lhs are replaced by the values that the rhs are bound to, without otherwise evaluating the expression. Example: if (x=7) & (y=4)
then '($x+3+$y)
becomes =7+3+4
. Notice that the solution below utilises no other names than arg
, the keyword that always denotes a function's argument. The test for negative or non-numeric arguments is outside the recursive part. The function fails if given negative input.
( (
=
. !arg:#:~<0
& ( (=.!arg$!arg)
$ (
=
.
' (
. !arg:<2
| (($arg)$($arg))$(!arg+-2)
+ (($arg)$($arg))$(!arg+-1)
)
)
)
$ !arg
)
$ 30
)
Answer:
832040
pure lambda calculus
(See http://en.wikipedia.org/wiki/Lambda_calculus). The following solution works almost the same way as the previous solution, but uses lambda calculus
( /(
' ( x
. $x:#:~<0
& ( /('(f.($f)$($f)))
$ /(
' ( r
. /(
' ( n
. $n:<2
| (($r)$($r))$($n+-2)
+ (($r)$($r))$($n+-1)
)
)
)
)
)
$ ($x)
)
)
$ 30
)
Answer:
832040
BQN
𝕊
is a useful symbol in BQN which references the function it is currently in. This can be used to perform anonymous recursion without the need of naming the function block.
The following code calls an anonymous recursive Fibonacci function on each number of the range 0-9.
{
(𝕩<2)◶⟨+´𝕊¨,𝕏⟩𝕩-1‿2
}¨↕10
⟨ 0 1 1 2 3 5 8 13 21 34 ⟩
Recursion can also be performed using an internal name defined by a header such as Fact:
or Fact 𝕩:
. This header is visible inside the block but not outside of it, so from the outside the function is anonymous. The named form allows the outer function to be called within nested blocks, while 𝕊
can only refer to the immediately containing one.
{Fact 𝕩:
(𝕩<2)◶⟨+´Fact¨,𝕏⟩𝕩-1‿2
}¨↕10
C
Using scoped function fib_i inside fib, with GCC (required version 3.2 or higher):
#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;
}
- 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
Recursive functions can be defined within statement expressions:
#include <stdio.h>
int main(){
int n = 3;
printf("%d",({
int fib(int n){
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
fib(n);
}));
return 0;
}
C#
The inner recursive function (delegate/lambda) has to be named.
static int Fib(int n)
{
if (n < 0) throw new ArgumentException("Must be non negativ", "n");
Func<int, int> fib = null; // Must be known, before we can assign recursively to it.
fib = p => p > 1 ? fib(p - 2) + fib(p - 1) : p;
return fib(n);
}
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.
double fib(double n)
{
if(n < 0)
{
throw "Invalid argument passed to fib";
}
else
{
struct actual_fib
{
static double calc(double n)
{
if(n < 2)
{
return n;
}
else
{
return calc(n-1) + calc(n-2);
}
}
};
return actual_fib::calc(n);
}
}
#include <functional>
using namespace std;
double fib(double n)
{
if(n < 0)
throw "Invalid argument";
function<double(double)> actual_fib = [&](double n)
{
if(n < 2) return n;
return actual_fib(n-1) + actual_fib(n-2);
};
return actual_fib(n);
}
Using a local function object that calls itself using this
:
double fib(double n)
{
if(n < 0)
{
throw "Invalid argument passed to fib";
}
else
{
struct
{
double operator()(double n)
{
if(n < 2)
{
return n;
}
else
{
return (*this)(n-1) + (*this)(n-2);
}
}
} actual_fib;
return actual_fib(n);
}
}
Clio
Simple anonymous recursion to print from 9 to 0.
10 -> (@eager) fn n:
if n:
n - 1 -> print -> recall
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.
(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)))))
Using an anonymous function
CoffeeScript
# This is a rather obscure technique to have an anonymous
# function call itself.
fibonacci = (n) ->
throw "Argument cannot be negative" if n < 0
do (n) ->
return n if n <= 1
arguments.callee(n-2) + arguments.callee(n-1)
# Since it's pretty lightweight to assign an anonymous
# function to a local variable, the idiom below might be
# more preferred.
fibonacci2 = (n) ->
throw "Argument cannot be negative" if n < 0
recurse = (n) ->
return n if n <= 1
recurse(n-2) + recurse(n-1)
recurse(n)
Common Lisp
Using Anaphora
This version uses the anaphoric lambda
from Paul Graham's On Lisp.
(defmacro alambda (parms &body body)
`(labels ((self ,parms ,@body))
#'self))
The Fibonacci function can then be defined as
(defun fib (n)
(assert (>= n 0) nil "'~a' is a negative number" n)
(funcall
(alambda (n)
(if (>= 1 n)
n
(+ (self (- n 1)) (self (- n 2)))))
n))
Using labels
This puts a function in a local label. The function is not anonymous, but not only is it local, so that its name does not pollute the global namespace, but the name can be chosen to be identical to that of the surrounding function, so it is not a newly invented name
(defun fib (number)
"Fibonacci sequence function."
(if (< number 0)
(error "Error. The number entered: ~A is negative" number)
(labels ((fib (n a b)
(if (= n 0)
a
(fib (- n 1) b (+ a b)))))
(fib number 0 1))))
Although name space polution isn't an issue, in recognition of the obvious convenience of anonymous recursive helpers, here is another solution: add the language feature for anonymously recursive blocks: the operator RECURSIVE, with a built-in local operator RECURSE to make recursive calls.
Here is fib
rewritten to use RECURSIVE:
(defun fib (number)
"Fibonacci sequence function."
(if (< number 0)
(error "Error. The number entered: ~A is negative" number)
(recursive ((n number) (a 0) (b 1))
(if (= n 0)
a
(recurse (- n 1) b (+ a b))))))
Implementation of RECURSIVE:
(defmacro recursive ((&rest parm-init-pairs) &body body)
(let ((hidden-name (gensym "RECURSIVE-")))
`(macrolet ((recurse (&rest args) `(,',hidden-name ,@args)))
(labels ((,hidden-name (,@(mapcar #'first parm-init-pairs)) ,@body))
(,hidden-name ,@(mapcar #'second parm-init-pairs))))))
RECURSIVE works by generating a local function with LABELS, but with a machine-generated unique name. Furthermore, it provides syntactic sugar so that the initial call to the recursive function takes place implicitly, and the initial values are specified using LET-like syntax. Of course, if RECURSIVE blocks are nested, each RECURSE refers to its own function. There is no way for an inner RECURSIVE to specify recursion to an other RECURSIVE. That is what names are for!
Exercises for reader:
- In the original
fib
, the recursive local function can obtain a reference to itself using#'fib
. This would allow it to, for instance,(apply #'fib list-of-args)
. Add a way for RECURSIVE blocks to obtain a reference to themselves. - Add support for &optional and &rest parameters. Optional: also &key and &aux.
- Add LOOPBACK operator whose syntax resembles RECURSE, but which simply assigns the variables and performs a branch back to the top rather than a recursive call.
- Tail recursion optimization is compiler-dependent in Lisp. Modify RECURSIVE so that it walks the expressions and identifies tail-recursive RECURSE calls, rewriting these to use looping code. Be careful that unevaluated literal lists which resemble RECURSE calls are not rewritten, and that RECURSE calls belonging to any nested RECURSIVE invocation are not accidentally treated.
Using the Y combinator
(setf (symbol-function '!) (symbol-function 'funcall)
(symbol-function '!!) (symbol-function 'apply))
(defmacro ? (args &body body)
`(lambda ,args ,@body))
(defstruct combinator
(name nil :type symbol)
(function nil :type function))
(defmethod print-object ((combinator combinator) stream)
(print-unreadable-object (combinator stream :type t)
(format stream "~A" (combinator-name combinator))))
(defconstant +y-combinator+
(make-combinator
:name 'y-combinator
:function (? (f) (! (? (g) (! g g))
(? (g) (! f (? (&rest a)
(!! (! g g) a))))))))
(defconstant +z-combinator+
(make-combinator
:name 'z-combinator
:function (? (f) (! (? (g) (! f (? (x) (! (! g g) x))))
(? (g) (! f (? (x) (! (! g g) x))))))))
(defparameter *default-combinator* +y-combinator+)
(defmacro with-y-combinator (&body body)
`(let ((*default-combinator* +y-combinator+))
,@body))
(defmacro with-z-combinator (&body body)
`(let ((*default-combinator* +z-combinator+))
,@body))
(defun x-call (x-function &rest args)
(apply (funcall (combinator-function *default-combinator*) x-function) args))
(defmacro x-function ((name &rest args) &body body)
`(lambda (,name)
(lambda ,args
(macrolet ((,name (&rest args)
`(funcall ,',name ,@args)))
,@body))))
(defmacro x-defun (name args &body body)
`(defun ,name ,args
(x-call (x-function (,name ,@args) ,@body) ,@args)))
;;;; examples
(x-defun factorial (n)
(if (zerop n)
1
(* n (factorial (1- n)))))
(x-defun fib (n)
(case n
(0 0)
(1 1)
(otherwise (+ (fib (- n 1))
(fib (- n 2))))))
Using optional function parameters
We can use optional parameters to get tail recursive functions without a helper.
(defun fib (n &optional (f1 0) (f2 1))
(if (< n 0)
(format t "Parameter must be >= 0")
(if (zerop n)
f1
(fib (1- n) f2 (+ f1 f2)))))
D
int fib(in uint arg) pure nothrow @safe @nogc {
assert(arg >= 0);
return function uint(in uint n) pure nothrow @safe @nogc {
static immutable self = &__traits(parent, {});
return (n < 2) ? n : self(n - 1) + self(n - 2);
}(arg);
}
void main() {
import std.stdio;
39.fib.writeln;
}
- Output:
63245986
With Anonymous Class
In this version 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.
import std.stdio;
int fib(in int n) pure nothrow {
assert(n >= 0);
return (new class {
static int opCall(in int m) pure nothrow {
if (m < 2)
return m;
else
return opCall(m - 1) + opCall(m - 2);
}
})(n);
}
void main() {
writeln(fib(39));
}
The output is the same.
Dylan
This puts a function in a local method binding. The function is not anonymous, but the name fib1 is local and never pollutes the outside namespace.
define function fib (n)
when (n < 0)
error("Can't take fibonacci of negative integer: %d\n", n)
end;
local method fib1 (n, a, b)
if (n = 0)
a
else
fib1(n - 1, b, a + b)
end
end;
fib1(n, 0, 1)
end
Déjà Vu
With Y combinator
Y f:
labda y:
labda:
f y @y
call dup
labda fib n:
if <= n 1:
1
else:
fib - n 1
fib - n 2
+
Y
set :fibo
for j range 0 10:
!print fibo j
With recurse
fibo-2 n:
n 0 1
labda times back-2 back-1:
if = times 0:
back-2
elseif = times 1:
back-1
elseif = times 2:
+ back-1 back-2
else:
recurse -- times back-1 + back-1 back-2
call
for j range 0 10:
!print fibo-2 j
Note that this method starts from 0, while the previous starts from 1.
Delphi
program AnonymousRecursion;
{$APPTYPE CONSOLE}
uses
SysUtils;
function Fib(X: Integer): integer;
function DoFib(N: Integer): Integer;
begin
if N < 2 then Result:=N
else Result:=DoFib(N-1) + DoFib(N-2);
end;
begin
if X < 0 then raise Exception.Create('Argument < 0')
else Result:=DoFib(X);
end;
var I: integer;
begin
for I:=-1 to 15 do
begin
try
WriteLn(I:3,' - ',Fib(I):3);
except WriteLn(I,' - Error'); end;
end;
WriteLn('Hit Any Key');
ReadLn;
end.
- Output:
-1 - -1 - Error 0 - 0 1 - 1 2 - 1 3 - 2 4 - 3 5 - 5 6 - 8 7 - 13 8 - 21 9 - 34 10 - 55 11 - 89 12 - 144 13 - 233 14 - 377 15 - 610 Hit Any Key
EchoLisp
A named let provides a local lambda via a label.
(define (fib n)
(let _fib ((a 1) (b 1) (n n))
(if
(<= n 1) a
(_fib b (+ a b) (1- n)))))
Ela
Using fix-point combinator:
fib n | n < 0 = fail "Negative n"
| else = fix (\f n -> if n < 2 then n else f (n - 1) + f (n - 2)) n
Function 'fix' is defined in standard Prelude as follows:
fix f = f (& fix f)
Elena
ELENA 6.x:
import extensions;
fib(n)
{
if (n < 0)
{ InvalidArgumentException.raise() };
^ (n) {
if (n > 1)
{
^ this self(n - 2) + (this self(n - 1))
}
else
{
^ n
}
}(n)
}
public program()
{
for (int i := -1; i <= 10; i += 1)
{
console.print("fib(",i,")=");
try
{
console.printLine(fib(i))
}
catch(Exception e)
{
console.printLine("invalid")
}
};
console.readChar()
}
- Output:
fib(-1)=invalid fib(0)=0 fib(1)=1 fib(2)=1 fib(3)=2 fib(4)=3 fib(5)=5 fib(6)=8 fib(7)=13 fib(8)=21 fib(9)=34 fib(10)=55
Elixir
With Y-Combinator:
fib = fn f -> (
fn x -> if x == 0, do: 0, else: (if x == 1, do: 1, else: f.(x - 1) + f.(x - 2)) end
)
end
y = fn x -> (
fn f -> f.(f)
end).(
fn g -> x.(fn z ->(g.(g)).(z) end)
end)
end
IO.inspect y.(&(fib.(&1))).(40)
- Output:
102334155
EMal
fun fibonacci = int by int n
if n < 0 do
logLine("Invalid argument: " + n) # logs on standard error
return -1 ^| it should be better to raise an error,
| but the task is about recursive functions
|^
end
fun actualFibonacci = int by int n
return when(n < 2, n, actualFibonacci(n - 1) + actualFibonacci(n - 2))
end
return actualFibonacci(n)
end
writeLine("F(0) = " + fibonacci(0))
writeLine("F(20) = " + fibonacci(20))
writeLine("F(-10) = " + fibonacci(-10))
writeLine("F(30) = " + fibonacci(30))
writeLine("F(10) = " + fibonacci(10))
- Output:
F(0) = 0 F(20) = 6765 Invalid argument: -10 F(-10) = -1 F(30) = 832040 F(10) = 55
Erlang
Two solutions. First fib that use the module to hide its helper. The helper also is called fib so there is no naming problem. Then fib_internal which has the helper function inside itself.
-module( anonymous_recursion ).
-export( [fib/1, fib_internal/1] ).
fib( N ) when N >= 0 ->
fib( N, 1, 0 ).
fib_internal( N ) when N >= 0 ->
Fun = fun (_F, 0, _Next, Acc ) -> Acc;
(F, N, Next, Acc) -> F( F, N - 1, Acc+Next, Next )
end,
Fun( Fun, N, 1, 0 ).
fib( 0, _Next, Acc ) -> Acc;
fib( N, Next, Acc ) -> fib( N - 1, Acc+Next, Next ).
F#
Using a nested function:
The function 'fib2' is only visible inside the 'fib' function.
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)
Using a fixed point combinator:
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)
- Output:
Both functions have the same output.
[-1..5] |> List.map fib |> printfn "%A"
[null; Some 1; Some 1; Some 2; Some 3; Some 5; Some 8]
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.
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 ) ;
The name q in the stack effect has no significance; call( x x -- x )
would still work.
The recursive quotation has 2 significant disadvantages:
- 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
andswap
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. - Factor cannot infer the stack effect of a recursive quotation. The last line must have
call( n q -- m )
instead of plaincall
; butcall( 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 offib
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.
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
- 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)
FBSL
#APPTYPE CONSOLE
FUNCTION Fibonacci(n)
IF n < 0 THEN
RETURN "Nuts!"
ELSE
RETURN Fib(n)
END IF
FUNCTION Fib(m)
IF m < 2 THEN
Fib = m
ELSE
Fib = Fib(m - 1) + Fib(m - 2)
END IF
END FUNCTION
END FUNCTION
PRINT Fibonacci(-1.5)
PRINT Fibonacci(1.5)
PRINT Fibonacci(13.666)
PAUSE
Output:
Nuts! 1.5 484.082 Press any key to continue...
Forth
Recursion is always anonymous in Forth, allowing it to be used in anonymous functions. However, definitions can't be defined during a definition (there are no 'local functions'), and the data stack can't be portably used to get data into a definition being defined.
- and any Forth in which colon-sys consumes zero cells on the data stack.
:noname ( n -- n' )
dup 2 < ?exit
1- dup recurse swap 1- recurse + ; ( xt )
: fib ( +n -- n' )
dup 0< abort" Negative numbers don't exist."
[ ( xt from the :NONAME above ) compile, ] ;
Portability is achieved with a once-off variable (or any temporary-use space with a constant address - i.e., not PAD):
( xt from :noname in the previous example )
variable pocket pocket !
: fib ( +n -- n' )
dup 0< abort" Negative numbers don't exist."
[ pocket @ compile, ] ;
Currently, most Forths have started to support embedded definitions (shown here for iForth):
: fib ( +n -- )
dup 0< abort" Negative numbers don't exist"
[: dup 2 < ?exit 1- dup MYSELF swap 1- MYSELF + ;] execute . ;
Fortran
Since a hidden named function instead of an anonymous one seems to be ok with implementors, here is the Fortran version:
integer function fib(n)
integer, intent(in) :: n
if (n < 0 ) then
write (*,*) 'Bad argument: fib(',n,')'
stop
else
fib = purefib(n)
end if
contains
recursive pure integer function purefib(n) result(f)
integer, intent(in) :: n
if (n < 2 ) then
f = n
else
f = purefib(n-1) + purefib(n-2)
end if
end function purefib
end function fib
FreeBASIC
FreeBASIC does not support nested functions, lambda expressions, functions inside nested types or even (in the default dialect) gosub.
However, for compatibility with old QB code, gosub can be used if one specifies the 'fblite', 'qb' or 'deprecated dialects:
' FB 1.05.0 Win64
#Lang "fblite"
Option Gosub '' enables Gosub to be used
' Using gosub to simulate a nested function
Function fib(n As UInteger) As UInteger
Gosub nestedFib
Exit Function
nestedFib:
fib = IIf(n < 2, n, fib(n - 1) + fib(n - 2))
Return
End Function
' This function simulates (rather messily) gosub by using 2 gotos and would therefore work
' even in the default dialect
Function fib2(n As UInteger) As UInteger
Goto nestedFib
exitFib:
Exit Function
nestedFib:
fib2 = IIf(n < 2, n, fib2(n - 1) + fib2(n - 2))
Goto exitFib
End Function
For i As Integer = 1 To 12
Print fib(i); " ";
Next
Print
For j As Integer = 1 To 12
Print fib2(j); " ";
Next
Print
Print "Press any key to quit"
Sleep
- Output:
1 1 2 3 5 8 13 21 34 55 89 144 1 1 2 3 5 8 13 21 34 55 89 144
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution.
It consists in having a local function inside the main function, so it is neither visible nor available outside. The local function is defined after the validation, so if the input is invalid, neither the definition nor its invocation is performed.
Test cases
Go
Y combinator
Y combinator solution. Go has no special support for anonymous recursion.
package main
import "fmt"
func main() {
for _, n := range []int{0, 1, 2, 3, 4, 5, 10, 40, -1} {
f, ok := arFib(n)
if ok {
fmt.Printf("fib %d = %d\n", n, f)
} else {
fmt.Println("fib undefined for negative numbers")
}
}
}
func arFib(n int) (int, bool) {
switch {
case n < 0:
return 0, false
case n < 2:
return n, true
}
return yc(func(recurse fn) fn {
return func(left, term1, term2 int) int {
if left == 0 {
return term1+term2
}
return recurse(left-1, term1+term2, term1)
}
})(n-2, 1, 0), true
}
type fn func(int, int, int) int
type ff func(fn) fn
type fx func(fx) fn
func yc(f ff) fn {
return func(x fx) fn {
return x(x)
}(func(x fx) fn {
return f(func(a1, a2, a3 int) int {
return x(x)(a1, a2, a3)
})
})
}
- Output:
fib 0 = 0 fib 1 = 1 fib 2 = 1 fib 3 = 2 fib 4 = 3 fib 5 = 5 fib 10 = 55 fib 40 = 102334155 fib undefined for negative numbers
Closure
package main
import (
"errors"
"fmt"
)
func fib(n int) (result int, err error) {
var fib func(int) int // Must be declared first so it can be called in the closure
fib = func(n int) int {
if n < 2 {
return n
}
return fib(n-1) + fib(n-2)
}
if n < 0 {
err = errors.New("negative n is forbidden")
return
}
result = fib(n)
return
}
func main() {
for i := -1; i <= 10; i++ {
if result, err := fib(i); err != nil {
fmt.Printf("fib(%d) returned error: %s\n", i, err)
} else {
fmt.Printf("fib(%d) = %d\n", i, result)
}
}
}
- Output:
fib(-1) returned error: negative n is forbidden fib(0) = 0 fib(1) = 1 fib(2) = 1 fib(3) = 2 fib(4) = 3 fib(5) = 5 fib(6) = 8 fib(7) = 13 fib(8) = 21 fib(9) = 34 fib(10) = 55
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.
def fib = {
assert it > -1
{i -> i < 2 ? i : {j -> owner.call(j)}(i-1) + {k -> owner.call(k)}(i-2)}(it)
}
Test:
def fib0to20 = (0..20).collect(fib)
println fib0to20
try {
println fib(-25)
} catch (Throwable e) {
println "KABOOM!!"
println e.message
}
- 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.
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)
Anonymous function:
This uses the 'fix' function to find the fixed point of the anonymous function.
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
- Output:
Both functions provide the same output when run in GHCI.
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]
Or, without imports (inlining an anonymous fix)
fib :: Integer -> Maybe Integer
fib n
| n < 0 = Nothing
| otherwise =
Just $
(\f ->
let x = f x
in x)
(\f n ->
if n > 1
then f (n - 1) + f (n - 2)
else 1)
n
-- TEST ----------------------------------------------------------------------
main :: IO ()
main =
print $
fib <$> [-4 .. 10] >>=
\m ->
case m of
Just x -> [x]
_ -> []
- Output:
[1,1,2,3,5,8,13,21,34,55,89]
Icon and Unicon
The following solution works in both languages. A cache is used to improve performance.
This example is more a case of can it even be done, and just because we CAN do something - doesn't mean we should do it. The use of co-expressions for this purpose was probably never intended by the language designers and is more than a little bit intensive and definitely NOT recommended.
This example does accomplish the goals of hiding the procedure inside fib so that the type and value checking is outside the recursion. It also does not require an identifier to reference the inner procedure; but, it requires a local variable to remember our return point. Also, each recursion will result in the current co-expression being refreshed, essentially copied, placing a heavy demand on co-expression resources.
Some of the code requires some explaining:
- The double curly brace syntax after makeProc serves two different purposes, the outer set is used in the call to create a co-expression. The inner one binds all the expressions together as a single unit.
- At #1 we remember where we came from and receive n from our caller
- At #2 we transmit the new parameters to refreshed copies of the current co-expression setup to act as a normal procedure and cache the result.
- At #3 we transmit the result back to our caller.
- The procedure makeProc consumes the the first transmission to the co-expression which is ignored. Essentially this primes the co-expression to behave like a regular procedure.
For reference, here is the non-cached version:
The performance of this second version is 'truly impressive'. And I mean that in a really bad way. By way of example, using default memory settings on a current laptop, a simple recursive non-cached fib out distanced the non-cached fib above by a factor of 20,000. And a simple recursive cached version out distanced the cached version above by a factor of 2,000.
Io
The most natural way to solve this task is to use a nested function whose scope is limited to the helper function.
fib := method(x,
if(x < 0, Exception raise("Negative argument not allowed!"))
fib2 := method(n,
if(n < 2, n, fib2(n-1) + fib2(n-2))
)
fib2(x floor)
)
J
Copied directly from the fibonacci sequence task, which in turn copied from one of several implementations in an essay on the J Wiki:
fibN=: (-&2 +&$: -&1)^:(1&<) M."0
Note that this is an identity function for arguments less than 1 (and 1 (and 5)).
Examples:
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
(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.
Note also http://www.jsoftware.com/pipermail/general/2003-August/015571.html which points out that the form
basis ` ($: @: g) @. test
which is an anonymous form matches the "tail recursion" pattern is not automatically transformed to satisfy the classic "tail recursion optimization". That optimization would be implemented as transforming this particular example of recursion to the non-recursive
basis @: (g^:test^:_)
Of course, that won't work here, because we are adding two recursively obtained results where tail recursion requires that the recursive result is the final result.
See also Y combinator but note that that approach is less efficient (has higher costs).
Also, note that J's "implicit mapping" is primitive recursive (as is arithmetic in general), and thus in some contexts a "more efficient approach to recursion".
Java
Creates an anonymous inner class to do the dirty work. While it does keep the recursive function out of the namespace of the class, it does seem to violate the spirit of the task in that the function is still named.
public static long fib(int n) {
if (n < 0)
throw new IllegalArgumentException("n can not be a negative number");
return new Object() {
private long fibInner(int n) {
return (n < 2) ? n : (fibInner(n - 1) + fibInner(n - 2));
}
}.fibInner(n);
}
Another way is to use the Java Y combinator implementation (the following uses the Java 8 version for better readability). Note that the fib method below is practically the same as that of the version above, with less fibInner.
import java.util.function.Function;
@FunctionalInterface
interface SelfApplicable<OUTPUT> {
OUTPUT apply(SelfApplicable<OUTPUT> input);
}
class Utils {
public static <INPUT, OUTPUT> SelfApplicable<Function<Function<Function<INPUT, OUTPUT>, Function<INPUT, OUTPUT>>, Function<INPUT, OUTPUT>>> y() {
return y -> f -> x -> f.apply(y.apply(y).apply(f)).apply(x);
}
public static <INPUT, OUTPUT> Function<Function<Function<INPUT, OUTPUT>, Function<INPUT, OUTPUT>>, Function<INPUT, OUTPUT>> fix() {
return Utils.<INPUT, OUTPUT>y().apply(Utils.<INPUT, OUTPUT>y());
}
public static long fib(int m) {
if (m < 0)
throw new IllegalArgumentException("n can not be a negative number");
return Utils.<Integer, Long>fix().apply(
f -> n -> (n < 2) ? n : (f.apply(n - 1) + f.apply(n - 2))
).apply(m);
}
}
JavaScript
function fibo(n) {
if (n < 0) { throw "Argument cannot be negative"; }
return (function(n) {
return (n < 2) ? n : arguments.callee(n-1) + arguments.callee(n-2);
})(n);
}
Note that arguments.callee
will not be available in ES5 Strict mode. Instead, you are expected to "name" function (the name is only visible inside function however).
function fibo(n) {
if (n < 0) { throw "Argument cannot be negative"; }
return (function fib(n) {
return (n < 2) ? n : fib(n-1) + fib(n-2);
})(n);
}
Joy
This definition is taken from "Recursion Theory and Joy" by Manfred von Thun.
fib == [small] [] [pred dup pred] [+] binrec;
jq
The "recurse" filter supports a type of anonymous recursion, e.g. to generate a stream of integers starting at 0:
0 | recurse(. + 1)
Also, as is the case for example with Julia, jq allows you to define an inner/nested function (in the follow example, aux
) that is only defined within the scope of the surrounding function (here fib
). It is thus invisible outside the function:
def fib(n):
def aux: if . == 0 then 0
elif . == 1 then 1
else (. - 1 | aux) + (. - 2 | aux)
end;
if n < 0 then error("negative arguments not allowed")
else n | aux
end ;
Julia
Julia allows you to define an inner/nested function (here, aux
) that is only defined within the surrounding function fib
scope.
function fib(n)
if n < 0
throw(ArgumentError("negative arguments not allowed"))
end
aux(m) = m < 2 ? one(m) : aux(m-1) + aux(m-2)
aux(n)
end
K
fib: {:[x<0; "Error Negative Number"; {:[x<2;x;_f[x-2]+_f[x-1]]}x]}
:
fib: {:[x<0; "Error Negative Number"; {:[x<2;x;o[x-2]+o[x-1]]}x]}
Examples:
fib'!10
0 1 1 2 3 5 8 13 21 34
fib -1
"Error Negative Number"
Klingphix
include ..\Utilitys.tlhy
:fib %f !f
%fr
[ %n !n
$n 2 <
( [$n]
[$n 1 - $fr eval $n 2 - $fr eval +] )
if
] !fr
$f 0 <
( ["Error: number is negative"]
[$f true $fr if] )
if
;
25 fib ?
msec ?
"End " input
Klong
fib::{:[x<0;"error: negative":|x<2;x;.f(x-1)+.f(x-2)]}
Kotlin
fun fib(n: Int): Int {
require(n >= 0)
fun fib(k: Int, a: Int, b: Int): Int =
if (k == 0) a else fib(k - 1, b, a + b)
return fib(n, 0, 1)
}
fun main(args: Array<String>) {
for (i in 0..20) print("${fib(i)} ")
println()
}
- Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
Lambdatalk
1) defining a quasi-recursive function combined with a simple Ω-combinator:
{def fibo {lambda {:n}
{{{lambda {:f} {:f :f}}
{lambda {:f :n :a :b}
{if {< :n 0}
then the number must be positive!
else {if {< :n 1}
then :a
else {:f :f {- :n 1} {+ :a :b} :a}}}}} :n 1 0}}}
-> fibo
2) testing:
{fibo -1} -> the number must be positive!
{fibo 0} -> 1
{fibo 8} -> 34
{fibo 1000} -> 7.0330367711422765e+208
{S.map fibo {S.serie 1 20}}
-> 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
We could also avoid any name and write an IIFE
{{lambda {:n}
{{{lambda {:f} {:f :f}}
{lambda {:f :n :a :b}
{if {< :n 0}
then the number must be positive!
else {if {< :n 1}
then :a
else {:f :f {- :n 1} {+ :a :b} :a}}}}} :n 1 0}}
8}
-> 34
Lang
fp.fib = ($n) -> {
if($n < 0) {
throw fn.withErrorMessage($LANG_ERROR_INVALID_ARGUMENTS, n must be >= 0)
}
fp.innerFib = ($n) -> {
if($n < 2) {
return $n
}
return parser.op(fp.innerFib($n - 1) + fp.innerFib($n - 2))
}
return fp.innerFib($n)
}
Lingo
Lingo does not support anonymous functions. But what comes close: you can create and instantiate an "anonymous class":
on fib (n)
if n<0 then return _player.alert("negative arguments not allowed")
-- create instance of unnamed class in memory only (does not pollute namespace)
m = new(#script)
r = RETURN
m.scriptText = "on fib (me,n)"&r&"if n<2 then return n"&r&"return me.fib(n-1)+me.fib(n-2)"&r&"end"
aux = m.script.new()
m.erase()
return aux.fib(n)
end
put fib(10)
-- 55
LOLCODE
HAI 1.3
HOW IZ I fib YR x
DIFFRINT x AN BIGGR OF x AN 0, O RLY?
YA RLY, FOUND YR "ERROR"
OIC
HOW IZ I fib_i YR n
DIFFRINT n AN BIGGR OF n AN 2, O RLY?
YA RLY, FOUND YR n
OIC
FOUND YR SUM OF...
I IZ fib_i YR DIFF OF n AN 2 MKAY AN...
I IZ fib_i YR DIFF OF n AN 1 MKAY
IF U SAY SO
FOUND YR I IZ fib_i YR x MKAY
IF U SAY SO
HOW IZ I fib_i YR n
VISIBLE "SRY U CANT HAS FIBS DIS TIEM"
IF U SAY SO
IM IN YR fibber UPPIN YR i TIL BOTH SAEM i AN 5
I HAS A i ITZ DIFF OF i AN 1
VISIBLE "fib(:{i}) = " I IZ fib YR i MKAY
IM OUTTA YR fibber
I IZ fib_i YR 3 MKAY
KTHXBYE
Lua
Using a Y combinator.
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)
using a metatable (also achieves memoization)
return setmetatable({1,1},{__index = function(self, n)
self[n] = self[n-1] + self[n-2]
return self[n]
end})
M2000 Interpreter
We can use a function in string. We can named it so the error say about "Fibonacci" To exclude first check for negative we have to declare a function in anonymous function, which may have a name (a local name)
A$={{ Module "Fibonacci" : Read X :If X<0 then {Error {X<0}} Else Fib=Lambda (x)->if(x>1->fib(x-1)+fib(x-2), x) : =fib(x)}}
Try Ok {
Print Function(A$, -12)
}
If Error or Not Ok Then Print Error$
Print Function(A$, 12)=144 ' true
For recursion we can use Lambda() or Lambda$() (for functions which return string) and not name of function so we can use it in a referenced function. Here in k() if we have the fib() we get an error, but with lambda(), interpreter use current function's name.
Function fib(x) {
If x<0 then Error "argument outside of range"
If x<2 then =x : exit
Def fib1(x)=If(x>1->lambda(x-1)+lambda(x-2), x)
=fib1(x)
}
Module CheckIt (&k()) {
Print k(12)
}
CheckIt &Fib()
Print fib(-2) ' error
Using lambda function
fib=lambda -> {
fib1=lambda (x)->If(x>1->lambda(x-1)+lambda(x-2), x)
=lambda fib1 (x) -> {
If x<0 then Error "argument outside of range"
If x<2 then =x : exit
=fib1(x)
}
}() ' using () execute this lambda so fib get the returned lambda
Module CheckIt (&k()) {
Print k(12)
}
CheckIt &Fib()
Try {
Print fib(-2)
}
Print Error$
Z=Fib
Print Z(12)
Dim a(10)
a(3)=Z
Print a(3)(12)=144
Inventory Alfa = "key1":=Z
Print Alfa("key1")(12)=144
Using a Group (object in M2000) like a function
A Group may have a name like k (which hold a unique group), or can be unnamed like item in A(4), or can be pointed by a variable (or an array item) (we can use many pointers for the same group)
Class Something {
\\ this class is a global function
\\ return a group with a value with one parameter
private:
\\ we can use lambda(), but here we use .fib1() as This.fib1()
fib1=lambda (x)->If(x>1->.fib1(x-1)+.fib1(x-2), x)
public:
Value (x) {
If x<0 then Error "argument outside of range"
If x<2 then =x : exit
=This.fib1(x) \\ we can omit This using .fib1(x)
}
}
K=Something() ' K is a static group here
Print k(12)=144
Dim a(10)
a(4)=Group(K)
Print a(4)(12)=144
pk->Something() ' pk is a pointer to group (object in M2000)
\\ pointers need Eval to process arguments
Print Eval(pk, 12)=144
Inventory Alfa = "Key2":=Group(k), 10*10:=pk
Print Alfa("Key2")(12)=144
Print Eval(Alfa("100"),12)=144, Eval(Alfa(100),12)=144
Maple
In Maple, the keyword thisproc refers to the currently executing procedure (closure), which need not be named. The following defines a procedure Fib, which uses a recursive, anonymous (unnamed) procedure to implement the Fibonacci sequence. For better efficiency, we use Maple's facility for automatic memoisation ("option remember").
Fib := proc( n :: nonnegint )
proc( k )
option remember; # automatically memoise
if k = 0 then
0
elif k = 1 then
1
else
# Recurse, anonymously
thisproc( k - 1 ) + thisproc( k - 2 )
end
end( n )
end proc:
For example:
> seq( Fib( i ), i = 0 .. 10 );
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
> Fib( -1 );
Error, invalid input: Fib expects its 1st argument, n, to be of type
nonnegint, but received -1
The check for a negative argument could be put either on the outer Fib procedure, or the anonymous inner procedure (or both). As it wasn't completely clear what was intended, I put it on Fib, which results in a slightly better error message in that it does not reveal how the procedure was actually implemented.
Mathematica / Wolfram Language
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.
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}
Making sure that the check is only performed once.
check := (Print[#];#<0)&
fib /@ Range[0,4]
0
1
2
3
4
{1, 1, 2, 3, 5}
MATLAB
Not anonymous exactly, but using a nested function solves all the problems stated in the task description.
- does not exist outside of parent function
- does not need a new name, can reuse the parent name
- a nested function can be defined in the place where it is needed
function v = fibonacci(n)
assert(n >= 0)
v = fibonacci(n,0,1);
% nested function
function a = fibonacci(n,a,b)
if n ~= 0
a = fibonacci(n-1,b,a+b);
end
end
end
Nemerle
Not anonymous exactly, but using inner function solves all problems stated in task description.
- name is basically the same as outer function and doesn't pollute the namespace
- inner function not expected to be called from anywhere else
- nesting maintains program flow in source code
using System;
using System.Console;
module Fib
{
Fib(n : long) : long
{
def fib(m : long)
{
|0 => 1
|1 => 1
|_ => fib(m - 1) + fib(m - 2)
}
match(n)
{
|n when (n < 0) => throw ArgumentException("Fib() not defined on negative numbers")
|_ => fib(n)
}
}
Main() : void
{
foreach (i in [-2 .. 10])
{
try {WriteLine("{0}", Fib(i));}
catch {|e is ArgumentException => WriteLine(e.Message)}
}
}
}
Nim
# Using scoped function fibI inside fib
proc fib(x: int): int =
proc fibI(n: int): int =
if n < 2: n else: fibI(n-2) + fibI(n-1)
if x < 0:
raise newException(ValueError, "Invalid argument")
return fibI(x)
for i in 0..4:
echo fib(i)
# fibI(10) # undeclared identifier 'fibI'
Output:
0 1 1 2 3
Objective-C
This shows how a method (not regular function) can recursively call itself without explicitly putting its name in the code.
#import <Foundation/Foundation.h>
@interface AnonymousRecursion : NSObject { }
- (NSNumber *)fibonacci:(NSNumber *)n;
@end
@implementation AnonymousRecursion
- (NSNumber *)fibonacci:(NSNumber *)n {
int i = [n intValue];
if (i < 0)
@throw [NSException exceptionWithName:NSInvalidArgumentException
reason:@"fibonacci: no negative numbers"
userInfo:nil];
int result;
if (i < 2)
result = 1;
else
result = [[self performSelector:_cmd withObject:@(i-1)] intValue]
+ [[self performSelector:_cmd withObject:@(i-2)] intValue];
return @(result);
}
@end
int main (int argc, const char *argv[]) {
@autoreleasepool {
AnonymousRecursion *dummy = [[AnonymousRecursion alloc] init];
NSLog(@"%@", [dummy fibonacci:@8]);
}
return 0;
}
- With internal named recursive block
#import <Foundation/Foundation.h>
int fib(int n) {
if (n < 0)
@throw [NSException exceptionWithName:NSInvalidArgumentException
reason:@"fib: no negative numbers"
userInfo:nil];
int (^f)(int);
__block __weak int (^weak_f)(int); // block cannot capture strong reference to itself
weak_f = f = ^(int n) {
if (n < 2)
return 1;
else
return weak_f(n-1) + weak_f(n-2);
};
return f(n);
}
int main (int argc, const char *argv[]) {
@autoreleasepool {
NSLog(@"%d", fib(8));
}
return 0;
}
When ARC is disabled, the above should be:
#import <Foundation/Foundation.h>
int fib(int n) {
if (n < 0)
@throw [NSException exceptionWithName:NSInvalidArgumentException
reason:@"fib: no negative numbers"
userInfo:nil];
__block int (^f)(int);
f = ^(int n) {
if (n < 2)
return 1;
else
return f(n-1) + f(n-2);
};
return f(n);
}
int main (int argc, const char *argv[]) {
@autoreleasepool {
NSLog(@"%d", fib(8));
}
return 0;
}
OCaml
OCaml 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.
let fib n =
let rec real = function
0 -> 1
| 1 -> 1
| n -> real (n-1) + real (n-2)
in
if n < 0 then
None
else
Some (real n)
Anonymous function:
This uses the 'fix' function to find the fixed point of the anonymous function.
let rec fix f x = f (fix f) x
let fib n =
if n < 0 then
None
else
Some (fix (fun f -> fun n -> if n <= 1 then 1 else f (n-1) + f (n-2)) n)
- Output:
# fib 8;; - : int option = Some 34
Ol
This uses named let to create a local function (loop) that only exists inside of function fibonacci.
(define (fibonacci n)
(if (> 0 n)
"error: negative argument."
(let loop ((a 1) (b 0) (count n))
(if (= count 0)
b
(loop (+ a b) a (- count 1))))))
(print
(map fibonacci '(1 2 3 4 5 6 7 8 9 10)))
- Output:
'(1 1 2 3 5 8 13 21 34 55)
OxygenBasic
An inner function keeps the name-space clean:
function fiboRatio() as double
function fibo( double i, j ) as double
if j > 2e12 then return j / i
return fibo j, i + j
end function
return fibo 1, 1
end function
print fiboRatio
PARI/GP
This version uses a Y combinator to get a self-reference.
Fib(n)={
my(F=(k,f)->if(k<2,k,f(k-1,f)+f(k-2,f)));
if(n<0,(-1)^(n+1),1)*F(abs(n),F)
};
This version gets a self-reference from self()
.
Fib(n)={
my(F=k->my(f=self());if(k<2,k,f(k-1)+f(k-2)));
if(n<0,(-1)^(n+1),1)*F(abs(n))
};
Pascal
program AnonymousRecursion;
function Fib(X: Integer): integer;
function DoFib(N: Integer): Integer;
begin
if N < 2 then DoFib:=N
else DoFib:=DoFib(N-1) + DoFib(N-2);
end;
begin
if X < 0 then Fib:=X
else Fib:=DoFib(X);
end;
var I,V: integer;
begin
for I:=-1 to 15 do
begin
V:=Fib(I);
Write(I:3,' - ',V:3);
if V<0 then Write(' - Error');
WriteLn;
end;
WriteLn('Hit Any Key');
ReadLn;
end.
- Output:
-1 - -1 - Error 0 - 0 1 - 1 2 - 1 3 - 2 4 - 3 5 - 5 6 - 8 7 - 13 8 - 21 9 - 34 10 - 55 11 - 89 12 - 144 13 - 233 14 - 377 15 - 610 Hit Any Key
PascalABC.NET
function Fib(n: integer): integer;
begin
if n <= 0 then
raise new System.ArgumentOutOfRangeException('Must be > 0','n');
var fibHelper: (integer,integer,integer) -> integer;
fibHelper := (n,a,b) -> n = 1 ? a : fibHelper(n-1, b, a + b);
Result := fibHelper(n,1,1);
end;
begin
for var i:=1 to 10 do
Fib(i).Print;
end.
or
function Fib(n: integer): integer;
function fibHelper(n,a,b: integer): integer :=
n = 1 ? a : fibHelper(n-1, b, a + b);
begin
if n <= 0 then
raise new System.ArgumentOutOfRangeException('Must be > 0','n');
Result := fibHelper(n,1,1);
end;
begin
for var i:=1 to 10 do
Fib(i).Print;
end.
- Output:
1 1 2 3 5 8 13 21 34 55
Perl
recur
isn't built into Perl, but it's easy to implement.
sub recur :prototype(&@) {
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;
}
Although for this task, it would be fine to use a lexical variable (closure) to hold an anonymous sub reference, we can also just push it onto the args stack and use it from there:
sub fib {
my ($n) = @_;
die "negative arg $n" if $n < 0;
# put anon sub on stack and do a magic goto to it
@_ = ($n, sub {
my ($n, $f) = @_;
# anon sub recurs with the sub ref on stack
$n < 2 ? $n : $f->($n - 1, $f) + $f->($n - 2, $f)
});
goto $_[1];
}
print(fib($_), " ") for (0 .. 10);
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.
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);
}
Perl 5.16 and __SUB__
Perl 5.16 introduced __SUB__ which refers to the current subroutine.
use v5.16;
say sub {
my $n = shift;
$n < 2 ? $n : __SUB__->($n-2) + __SUB__->($n-1)
}->($_) for 0..10
Phix
using classes
With proof that the private fib_i() does not pollute the outer namespace.
without js -- (no class yet) class Fib private function fib_i(integer n) return iff(n<2?n:this.fib_i(n-1)+this.fib_i(n-2)) end function public function fib(integer n) if n<0 then throw("constraint error") end if return this.fib_i(n) end function end class Fib f = new() function fib_i(integer i) return sprintf("this is not the fib_i(%d) you are looking for\n",i) end function ?f.fib(10) --?f.fib_i(10) -- illegal ?fib_i(10)
- Output:
55 "this is not the fib_i(10) you are looking for\n"
using a lambda expression
Make of this what you will...
Obviously the inner function does not have to and in fact is not allowed to have a name itself, but it needs to be stored in something with a name before it can be called,
and in being anonymous, in order to effect recursion it must be passed to itself, repeatedly and not really anonymous at all anymore.
without js -- (no lambda yet) function erm(integer n, f) return f(n,f) end function function fib(integer n) if n<0 then throw("constraint error") end if return erm(n,function(integer n,f) return iff(n<2?n:f(n-1,f)+f(n-2,f)) end function) end function ?fib(10)
- Output:
55
PHP
In this solution, the function is always called using call_user_func()
rather than using function call syntax directly. Inside the function, we get the function itself (without having to refer to the function by name) by relying on the fact that this function must have been passed as the first argument to call_user_func()
one call up on the call stack. We can then use debug_backtrace()
to get this out.
<?php
function fib($n) {
if ($n < 0)
throw new Exception('Negative numbers not allowed');
$f = function($n) { // This function must be called using call_user_func() only
if ($n < 2)
return 1;
else {
$g = debug_backtrace()[1]['args'][0];
return call_user_func($g, $n-1) + call_user_func($g, $n-2);
}
};
return call_user_func($f, $n);
}
echo fib(8), "\n";
?>
- With internal named recursive function
<?php
function fib($n) {
if ($n < 0)
throw new Exception('Negative numbers not allowed');
$f = function($n) use (&$f) {
if ($n < 2)
return 1;
else
return $f($n-1) + $f($n-2);
};
return $f($n);
}
echo fib(8), "\n";
?>
- With a function object that can call itself using
$this
<?php
class fib_helper {
function __invoke($n) {
if ($n < 2)
return 1;
else
return $this($n-1) + $this($n-2);
}
}
function fib($n) {
if ($n < 0)
throw new Exception('Negative numbers not allowed');
$f = new fib_helper();
return $f($n);
}
echo fib(8), "\n";
?>
PicoLisp
(de fibo (N)
(if (lt0 N)
(quit "Illegal argument" N) )
(recur (N)
(if (> 2 N)
1
(+ (recurse (dec N)) (recurse (- N 2))) ) ) )
Explanation: The above uses the 'recur' / 'recurse' function pair, which is defined as a standard language extensions as
(de recur recurse
(run (cdr recurse)) )
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
Postscript can make use of the higher order combinators to provide recursion.
% 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}.
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.
:- 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).
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]
Same thing as the above, but modified so that the function is uncurried:
>>>from functools import partial
>>> Y = lambda f: (lambda x: x(x))(lambda y: partial(f, lambda *args: y(y)(*args)))
>>> fib = lambda f, 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]
A different approach: the function always receives itself as the first argument, and when recursing, makes sure to pass the called function as the first argument also
>>> from functools import partial
>>> Y = lambda f: partial(f, f)
>>> fib = lambda f, n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(f, n-1) + f(f, n-2)))
>>> [ Y(fib)(i) for i in range(-2, 10) ]
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
An interesting approach using introspection (from http://metapython.blogspot.com/2010/11/recursive-lambda-functions.html)
>>> from inspect import currentframe
>>> from types import FunctionType
>>> def myself (*args, **kw):
... caller_frame = currentframe(1)
... code = caller_frame.f_code
... return FunctionType(code, caller_frame.f_globals)(*args, **kw)
...
>>> print "factorial(5) =",
>>> print (lambda n:1 if n<=1 else n*myself(n-1)) ( 5 )
Another way of implementing the "Y" function is given in this post: https://stackoverflow.com/questions/481692/can-a-lambda-function-call-itself-recursively-in-python. The main problem to solve is that the function "fib" can't call itself. Therefore, the function "Y" is used to help "fib" call itself.
>>> Y = lambda f: lambda n: f(f,n)
>>> fib = lambda f, n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(f,n-1) + f(f,n-2))) #same as the first three implementations
>>> [ Y(fib)(i) for i in range(-2, 10) ]
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
All in one line:
>>> fib_func = (lambda f: lambda n: f(f,n))(lambda f, n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(f,n-1) + f(f,n-2))))
>>> [ fib_func(i) for i in range(-2, 10) ]
[None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
QBasic
DECLARE FUNCTION Fibonacci! (num!)
PRINT Fibonacci(20)
PRINT Fibonacci(30)
PRINT Fibonacci(-10)
PRINT Fibonacci(10)
END
FUNCTION Fibonacci (num)
IF num < 0 THEN
PRINT "Invalid argument: ";
Fibonacci = num
END IF
IF num < 2 THEN
Fibonacci = num
ELSE
Fibonacci = Fibonacci(num - 1) + Fibonacci(num - 2)
END IF
END FUNCTION
- Output:
Igual que la entrada de BASIC256.
Qi
Use of anonymous recursive functions is not common in Qi. The philosophy of Qi seems to be that using a "silly name" like "foo2" or "foo_helper" makes the code clearer than using anonymous recursive functions.
However, it can be done, for instance like this:
(define fib
N -> (let A (/. A N
(if (< N 2)
N
(+ (A A (- N 2))
(A A (- N 1)))))
(A A N)))
Quackery
Quackery can do anonymous recursion via the word recurse
.
[ dup 0 < iff $ "negative argument passed to fibonacci" fail [ dup 2 < if done dup 1 - recurse swap 2 - recurse + ] ] is fibonacci ( n --> n )
recurse
causes the current nest (i.e. the on that starts [ dup
and ends + ]
to be evaluated recursively. This means that if, for example, the first recursive call was inside one or more nested nests, it would not work as desired. So the first instance of recurse
in:
( *** faulty code *** ) [ dup 0 < iff $ "negative argument passed to fibonacci" fail [ dup 2 < if done [ [ [ [ [ [ [ dup 1 - recurse ] ] ] ] ] ] ] swap 2 - recurse + ] ] is fibonacci ( n --> n )
would cause the nest [ dup 1 - recurse ]
to be evaluated, and the program would go into a tailspin, recursively evaluating that nest until the return stack overflowed.
This limitation can be overcome with the understanding that recursion can be factored out into two ideas, i.e. self-reference and evaluation. The self-reference word in Quackery is this
, which puts a pointer to the current nest on the data stack (usually just called "the stack") and the evaluation word is do
, which takes an item from the stack and evaluates it. So this do
is equivalent to recurse
.
The final example fixes the previous example by using this
and do
to put the pointer to the current nest on the stack at the correct level of nesting and evaluate it within the nested nests. See also Even or Odd#Quackery: With Anonymous Mutual recursion.
[ dup 0 < iff $ "negative argument passed to fibonacci" fail [ dup 2 < if done this [ [ [ [ [ [ [ dip [ dup 1 - ] do ] ] ] ] ] ] ] swap 2 - recurse + ] ] is fibonacci ( n --> n )
Quackery also provides named recursion with forward
and resolves
, so this is usually not necessary but can be useful in unusual circumstances.
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.
fib2 <- function(n) {
(n >= 0) || stop("bad argument")
( function(n) if (n <= 1) 1 else Recall(n-1)+Recall(n-2) )(n)
}
Racket
In Racket, local helper function definitions inside of a function are only visible locally and do not pollute the module or global scope.
#lang racket
;; Natural -> Natural
;; Calculate factorial
(define (fact n)
(define (fact-helper n acc)
(if (= n 0)
acc
(fact-helper (sub1 n) (* n acc))))
(unless (exact-nonnegative-integer? n)
(raise-argument-error 'fact "natural" n))
(fact-helper n 1))
;; Unit tests, works in v5.3 and newer
(module+ test
(require rackunit)
(check-equal? (fact 0) 1)
(check-equal? (fact 5) 120))
This calculates the slightly more complex Fibonacci funciton:
#lang racket
;; Natural -> Natural
;; Calculate fibonacci
(define (fibb n)
(define (fibb-helper n fibb_n-1 fibb_n-2)
(if (= 1 n)
fibb_n-1
(fibb-helper (sub1 n) (+ fibb_n-1 fibb_n-2) fibb_n-1)))
(unless (exact-nonnegative-integer? n)
(raise-argument-error 'fibb "natural" n))
(if (zero? n) 0 (fibb-helper n 1 0)))
;; Unit tests, works in v5.3 and newer
(module+ test
(require rackunit)
(check-exn exn:fail? (lambda () (fibb -2)))
(check-equal?
(for/list ([i (in-range 21)]) (fibb i))
'(0 1 1 2 3 5 8 13 21 34 55 89 144 233
377 610 987 1597 2584 4181 6765)))
Also with the help of first-class functions in Racket, anonymous recursion can be implemented using fixed-points operators:
#lang racket
;; We use Z combinator (applicative order fixed-point operator)
(define Z
(λ (f)
((λ (x) (f (λ (g) ((x x) g))))
(λ (x) (f (λ (g) ((x x) g)))))))
(define fibonacci
(Z (λ (fibo)
(λ (n)
(if (<= n 2)
1
(+ (fibo (- n 1))
(fibo (- n 2))))))))
> (fibonacci -2) 1 > (fibonacci 5) 5 > (fibonacci 10) 55
Raku
(formerly Perl 6)
In addition to the methods in the Perl entry above, and the Y-combinator described in Y_combinator, you may also refer to an anonymous block or function from the inside:
sub fib($n) {
die "Naughty fib" if $n < 0;
return {
$_ < 2
?? $_
!! &?BLOCK($_-1) + &?BLOCK($_-2);
}($n);
}
say fib(10);
However, using any of these methods is insane, when Raku provides a sort of inside-out combinator that lets you define lazy infinite constants, where the demand for a particular value is divorced from dependencies on more primitive values. This operator, known as the sequence operator, does in a sense provide anonymous recursion to a closure that refers to more primitive values.
constant @fib = 0, 1, *+* ... *;
say @fib[10];
Here the closure, *+*, is just a quick way to write a lambda, -> $a, $b { $a + $b }. The sequence operator implicitly maps the two arguments to the -2nd and -1st elements of the sequence. So the sequence operator certainly applies an anonymous lambda, but whether it's recursion or not depends on whether you view a sequence as iteration or as simply a convenient way of memoizing a recursion. Either view is justifiable.
At this point someone may complain that the solution is doesn't fit the specified task because the sequence operator doesn't do the check for negative. True, but the sequence operator is not the whole of the solution; this check is supplied by the subscripting operator itself when you ask for @fib[-1]. Instead of scattering all kinds of arbitrary boundary conditions throughout your functions, the sequence operator maps them quite naturally to the boundary of definedness at the start of a list.
REBOL
fib: func [n /f][ do f: func [m] [ either m < 2 [m][(f m - 1) + f m - 2]] n]
REXX
[Modeled after the Fortran example.]
Since a hidden named function (instead of an anonymous function) seems
to be OK with the implementers, here are the REXX versions.
simplistic
/*REXX program to show anonymous recursion (of a function or subroutine). */
numeric digits 1e6 /*in case the user goes ka-razy with X.*/
parse arg x . /*obtain the optional argument from CL.*/
if x=='' | x=="," then x= 12 /*Not specified? Then use the default.*/
w= length(x) /*W: used for formatting the output. */
do j=0 for x+1 /*use the argument as an upper limit.*/
say 'fibonacci('right(j, w)") =" fib(j)
end /*j*/ /* [↑] show Fibonacci sequence: 0 ──► X*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
fib: procedure; parse arg z; if z>=0 then return .(z)
say "***error*** argument can't be negative."; exit
.: procedure; parse arg #; if #<2 then return #; return .(#-1) + .(#-2)
- output when using the input of: 12
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 fibonacci(11) = 89 fibonacci(12) = 144
memoization
Since the above REXX version is very slow for larger numbers, the following version was added that incorporates memoization.
It's many orders of magnitude faster for larger values.
/*REXX program to show anonymous recursion of a function or subroutine with memoization.*/
numeric digits 1e6 /*in case the user goes ka-razy with X.*/
parse arg x . /*obtain the optional argument from CL.*/
if x=='' | x=="," then x= 12 /*Not specified? Then use the default.*/
@.= .; @.0= 0; @.1= 1 /*used to implement memoization for FIB*/
w= length(x) /*W: used for formatting the output. */
do j=0 for x+1 /*use the argument as an upper limit.*/
say 'fibonacci('right(j, w)") =" fib(j)
end /*j*/ /* [↑] show Fibonacci sequence: 0 ──► X*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
fib: procedure expose @.; arg z; if z>=0 then return .(z)
say "***error*** argument can't be negative."; exit
.: procedure expose @.; arg #; if @.#\==. then return @.#; @.#=.(#-1)+.(#-2); return @.#
- output is identical to the 1st REXX version.
Ring
# Project : Anonymous recursion
t=0
for x = -2 to 12
n = x
recursion()
if x > -1
see t + nl
ok
next
func recursion()
nold1=1
nold2=0
if n < 0
see "positive argument required!" + nl
return
ok
if n=0
t=nold2
return t
ok
if n=1
t=nold1
return t
ok
while n
t=nold2+nold1
if n>2
n=n-1
nold2=nold1
nold1=t
loop
ok
return t
end
return t
Output:
positive argument required! positive argument required! 0 1 1 2 3 5 8 13 21 34 55 89 144
RPL
Hidden variable
The recursive part of the function is stored in a local variable, which is made accessible to all the recursive instances by starting its name with the ←
character.
≪ ≪ IF DUP 1 > THEN
DUP 1 - ←fib EVAL
SWAP 2 - ←fib EVAL +
END ≫ → ←fib
≪ IF DUP 0 <
THEN DROP "Negative value" DOERR
ELSE ←fib EVAL END
≫ ≫ 'FIBAR' STO
-2 FIBAR 10 FIBAR
- Output:
1: 55
Truly anonymous
Both the recursive block and the argument are pushed onto the stack, without any naming. This meets the requirements of the task perfectly and works on any RPL machine, but it is far from idiomatic and uses a lot of stack space.
≪ IF DUP 0 <
THEN DROP "Negative value"
ELSE
≪ IF DUP 1 > THEN
DUP2 1 - OVER EVAL
ROT ROT 2 - OVER EVAL +
ELSE SWAP DROP END
≫
SWAP OVER EVAL
END
≫ 'FIBAR' STO
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
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
(-2..12).map { |i| fib i rescue :error }
=> [:error, :error, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
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.
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
# 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]
# 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]
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
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
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
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
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
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
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'.
Rust
fn fib(n: i64) -> Option<i64> {
// A function declared inside another function does not pollute the outer namespace.
fn actual_fib(n: i64) -> i64 {
if n < 2 {
n
} else {
actual_fib(n - 1) + actual_fib(n - 2)
}
}
if n < 0 {
None
} else {
Some(actual_fib(n))
}
}
fn main() {
println!("Fib(-1) = {:?}", fib(-1));
println!("Fib(0) = {:?}", fib(0));
println!("Fib(1) = {:?}", fib(1));
println!("Fib(2) = {:?}", fib(2));
println!("Fib(3) = {:?}", fib(3));
println!("Fib(4) = {:?}", fib(4));
println!("Fib(5) = {:?}", fib(5));
println!("Fib(10) = {:?}", fib(10));
}
#[test]
fn test_fib() {
assert_eq!(fib(0).unwrap(), 0);
assert_eq!(fib(1).unwrap(), 1);
assert_eq!(fib(2).unwrap(), 1);
assert_eq!(fib(3).unwrap(), 2);
assert_eq!(fib(4).unwrap(), 3);
assert_eq!(fib(5).unwrap(), 5);
assert_eq!(fib(10).unwrap(), 55);
}
#[test]
fn test_invalid_argument() {
assert_eq!(fib(-1), None);
}
Scala
Using a Y-combinator:
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
- Output:
(-2,None) (-1,None) (0,Some(1)) (1,Some(1)) (2,Some(2)) (3,Some(3)) (4,Some(5)) (5,Some(8))
Scheme
This uses named let to create a function (aux) that only exists inside of fibonacci:
(define (fibonacci n)
(if (> 0 n)
"Error: argument must not be negative."
(let aux ((a 1) (b 0) (count n))
(if (= count 0)
b
(aux (+ a b) a (- count 1))))))
(map fibonacci '(1 2 3 4 5 6 7 8 9 10))
- Output:
'(1 1 2 3 5 8 13 21 34 55)
Seed7
Uses a local function to do the dirty work. The local function has a name, but it is not in the global namespace.
$ include "seed7_05.s7i";
const func integer: fib (in integer: x) is func
result
var integer: fib is 0;
local
const func integer: fib1 (in integer: n) is func
result
var integer: fib1 is 0;
begin
if n < 2 then
fib1 := n;
else
fib1 := fib1(n-2) + fib1(n-1);
end if;
end func;
begin
if x < 0 then
raise RANGE_ERROR;
else
fib := fib1(x);
end if;
end func;
const proc: main is func
local
var integer: i is 0;
begin
for i range 0 to 4 do
writeln(fib(i));
end for;
end func;
- Output:
0 1 1 2 3
Sidef
__FUNC__ refers to the current function.
func fib(n) {
return NaN if (n < 0)
func (n) {
n < 2 ? n
: (__FUNC__(n-1) + __FUNC__(n-2))
}(n)
}
__BLOCK__ refers to the current block.
func fib(n) {
return NaN if (n < 0)
{|n|
n < 2 ? n
: (__BLOCK__(n-1) + __BLOCK__(n-2))
}(n)
}
Smalltalk
In Smalltalk, things are referred to by a name, so the following may not fully qualify as solutions.
Also: doing things like this is not considered "good style" (give things a good name to make the meaning obvious).
Notice, that none of the two solutions below pollutes any namespace; in (a), the variable introduced is strictly local to the method, in (b) not even a method-local is introduced (so maybe (b) does qualify, after all).
a) Use a funny local name (in this case: "_"). Here the closure is defined as "_", and then evaluated (by sending it a value: message).
myMethodComputingFib:arg
|_|
^ (_ := [:n | n <= 1
ifTrue:[n]
ifFalse:[(_ value:(n - 1))+(_ value:(n - 2))]]
) value:arg.
b) Define it in a local scope to not infect the outer scopes.
Here, a separate closure is defined (and evaluated with value), in which fib is defined and evaluated with the argument.
This is semantically equivalent to the named let solution of Scheme.
myMethodComputingFib2:arg
^ [
|fib|
[:n | n <= 1
ifTrue:[1]
ifFalse:[(fib value:(n - 1))+(fun value:(n - 2))]] value:arg.
] value.
To completely make it anonymous, we could use reflection to get at the current executed block (via thisContext), but that is too ugly and obfuscating to be shown here.
Sparkling
As a function expression:
function(n, f) {
return f(n, f);
}(10, function(n, f) {
return n < 2 ? 1 : f(n - 1, f) + f(n - 2, f);
})
When typed into the REPL:
spn:1> function(n, f) { return f(n, f); }(10, function(n, f) { return n < 2 ? 1 : f(n - 1, f) + f(n - 2, f); })
= 89
Standard ML
ML does not have a built-in construct for anonymous recursion, but you can easily write your own fix-point combinator:
fun fix f x = f (fix f) x
fun fib n =
if n < 0 then raise Fail "Negative"
else
fix (fn fib =>
(fn 0 => 0
| 1 => 1
| n => fib (n-1) + fib (n-2))) n
Instead of using a fix-point, the more common approach is to locally define a recursive function and call it once:
fun fib n =
let
fun fib 0 = 0
| fib 1 = 1
| fib n = fib (n-1) + fib (n-2)
in
if n < 0 then
raise Fail "Negative"
else
fib n
end
In this example the local function has the same name as the outer function. This is fine: the local definition shadows the outer definition, so the line "fib n" will refer to our helper function.
Another variation is possible. Instead, we could define the recursive "fib" at top-level, then shadow it with a non-recursive wrapper. To force the wrapper to be non-recursive, we use the "val" syntax instead of "fun":
fun fib 0 = 0
| fib 1 = 1
| fib n = fib (n-1) + fib (n-2)
val fib = fn n => if n < 0 then raise Fail "Negative"
else fib n
SuperCollider
SuperCollider has a keyword "thisFunction", which refers to the current function context. The example below uses this for anonymous recursion. One may think that "thisFunction" would refer to the second branch of the if statement, but because if statements are inlined, the function is the outer one.
(
f = { |n|
if(n >= 0) {
if(n < 2) { n } { thisFunction.(n-1) + thisFunction.(n-2) }
}
};
(0..20).collect(f)
)
Swift
- With internal named recursive closure
let fib: Int -> Int = {
func f(n: Int) -> Int {
assert(n >= 0, "fib: no negative numbers")
return n < 2 ? 1 : f(n-1) + f(n-2)
}
return f
}()
print(fib(8))
let fib: Int -> Int = {
var f: (Int -> Int)!
f = { n in
assert(n >= 0, "fib: no negative numbers")
return n < 2 ? 1 : f(n-1) + f(n-2)
}
return f
}()
println(fib(8))
- Using Y combinator
struct RecursiveFunc<F> {
let o : RecursiveFunc<F> -> F
}
func y<A, B>(f: (A -> B) -> A -> B) -> A -> B {
let r = RecursiveFunc<A -> B> { w in f { w.o(w)($0) } }
return r.o(r)
}
func fib(n: Int) -> Int {
assert(n >= 0, "fib: no negative numbers")
return y {f in {n in n < 2 ? 1 : f(n-1) + f(n-2)}} (n)
}
println(fib(8))
Tailspin
See the actual fibonacci solution Fibonacci_sequence#State_machine
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.
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
}
Demonstrating:
puts [fib 12]
- Output:
}
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:
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
}
However, we can create a recurse
function that makes this much more straight-forward:
# 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
}
True BASIC
FUNCTION Fibonacci (num)
IF num < 0 THEN
PRINT "Invalid argument: ";
LET Fibonacci = num
END IF
IF num < 2 THEN
LET Fibonacci = num
ELSE
LET Fibonacci = Fibonacci(num - 1) + Fibonacci(num - 2)
END IF
END FUNCTION
PRINT Fibonacci(20)
PRINT Fibonacci(30)
PRINT Fibonacci(-10)
PRINT Fibonacci(10)
END
- Output:
Igual que la entrada de BASIC256.
TXR
For the Y combinator approach in TXR, see the Y combinator task.
The following easy transliteration of one of the Common Lisp solutions shows the conceptual and cultural compatibility between TXR Lisp macros and CL macros:
(defmacro recursive ((. parm-init-pairs) . body)
(let ((hidden-name (gensym "RECURSIVE-")))
^(macrolet ((recurse (. args) ^(,',hidden-name ,*args)))
(labels ((,hidden-name (,*[mapcar first parm-init-pairs]) ,*body))
(,hidden-name ,*[mapcar second parm-init-pairs])))))
(defun fib (number)
(if (< number 0)
(error "Error. The number entered: ~a is negative" number)
(recursive ((n number) (a 0) (b 1))
(if (= n 0)
a
(recurse (- n 1) b (+ a b))))))
(put-line `fib(10) = @(fib 10)`)
(put-line `fib(-1) = @(fib -1)`))
- Output:
$ txr anonymous-recursion.txr fib(10) = 55 txr: unhandled exception of type error: txr: possibly triggered by anonymous-recursion.txr:9 txr: Error. The number entered: -1 is negative Aborted (core dumped)
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.
fib() {
if test 0 -gt "$1"; then
echo "fib: fib of negative" 1>&2
return 1
else
(
fib2() {
if test 2 -gt "$1"; then
echo "$1"
else
echo $(( $(fib2 $(($1 - 1)) ) + $(fib2 $(($1 - 2)) ) ))
fi
}
fib2 "$1"
)
fi
}
$ 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
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
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.
UTFool
Solution with anonymous class
···
http://rosettacode.org/wiki/Anonymous_recursion
···
⟦import java.util.function.UnaryOperator;⟧
■ AnonymousRecursion
§ static
▶ main
• args⦂ String[]
if 0 > Integer.valueOf args[0]
System.out.println "negative argument"
else
System.out.println *UnaryOperator⟨Integer⟩° ■
▶ apply⦂ Integer
• n⦂ Integer
⏎ n ≤ 1 ? n ! (apply n - 1) + (apply n - 2)
°.apply Integer.valueOf args[0]
VBA
Sub Main()
Debug.Print F(-10)
Debug.Print F(10)
End Sub
Private Function F(N As Long) As Variant
If N < 0 Then
F = "Error. Negative argument"
ElseIf N <= 1 Then
F = N
Else
F = F(N - 1) + F(N - 2)
End If
End Function
- Output:
Error. Negative argument 55
Wart
def (fib n)
if (n >= 0)
(transform n :thru (afn (n)
(if (n < 2)
n
(+ (self n-1)
(self n-2)))))
afn
creates an anonymous function that can be recursed by calling self
.
WDTE
let str => 'strings';
let fib n => switch n {
< 0 => str.format 'Bad argument: {q}' n;
default => n -> (@ memo s n => switch n {
== 0 => 0; == 1 => 1;
default => + (s (- n 1)) (s (- n 2));
});
};
In WDTE, a lambda, defined in a block delineated by (@)
, gets passed itself as its first argument, allowing for recursion.
Wren
class Fibonacci {
static compute(n) {
var fib
fib = Fn.new {|n|
if (n < 2) return n
return fib.call(n - 1) + fib.call(n - 2)
}
if (n < 0) return null
return fib.call(n)
}
}
System.print(Fibonacci.compute(36))
- Output:
14930352
x86 Assembly
32 bit
Fakes the actual first call to the function that generates Fibonacci numbers. The address of the instructions after the function get put on the stack and then execution continues into the actual function. When the recursion is complete, instead of returning to the location of the call it goes to the end of the loop.
; Calculates and prints Fibonacci numbers (Fn)
; Prints numbers 1 - 47 (largest 32bit Fn that fits)
; Build:
; nasm -felf32 fib.asm
; ld -m elf32_i386 fib.o -o fib
global _start
section .text
_start:
mov ecx, 48 ; Initialize loop counter
.loop:
mov ebx, 48 ; Calculate which Fn will be computed
sub ebx, ecx ; Takes into account the reversed nature
push ebx ; Pass the parameter in on the stack
push .done ; Emulate a call but "return" to end of loop
; The return adress is manually set on the stack
; int fib (int n)
; Returns the n'th Fn
; fib(n) = 0 if n <= 0
; 1 if n == 1
; fib(n-1) + fib(n-2) otherwise
.fib:
push ebp ; Setup stack frame
mov ebp, esp
push ebx ; Save needed registers
xor eax, eax
mov ebx, [ebp + 8] ; Get the parameter
cmp ebx, 1 ; Test for base cases
jl .return
mov eax, 1
je .return
dec ebx ; Calculate fib(n-1)
push ebx
call .fib
mov [esp], eax ; Save result on top of parameter in stack
dec ebx ; Calculate fib(n-2)
push ebx
call .fib
add eax, [esp + 4] ; Add the first to the second
add esp, 8 ; Reset local stack
.return:
pop ebx ; Restore modified registers
mov esp, ebp ; Tear down stack frame and return
pop ebp
ret
.done:
mov [esp], ecx ; Save the counter between calls
push eax ; Print the number
call print_num
add esp, 4
pop ecx ; Restore the loop counter
loop .loop ; Loop until 0
mov eax, 0x01 ; sys_exit(int error)
xor ebx, ebx ; error = 0 (success)
int 0x80 ; syscall
; void print_num (int n)
; Prints an integer and newline
print_num:
push ebp
mov ebp, esp
sub esp, 11 ; Save space for digits and newline
lea ecx, [ebp - 1] ; Save a pointer to after the buffer
mov BYTE [ecx], 0x0A ; Set the newline at the end
mov eax, [ebp + 8] ; Get the parameter
mov ebx, DWORD 10 ; Divisor
.loop:
dec ecx ; Move pointer to next digit
xor edx, edx
div ebx ; Extract one digit, quot in eax, rem in edx
add dl, 0x30 ; Convert remainder to ascii
mov [ecx], dl ; Save the ascii form
cmp eax, 0 ; Loop until all digits have been converted
jg .loop
mov eax, 0x04 ; sys_write(int fd, char **buf, int len)
mov ebx, 1 ; stdout
mov edx, ebp ; Calculate the length
sub edx, ecx ; address after newline - address of first digit
int 0x80
mov esp, ebp
pop ebp
ret
XPL0
In XPL0 you can nest functions/procedures inside other functions/procedures up to eight levels deep. This makes those nested functions invisible to the outside, thus preventing namespace pollution.
include c:\cxpl\codes;
func Fib(X);
int X;
func ActualFib(N);
int N;
[if N<2 then return N
else return ActualFib(N-1) + ActualFib(N-2);
]; \ActualFib;
[if X<0 then [Text(0, "Error "); return 0]
else return ActualFib(X);
]; \Fib;
[IntOut(0, Fib(8)); CrLf(0);
IntOut(0, Fib(-2)); CrLf(0);
]
- Output:
21 Error 0
Yabasic
print Fibonacci(-10)
print Fibonacci(10)
sub Fibonacci(number)
If number < 0 print "Invalid argument: "; : return number
If number < 2 Then
Return number
Else
Return Fibonacci(number - 1) + Fibonacci(number - 2)
EndIf
end sub
zkl
fcn fib(n){
if (n<0) throw(Exception.ValueError);
fcn(n){
if (n < 2) return(1);
else return(self.fcn(n-1) + self.fcn(n-2));
}(n);
}
fib(8) .println();
fib(-8).println();
- Output:
34 ValueError thrown
ZX Spectrum Basic
10 INPUT "Enter a number: ";n
20 LET t=0
30 GO SUB 60
40 PRINT t
50 STOP
60 LET nold1=1: LET nold2=0
70 IF n<0 THEN PRINT "Positive argument required!": RETURN
80 IF n=0 THEN LET t=nold2: RETURN
90 IF n=1 THEN LET t=nold1: RETURN
100 LET t=nold2+nold1
110 IF n>2 THEN LET n=n-1: LET nold2=nold1: LET nold1=t: GO SUB 100
120 RETURN
- Programming Tasks
- Recursion
- 11l
- Ada
- ALGOL 68
- APL
- AppleScript
- Arturo
- AutoHotkey
- AutoIt
- Axiom
- BASIC
- BaCon
- BASIC256
- Chipmunk Basic
- BBC BASIC
- IS-BASIC
- Bracmat
- BQN
- C
- C sharp
- C++
- Clio
- Clojure
- CoffeeScript
- Common Lisp
- D
- Dylan
- Déjà Vu
- Delphi
- EchoLisp
- Ela
- Elena
- Elixir
- EMal
- Erlang
- F Sharp
- Factor
- Falcon
- FBSL
- Forth
- Fortran
- FreeBASIC
- Fōrmulæ
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Io
- J
- Java
- JavaScript
- Joy
- Jq
- Julia
- K
- Klingphix
- Klong
- Kotlin
- Lambdatalk
- Lang
- Lingo
- LOLCODE
- Lua
- M2000 Interpreter
- Maple
- Mathematica
- Wolfram Language
- MATLAB
- Nemerle
- Nim
- Objective-C
- OCaml
- Ol
- OxygenBasic
- PARI/GP
- Pascal
- PascalABC.NET
- Perl
- Phix
- Phix/Class
- PHP
- PicoLisp
- PostScript
- Initlib
- Prolog
- Python
- QBasic
- Qi
- Quackery
- R
- Racket
- Raku
- REBOL
- REXX
- Ring
- RPL
- Ruby
- Continuation
- Rust
- Scala
- Scheme
- Seed7
- Sidef
- Smalltalk
- Sparkling
- Standard ML
- SuperCollider
- Swift
- Tailspin
- Tcl
- True BASIC
- TXR
- UNIX Shell
- Ursala
- UTFool
- VBA
- Wart
- WDTE
- Wren
- X86 Assembly
- XPL0
- Yabasic
- Zkl
- ZX Spectrum Basic
- ACL2/Omit
- Euphoria/Omit
- PureBasic/Omit
- Stata/Omit
- Pages with too many expensive parser function calls