Fibonacci sequence
You are encouraged to solve this task according to the task description, using any language you may know.
The Fibonacci sequence is a sequence Fn of natural numbers defined recursively:
F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2, if n>1
Write a function to generate the nth Fibonacci number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).
The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition:
Fn = Fn+2 - Fn+1, if n<0
Support for negative n in the solution is optional.
References:
ActionScript
<lang actionscript>public function fib(n:uint):uint {
if (n < 2)
return n;
return fib(n - 1) + fib(n - 2);
}</lang>
AppleScript
<lang applescript>set fibs to {} set x to (text returned of (display dialog "What fibbonaci number do you want?" default answer "3")) set x to x as integer repeat with y from 1 to x if (y = 1 or y = 2) then copy 1 to the end of fibs else copy ((item (y - 1) of fibs) + (item (y - 2) of fibs)) to the end of fibs end if end repeat return item x of fibs</lang>
Ada
<lang ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Fibonacci is
function Fibonacci (N : Natural) return Natural is
This : Natural := 0;
That : Natural := 1;
Sum : Natural;
begin
for I in 1..N loop
Sum := This + That;
That := This;
This := Sum;
end loop;
return This;
end Fibonacci;
begin
for N in 0..10 loop
Put_Line (Positive'Image (Fibonacci (N)));
end loop;
end Test_Fibonacci;</lang> Sample output:
0 1 1 2 3 5 8 13 21 34 55
ALGOL 68
Analytic
<lang algol68>PROC analytic fibonacci = (LONG INT n)LONG INT:(
LONG REAL sqrt 5 = long sqrt(5); LONG REAL p = (1 + sqrt 5) / 2; LONG REAL q = 1/p; ROUND( (p**n + q**n) / sqrt 5 )
);
FOR i FROM 1 TO 30 WHILE
print(whole(analytic fibonacci(i),0));
- WHILE # i /= 30 DO
print(", ")
OD; print(new line)</lang> Output:
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
Iterative
<lang algol68>PROC iterative fibonacci = (INT n)INT:
CASE n+1 IN
0, 1, 1, 2, 3, 5
OUT
INT even:=3, odd:=5;
FOR i FROM odd+1 TO n DO
(ODD i|odd|even) := odd + even
OD;
(ODD n|odd|even)
ESAC;
FOR i FROM 0 TO 30 WHILE
print(whole(iterative fibonacci(i),0));
- WHILE # i /= 30 DO
print(", ")
OD; print(new line)</lang> Output:
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
Recursive
<lang algol68>PROC recursive fibonacci = (INT n)INT:
( n < 2 | n | fib(n-1) + fib(n-2));</lang>
Generative
- note: This specimen retains the original Python coding style.
<lang algol68>MODE YIELDINT = PROC(INT)VOID;
PROC gen fibonacci = (INT n, YIELDINT yield)VOID: (
INT even:=0, odd:=1; yield(even); yield(odd); FOR i FROM odd+1 TO n DO yield( (ODD i|odd|even) := odd + even ) OD
);
main:(
# FOR INT n IN # gen fibonacci(30, # ) DO ( #
## (INT n)VOID:(
print((" ",whole(n,0)))
# OD # ));
print(new line)
)</lang> Output:
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
Array (Table) Lookup
This uses a pre-generated list, requiring much less run-time processor usage, but assumes that INT is only 31 bits wide. <lang algol68>[]INT const fibonacci = []INT( -1836311903, 1134903170,
-701408733, 433494437, -267914296, 165580141, -102334155, 63245986, -39088169, 24157817, -14930352, 9227465, -5702887, 3524578, -2178309, 1346269, -832040, 514229, -317811, 196418, -121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181, -2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13, -8, 5, -3, 2, -1, 1, 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, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903
)[@-46];
PROC VOID value error := stop;
PROC lookup fibonacci = (INT i)INT: (
IF LWB const fibonacci <= i AND i<= UPB const fibonacci THEN const fibonacci[i] ELSE value error; SKIP FI
);
FOR i FROM 0 TO 30 WHILE
print(whole(lookup fibonacci(i),0));
- WHILE # i /= 30 DO
print(", ")
OD; print(new line)</lang> Output:
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
AutoHotkey
Search autohotkey.com: sequence
Iterative
<lang AutoHotkey>Loop, 5
MsgBox % fib(A_Index)
Return
fib(n) {
If (n < 2)
Return n
i := last := this := 1
While (i <= n)
{
new := last + this
last := this
this := new
i++
}
Return this
}</lang>
Recursive and iterative
Source: AutoHotkey forum by Laszlo <lang AutoHotkey>/* Important note: the recursive version would be very slow without a global or static array. The iterative version handles also negative arguments properly.
- /
FibR(n) { ; n-th Fibonacci number (n>=0, recursive with static array Fibo)
Static Return n<2 ? n : Fibo%n% ? Fibo%n% : Fibo%n% := FibR(n-1)+FibR(n-2)
}
Fib(n) { ; n-th Fibonacci number (n < 0 OK, iterative)
a := 0, b := 1
Loop % abs(n)-1
c := b, b += a, a := c
Return n=0 ? 0 : n>0 || n&1 ? b : -b
}</lang>
AutoIt
Iterative
<lang AutoIt>#AutoIt Version: 3.2.10.0 $n0 = 0 $n1 = 1 $n = 10 MsgBox (0,"Iterative Fibonacci ", it_febo($n0,$n1,$n))
Func it_febo($n_0,$n_1,$N)
$first = $n_0
$second = $n_1
$next = $first + $second
$febo = 0
For $i = 1 To $N-3
$first = $second
$second = $next
$next = $first + $second
Next
if $n==0 Then
$febo = 0
ElseIf $n==1 Then
$febo = $n_0
ElseIf $n==2 Then
$febo = $n_1
Else
$febo = $next
EndIf
Return $febo
EndFunc </lang>
Recursive
<lang AutoIt>#AutoIt Version: 3.2.10.0 $n0 = 0 $n1 = 1 $n = 10 MsgBox (0,"Recursive Fibonacci ", rec_febo($n0,$n1,$n)) Func rec_febo($r_0,$r_1,$R)
if $R<3 Then
if $R==2 Then
Return $r_1
ElseIf $R==1 Then
Return $r_0
ElseIf $R==0 Then
Return 0
EndIf
Return $R
Else
Return rec_febo($r_0,$r_1,$R-1) + rec_febo($r_0,$r_1,$R-2)
EndIf
EndFunc </lang>
AWK
As in many examples, this one-liner contains the function as well as testing with input from stdin, output to stdout. <lang awk>$ awk 'func fib(n){return(n<2?n:fib(n-1)+fib(n-2))}{print "fib("$1")="fib($1)}' 10 fib(10)=55</lang>
BASIC
Iterative
<lang qbasic>FUNCTION itFib (n)
n1 = 0
n2 = 1
FOR k = 1 TO ABS(n)
sum = n1 + n2
n1 = n2
n2 = sum
NEXT k
IF n < 0 THEN
itFib = n1 * ((-1) ^ ((-n) + 1))
ELSE
itFib = n1
END IF
END FUNCTION</lang>
This version calculates each value once, as needed, and stores the results in an array for later retreival. (Due to the use of REDIM PRESERVE, it requires QuickBASIC 4.5 or newer.)
<lang qbasic>DECLARE FUNCTION fibonacci& (n AS INTEGER)
REDIM SHARED fibNum(1) AS LONG
fibNum(1) = 1
'*****sample inputs***** PRINT fibonacci(0) 'no calculation needed PRINT fibonacci(13) 'figure F(2)..F(13) PRINT fibonacci(-42) 'figure F(14)..F(42) PRINT fibonacci(47) 'error: too big '*****sample inputs*****
FUNCTION fibonacci& (n AS INTEGER)
DIM a AS INTEGER
a = ABS(n)
SELECT CASE a
CASE 0 TO 46
SHARED fibNum() AS LONG
DIM u AS INTEGER, L0 AS INTEGER
u = UBOUND(fibNum)
IF a > u THEN
REDIM PRESERVE fibNum(a) AS LONG
FOR L0 = u + 1 TO a
fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2)
NEXT
END IF
IF n < 0 THEN
fibonacci = fibNum(a) * ((-1) ^ (a + 1))
ELSE
fibonacci = fibNum(n)
END IF
CASE ELSE
'limited to signed 32-bit int (LONG)
'F(47)=&hB11924E1
ERROR 6 'overflow
END SELECT
END FUNCTION</lang>
Outputs (unhandled error in final input prevents output):
0 233 -267914296
Recursive
This example can't handle n < 0.
<lang qbasic>FUNCTION recFib (n)
IF (n < 2) THEN
recFib = n
ELSE
recFib = recFib(n - 1) + recFib(n - 2)
END IF
END FUNCTION</lang>
Array (Table) Lookup
This uses a pre-generated list, requiring much less run-time processor usage. (Since the sequence never changes, this is probably the best way to do this in "the real world". The same applies to other sequences like prime numbers, and numbers like pi and e.)
<lang qbasic>DATA -1836311903,1134903170,-701408733,433494437,-267914296,165580141,-102334155 DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309 DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711 DATA 10946,-6765,4181,-2584,1597,-987,610,-377,233,-144,89,-55,34,-21,13,-8,5,-3 DATA 2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765 DATA 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269 DATA 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986 DATA 102334155,165580141,267914296,433494437,701408733,1134903170,1836311903
DIM fibNum(-46 TO 46) AS LONG
FOR n = -46 TO 46
READ fibNum(n)
NEXT
'*****sample inputs***** FOR n = -46 TO 46
PRINT fibNum(n),
NEXT PRINT '*****sample inputs*****</lang>
Batch File
Recursive version <lang dos>::fibo.cmd @echo off if "%1" equ "" goto :eof call :fib %1 echo %errorlevel% goto :eof
- fib
setlocal enabledelayedexpansion if %1 geq 2 goto :ge2 exit /b %1
- ge2
set /a r1 = %1 - 1 set /a r2 = %1 - 2 call :fib !r1! set r1=%errorlevel% call :fib !r2! set r2=%errorlevel% set /a r0 = r1 + r2 exit /b !r0!</lang>
Output:
>for /L %i in (1,5,20) do fibo.cmd %i >fibo.cmd 1 1 >fibo.cmd 6 8 >fibo.cmd 11 89 >fibo.cmd 16 987
bc
iterative
<lang bc>#! /usr/bin/bc -q
define fib(x) {
if (x <= 0) return 0; if (x == 1) return 1;
a = 0;
b = 1;
for (i = 1; i < x; i++) {
c = a+b; a = b; b = c;
}
return c;
} fib(1000) quit</lang>
Befunge
<lang befunge>00:.1:.>:"@"8**++\1+:67+`#@_v
^ .:\/*8"@"\%*8"@":\ <</lang>
Brainf***
The first cell contains n (10), the second cell will contain fib(n) (55), and the third cell will contain fib(n-1) (34). <lang bf>++++++++++ >>+<<[->[->+>+<<]>[-<+>]>[-<+>]<<<]</lang>
The following generates n fibonacci numbers and prints them, though not in ascii. It does have a limit due to the cells usually being 1 byte in size. <lang bf>+++++ +++++ #0 set to n >> + Init #2 to 1 << [ - #Decrement counter in #0 >>. Notice: This doesn't print it in ascii To look at results you can pipe into a file and look with a hex editor
Copying sequence to save #2 in #4 using #5 as restore space >>[-] Move to #4 and clear >[-] Clear #5 <<< #2 [ Move loop - >> + > + <<< Subtract #2 and add #4 and #5 ] >>> [ Restore loop - <<< + >>> Subtract from #5 and add to #2 ]
<<<< Back to #1 Non destructive add sequence using #3 as restore value [ Loop to add - > + > + << Subtract #1 and add to value #2 and restore space #3 ] >> [ Loop to restore #1 from #3 - << + >> Subtract from restore space #3 and add in #1 ]
<< [-] Clear #1 >>> [ Loop to move #4 to #1 - <<< + >>> Subtract from #4 and add to #1 ] <<<< Back to #0 ]</lang>
Bracmat
Recursive
<lang bracmat>fib=.!arg:<2|fib$(!arg+-2)+fib$(!arg+-1)</lang>
fib$30 832040
Iterative
<lang bracmat>(fib=
last i this new
. !arg:<2
| 0:?last:?i
& 1:?this
& whl
' ( !i+1:<!arg:?i
& !last+!this:?new
& !this:?last
& !new:?this
)
& !this
)</lang>
fib$777 1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082
Brat
Recursive
<lang brat>fibonacci = { x |
true? x < 2, x, { fibonacci(x - 1) + fibonacci(x - 2) }
}</lang>
Tail Recursive
<lang brat>fib_aux = { x, next, result |
true? x == 0,
result,
{ fib_aux x - 1, next + result, next }
}
fibonacci = { x |
fib_aux x, 1, 0
}</lang>
Memoization
<lang brat>cache = hash.new
fibonacci = { x |
true? cache.key?(x)
{ cache[x] }
{true? x < 2, x, { cache[x] = fibonacci(x - 1) + fibonacci(x - 2) }}
}</lang>
C
Recursive
<lang c>long long unsigned fib(unsigned n) {
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}</lang>
Iterative
<lang c>long long unsigned fib(unsigned n) {
long long unsigned last = 0, this = 1, new, i;
if (n < 2) return n;
for (i = 1 ; i < n ; ++i) {
new = last + this;
last = this;
this = new;
}
return this;
}</lang>
Analytic
<lang c>#include <tgmath.h>
- define PHI ((1 + sqrt(5))/2)
long long unsigned fib(unsigned n) {
return floor( (pow(PHI, n) - pow(1 - PHI, n))/sqrt(5) );
}</lang>
Generative
<lang c>#include <stdio.h> typedef enum{false=0, true=!0} bool; typedef void iterator;
- include <setjmp.h>
/* declare label otherwise it is not visible in sub-scope */
- define LABEL(label) jmp_buf label; if(setjmp(label))goto label;
- define GOTO(label) longjmp(label, true)
/* the following line is the only time I have ever required "auto" */
- define FOR(i, iterator) { auto bool lambda(i); yield_init = (void *)λ iterator; bool lambda(i)
- define DO {
- define YIELD(x) if(!yield(x))return
- define BREAK return false
- define CONTINUE return true
- define OD CONTINUE; } }
static volatile void *yield_init; /* not thread safe */
- define YIELDS(type) bool (*yield)(type) = yield_init
iterator fibonacci(int stop){
YIELDS(int);
int f[] = {0, 1};
int i;
for(i=0; i<stop; i++){
YIELD(f[i%2]);
f[i%2]=f[0]+f[1];
}
}
main(){
printf("fibonacci: ");
FOR(int i, fibonacci(16)) DO
printf("%d, ",i);
OD;
printf("...\n");
}</lang> Output:
fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
C++
Using unsigned int, this version only works up to 48 before fib overflows. <lang cpp>#include <iostream>
int main() {
unsigned int a = 1, b = 1;
unsigned int target = 48;
for(unsigned int n = 3; n <= target; ++n)
{
unsigned int fib = a + b;
std::cout << "F("<< n << ") = " << fib << std::endl;
a = b;
b = fib;
}
return 0;
}</lang>
This version does not have an upper bound.
<lang cpp>#include <iostream>
- include <gmpxx.h>
int main() {
mpz_class a = mpz_class(1), b = mpz_class(1);
mpz_class target = mpz_class(100);
for(mpz_class n = mpz_class(3); n <= target; ++n)
{
mpz_class fib = b + a;
if ( fib < b )
{
std::cout << "Overflow at " << n << std::endl;
break;
}
std::cout << "F("<< n << ") = " << fib << std::endl;
a = b;
b = fib;
}
return 0;
}</lang>
Version using transform: <lang cpp>#include <algorithm>
- include <vector>
- include <functional>
- include <iostream>
unsigned int fibonacci(unsigned int n) {
if (n == 0) return 0; std::vector<int> v(n+1); v[1] = 1; transform(v.begin(), v.end()-2, v.begin()+1, v.begin()+2, std::plus<int>()); // "v" now contains the Fibonacci sequence from 0 up return v[n];
}</lang>
Far-fetched version using adjacent_difference: <lang cpp>#include <numeric>
- include <vector>
- include <functional>
- include <iostream>
unsigned int fibonacci(unsigned int n) {
if (n == 0) return 0; std::vector<int> v(n, 1); adjacent_difference(v.begin(), v.end()-1, v.begin()+1, std::plus<int>()); // "array" now contains the Fibonacci sequence from 1 up return v[n-1];
} </lang>
Version which computes at compile time with metaprogramming: <lang cpp>#include <iostream>
template <int n> struct fibo {
enum {value=fibo<n-1>::value+fibo<n-2>::value};
};
template <> struct fibo<0> {
enum {value=0};
};
template <> struct fibo<1> {
enum {value=1};
};
int main(int argc, char const *argv[])
{
std::cout<<fibo<12>::value<<std::endl; std::cout<<fibo<46>::value<<std::endl; return 0;
}</lang>
The following version is based on fast exponentiation: <lang cpp>#include <iostream>
inline void fibmul(int* f, int* g) {
int tmp = f[0]*g[0] + f[1]*g[1]; f[1] = f[0]*g[1] + f[1]*(g[0] + g[1]); f[0] = tmp;
}
int fibonacci(int n) {
int f[] = { 1, 0 };
int g[] = { 0, 1 };
while (n > 0)
{
if (n & 1) // n odd
{
fibmul(f, g);
--n;
}
else
{
fibmul(g, g);
n >>= 1;
}
}
return f[1];
}
int main() {
for (int i = 0; i < 20; ++i) std::cout << fibonacci(i) << " "; std::cout << std::endl;
}</lang> Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
C#
Recursive
<lang csharp>static long recFib(int n) {
if (n < 2) return n; return recFib(n - 1) + recFib(n - 2);
}</lang>
Cat
<lang cat>define fib {
dup 1 <= [] [dup 1 - fib swap 2 - fib +] if
}</lang>
Chef
<lang chef>Stir-Fried Fibonacci Sequence.
An unobfuscated iterative implementation. It prints the first N + 1 Fibonacci numbers, where N is taken from standard input.
Ingredients. 0 g last 1 g this 0 g new 0 g input
Method. Take input from refrigerator. Put this into 4th mixing bowl. Loop the input. Clean the 3rd mixing bowl. Put last into 3rd mixing bowl. Add this into 3rd mixing bowl. Fold new into 3rd mixing bowl. Clean the 1st mixing bowl. Put this into 1st mixing bowl. Fold last into 1st mixing bowl. Clean the 2nd mixing bowl. Put new into 2nd mixing bowl. Fold this into 2nd mixing bowl. Put new into 4th mixing bowl. Endloop input until looped. Pour contents of the 4th mixing bowl into baking dish.
Serves 1.</lang>
CMake
Iteration uses a while() loop. Memoization uses global properties.
<lang cmake>set_property(GLOBAL PROPERTY fibonacci_0 0) set_property(GLOBAL PROPERTY fibonacci_1 1) set_property(GLOBAL PROPERTY fibonacci_next 2)
- var = nth number in Fibonacci sequence.
function(fibonacci var n)
# If the sequence is too short, compute more Fibonacci numbers.
get_property(next GLOBAL PROPERTY fibonacci_next)
if(NOT next GREATER ${n})
# a, b = last 2 Fibonacci numbers
math(EXPR i "${next} - 2")
get_property(a GLOBAL PROPERTY fibonacci_${i})
math(EXPR i "${next} - 1")
get_property(b GLOBAL PROPERTY fibonacci_${i})
while(NOT next GREATER ${n})
math(EXPR i "${a} + ${b}") # i = next Fibonacci number
set_property(GLOBAL PROPERTY fibonacci_${next} ${i})
set(a ${b})
set(b ${i})
math(EXPR next "${next} + 1")
endwhile()
set_property(GLOBAL PROPERTY fibonacci_next ${next})
endif()
get_property(answer GLOBAL PROPERTY fibonacci_${n})
set(${var} ${answer} PARENT_SCOPE)
endfunction(fibonacci)</lang>
<lang cmake># Test program: print 0th to 9th and 25th to 30th Fibonacci numbers. set(s "") foreach(i RANGE 0 9)
fibonacci(f ${i})
set(s "${s} ${f}")
endforeach(i) set(s "${s} ... ") foreach(i RANGE 25 30)
fibonacci(f ${i})
set(s "${s} ${f}")
endforeach(i) message(${s})</lang>
0 1 1 2 3 5 8 13 21 34 ... 75025 121393 196418 317811 514229 832040
Clojure
This is implemented idiomatically as an infinitely long, lazy sequence of all Fibonacci numbers: <lang Clojure>(defn fibs []
(map first (iterate (fn a b [b (+ a b)]) [0 1])))</lang>
Thus to get the nth one: <lang Clojure>(nth (fibs) 5)</lang> So long as one does not hold onto the head of the sequence, this is unconstrained by length.
The one-line implementation may look confusing at first, but on pulling it apart it actually solves the problem more "directly" than a more explicit looping construct. <lang Clojure>(defn fibs []
(map first ;; throw away the "metadata" (see below) to view just the fib numbers
(iterate ;; create an infinite sequence of [prev, curr] pairs
(fn a b ;; to produce the next pair, call this function on the current pair
[b (+ a b)]) ;; new prev is old curr, new curr is sum of both previous numbers
[0 1]))) ;; recursive base case: prev 0, curr 1</lang>
A more elegant solution is inspired by the Haskell implementation of an infinite list of Fibonacci numbers: <lang Clojure>(def fib (lazy-cat [0 1] (map + fib (rest fib))))</lang> Then, to see the first ten, <lang Clojure>user> (take 10 fib) (0 1 1 2 3 5 8 13 21 34)</lang>
CoffeeScript
Analytic
<lang coffeescript>fib_ana = (n) ->
sqrt = Math.sqrt phi = ((1 + sqrt(5))/2) return Math.round((Math.pow(phi, n)/sqrt(5)))</lang>
Iterative
<lang coffeescript>fib_iter = (n) ->
if n < 2
return n
[prev, curr] = 0, 1
for i in [1..n]
[prev, curr] = [curr, curr + prev]
return curr</lang>
Recursive
<lang coffeescript>fib_rec = (n) ->
if n < 2
return n
else
return fib_rec(n-1) + fib_rec(n-2)</lang>
Common Lisp
Note that Common Lisp uses bignums, so this will never overflow.
<lang lisp>(defun fibonacci-recursive (n)
(if (< n 2)
n
(+ (fibonacci-recursive (- n 2)) (fibonacci-recursive (- n 1)))))</lang>
<lang lisp>(defun fibonacci-iterative (n)
(if (< n 2)
n
(let ((result 0)
(a 1)
(b 1))
(loop for n from (- n 2) downto 1
do (setq result (+ a b)
a b
b result))
result)))</lang>
<lang lisp>(defun fibonacci-tail-recursive ( n &optional (a 0) (b 1))
(if (= n 0)
b
(fibonacci-tail-recursive (- n 1) b (+ a b))))</lang>
Tail recursive and squaring: <lang lisp>(defun fib (n &optional (a 1) (b 0) (p 0) (q 1))
(cond ((zerop n) b)
((evenp n) (fib (/ n 2) a b (+ (* p p) (* q q)) (+ (* q q) (* 2 p q)))) (t (fib (1- n) (+ (* b q) (* a (+ p q))) (+ (* b p) (* a q)) p q))))
(print (fib 100000))</lang>
Not a function, just printing out the entire (for some definition of "entire") sequence with a for var = loop:<lang lisp>(loop for x = 0 then y and y = 1 then (+ x y) do (print x))</lang>
D
Here are four versions of Fibonacci Number calculating functions. FibD has an argument limit of magnitude 84 due to floating point precision, the others have a limit of 92 due to overflow (long).The traditional recursive version is inefficient. It is optimized by supplying a static storage to store intermediate results. A Fibonacci Number generating function is added. All functions have support for negative arguments. <lang d>import std.stdio, std.conv, std.algorithm, std.math ;
long sgn(alias unsignedFib)(int n) { // break sign manipulation apart
immutable uint m = (n >= 0) ? n : -n ;
if(n < 0 && (n % 2 == 0))
return - unsignedFib(m) ;
else
return unsignedFib(m) ;
}
long FibD(uint m) { // Direct Calculation, correct for abs(m) <= 84
enum sqrt5r = 1.0L / sqrt(5.0L) ; // 1 / sqrt(5) enum golden = (1.0L + sqrt(5.0L))/ 2.0L ; // (1 + sqrt(5)) / 2 ; return roundTo!long(pow(golden, m) * sqrt5r) ;
}
long FibI(uint m) { // Iterative
long thisFib = 0 ;
long nextFib = 1 ;
for(int i = 0 ; i < m ;i++) {
long tmp = nextFib ;
nextFib += thisFib ;
thisFib = tmp ;
}
return thisFib ;
}
long FibR(uint m) { // Recursive
return (m < 2) ? m : FibR(m-1) + FibR(m-2) ;
}
long FibM(uint m) { // memoized Recursive
static long[] fib = [0,1] ;
while(m >= fib.length )
fib ~= FibM(m - 2) + FibM(m - 1) ;
return fib[m] ;
}
alias sgn!FibD fibD ; alias sgn!FibI fibI ; alias sgn!FibR fibR ; alias sgn!FibM fibM ;
auto fibG(int m) { // generator(?)
immutable int sign = (m < 0) ? -1 : 1 ;
long yield ;
return new class {
int opApply(int delegate(ref int, ref long) dg) {
int idx = -sign ; // prepare for pre-increment
foreach(f;this)
if(dg(idx += sign, f))
break ;
return 0 ;
}
int opApply(int delegate(ref long) dg) {
long f0, f1 = 1 ;
foreach(p;0..m*sign + 1) {
if(sign == -1 && (p % 2 == 0))
yield = - f0 ;
else
yield = f0 ;
if(dg(yield)) break ;
auto temp = f1 ;
f1 = f0 + f1 ;
f0 = temp ;
}
return 0 ;
}
} ;
}
void main(string[] args) {
int k = args.length > 1 ? to!int(args[1]) : 10 ;
writefln("Fib(%3d) = ", k) ;
writefln("D : %20d <- %20d + %20d", fibD(k), fibD(k - 1), fibD(k - 2) ) ;
writefln("I : %20d <- %20d + %20d", fibI(k), fibI(k - 1), fibI(k - 2) ) ;
if( abs(k) < 36 || args.length > 2) // set a limit for recursive version
writefln("R : %20d <- %20d + %20d", fibR(k), fibM(k - 1), fibM(k - 2) ) ;
writefln("O : %20d <- %20d + %20d", fibM(k), fibM(k - 1), fibM(k - 2) ) ;
foreach(i, f;fibG(-9))
writef("%d:%d | ",i, f) ;
}</lang> Output for n = 85:
Fib( 85) = D : 259695496911122586 <- 160500643816367088 + 99194853094755497 I : 259695496911122585 <- 160500643816367088 + 99194853094755497 O : 259695496911122585 <- 160500643816367088 + 99194853094755497 0:0 | -1:1 | -2:-1 | -3:2 | -4:-3 | -5:5 | -6:-8 | -7:13 | -8:-21 | -9:34 |
Dart
<lang dart>int fib(int n) {
if(n==0 || n==1) {
return n;
}
int prev=1;
int current=1;
for(int i=2;i<n;i++) {
int next=prev+current;
prev=current;
current=next;
}
return current;
}
int fibRec(int n) => n==0||n==1 ? n : fibRec(n-1)+fibRec(n-2);
main() {
print(fib(11)); print(fibRec(11));
}</lang>
Delphi
Iterative
<lang Delphi> function FibonacciI(N: Word): UInt64; var
Last, New: UInt64; I: Word;
begin
if N < 2 then
Result := N
else begin
Last := 0;
Result := 1;
for I := 2 to N do
begin
New := Last + Result;
Last := Result;
Result := New;
end;
end;
end; </lang>
Recursive
<lang Delphi> function Fibonacci(N: Word): UInt64; begin
if N < 2 then Result := N else Result := Fibonacci(N - 1) + Fibonacci(N - 2);
end; </lang>
DWScript
<lang Delphi>function fib(N : Integer) : Integer; begin
if N < 2 then Result := 1 else Result := fib(N-2) + fib(N-1);
End;</lang>
E
<lang e>def fib(n) {
var s := [0, 1]
for _ in 0..!n {
def [a, b] := s
s := [b, a+b]
}
return s[0]
}</lang>
(This version defines fib(0) = 0 because OEIS A000045 does.)
Ela
<lang Ela> let fib = fib' 0 1
where fib' a b 0 = a
fib' a b n = fib' b (a + b) (n - 1)</lang>
Erlang
Recursive: <lang erlang>fib(0) -> 0; fib(1) -> 1; fib(N) when N > 1 -> fib(N-1) + fib(N-2).</lang>
Tail-recursive (iterative): <lang erlang>fib(N) -> fib(N,0,1). fib(0,Res,_) -> Res; fib(N,Res,Next) when N > 0 -> fib(N-1, Next, Res+Next).</lang>
Euphoria
'Recursive' version
<lang Euphoria> function fibor(integer n)
if n<2 then return n end if return fibor(n-1)+fibor(n-2)
end function </lang>
'Iterative' version
<lang Euphoria> function fiboi(integer n) integer f0=0, f1=1, f
if n<2 then return n end if for i=2 to n do f=f0+f1 f0=f1 f1=f end for return f
end function </lang>
'Tail recursive' version
<lang Euphoria> function fibot(integer n, integer u = 1, integer s = 0)
if n < 1 then return s else return fibot(n-1,u+s,u) end if
end function
-- example: ? fibot(10) -- says 55 </lang>
'Paper tape' version
<lang Euphoria> include std/mathcons.e -- for PINF constant
enum ADD, MOVE, GOTO, OUT, TEST, TRUETO
global sequence tape = { 0, 1, { ADD, 2, 1 }, { TEST, 1, PINF }, { TRUETO, 0 }, { OUT, 1, "%.0f\n" }, { MOVE, 2, 1 }, { MOVE, 0, 2 }, { GOTO, 3 } }
global integer ip global integer test global atom accum
procedure eval( sequence cmd ) atom i = 1 while i <= length( cmd ) do switch cmd[ i ] do case ADD then accum = tape[ cmd[ i + 1 ] ] + tape[ cmd[ i + 2 ] ] i += 2
case OUT then printf( 1, cmd[ i + 2], tape[ cmd[ i + 1 ] ] ) i += 2
case MOVE then if cmd[ i + 1 ] = 0 then tape[ cmd[ i + 2 ] ] = accum else tape[ cmd[ i + 2 ] ] = tape[ cmd[ i + 1 ] ] end if i += 2
case GOTO then ip = cmd[ i + 1 ] - 1 -- due to ip += 1 in main loop i += 1
case TEST then if tape[ cmd[ i + 1 ] ] = cmd[ i + 2 ] then test = 1 else test = 0 end if i += 2
case TRUETO then if test then if cmd[ i + 1 ] = 0 then abort(0) else ip = cmd[ i + 1 ] - 1 end if end if
end switch i += 1 end while end procedure
test = 0 accum = 0 ip = 1
while 1 do
-- embedded sequences (assumed to be code) are evaluated -- atoms (assumed to be data) are ignored
if sequence( tape[ ip ] ) then eval( tape[ ip ] ) end if ip += 1 end while
</lang>
FALSE
<lang false>[0 1[@$][1-@@\$@@+\]#%%]f:</lang>
Factor
Iterative
<lang factor>: fib ( n -- m )
dup 2 < [
[ 0 1 ] dip [ swap [ + ] keep ] times
drop
] unless ;</lang>
Recursive
<lang factor>: fib ( n -- m )
dup 2 < [
[ 1 - fib ] [ 2 - fib ] bi +
] unless ;</lang>
Tail-Recursive
<lang factor>: fib2 ( x y n -- a )
dup 1 < [ 2drop ] [ [ swap [ + ] keep ] dip 1 - fib2 ] if ;
- fib ( n -- m ) [ 0 1 ] dip fib2 ;</lang>
Matrix
<lang factor>USE: math.matrices
- fib ( n -- m )
dup 2 < [
[ { { 0 1 } { 1 1 } } ] dip 1 - m^n
second second
] unless ;</lang>
Fancy
<lang fancy>class Fixnum {
def fib {
match self -> {
case 0 -> 0
case 1 -> 1
case _ -> self - 1 fib + (self - 2 fib)
}
}
}
15 times: |x| {
x fib println
} </lang>
Falcon
Iterative
<lang falcon>function fib_i(n)
if n < 2: return n
fibPrev = 1
fib = 1
for i in [2:n]
tmp = fib
fib += fibPrev
fibPrev = tmp
end
return fib
end</lang>
Recursive
<lang falcon>function fib_r(n)
if n < 2 : return n return fib_r(n-1) + fib_r(n-2)
end</lang>
Tail Recursive
<lang falcon>function fib_tr(n)
return fib_aux(n,0,1)
end function fib_aux(n,a,b)
switch n
case 0 : return a
default: return fib_aux(n-1,a+b,a)
end
end</lang>
Fantom
Ints have a limit of 64-bits, so overflow errors occur after computing Fib(92) = 7540113804746346429.
<lang fantom> class Main {
static Int fib (Int n)
{
if (n < 2) return n
fibNums := [1, 0]
while (fibNums.size <= n)
{
fibNums.insert (0, fibNums[0] + fibNums[1])
}
return fibNums.first
}
public static Void main ()
{
20.times |n|
{
echo ("Fib($n) is ${fib(n)}")
}
}
} </lang>
Forth
<lang forth>: fib ( n -- fib )
0 1 rot 0 ?do over + swap loop drop ;</lang>
Fortran
Recursive
In ISO Fortran 90 or later, use a RECURSIVE function: <lang fortran>module fibonacci contains
recursive function fibR(n) result(fib)
integer, intent(in) :: n
integer :: fib
select case (n)
case (:0); fib = 0
case (1); fib = 1
case default; fib = fibR(n-1) + fibR(n-2)
end select
end function fibR</lang>
Iterative
In ISO Fortran 90 or later: <lang fortran> function fibI(n)
integer, intent(in) :: n
integer, parameter :: fib0 = 0, fib1 = 1
integer :: fibI, back1, back2, i
select case (n)
case (:0); fibI = fib0
case (1); fibI = fib1
case default
fibI = fib1
back1 = fib0
do i = 2, n
back2 = back1
back1 = fibI
fibI = back1 + back2
end do
end select
end function fibI
end module fibonacci</lang>
Test program <lang fortran>program fibTest
use fibonacci
do i = 0, 10
print *, fibr(i), fibi(i)
end do
end program fibTest</lang>
Output
0 0 1 1 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34 34 55 55
F#
This is a fast [tail-recursive] approach using the F# big integer support. <lang fsharp> let fibonacci n : bigint =
let rec f a b n = match n with | 0 -> a | 1 -> b | n -> (f b (a + b) (n - 1)) f (bigint 0) (bigint 1) n
> fibonacci 100;; val it : bigint = 354224848179261915075I</lang> Lazy evaluated using sequence workflow <lang fsharp>let rec fib = seq { yield! [0;1];
for (a,b) in Seq.zip fib (Seq.skip 1 fib) -> a+b}</lang>
Lazy evaluated using the sequence unfold anamorphism <lang fsharp>let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I) fibonacci |> Seq.nth 10000 </lang>
GAP
<lang gap>fib := function(n)
local a; a := [[0, 1], [1, 1]]^n; return a[1][2];
end;</lang> GAP has also a buit-in function for that. <lang gap>Fibonacci(n);</lang>
Gecho
<lang gecho>0 1 dup wover + dup wover + dup wover + dup wover +</lang> Prints the first several fibonacci numbers...
Go
Recursive
<lang go>func fib(a int) int {
if a < 2 {
return a
}
return fib(a - 1) + fib(a - 2)
}</lang>
Iterative
<lang go>import "big"
func fib(n uint64) (*big.Int) { a, b := big.NewInt(0), big.NewInt(1) var c big.Int
for i := uint64(0); i < n; i++ { c.Add(a, b) b.Set(a) a.Set(&c) }
return a }</lang>
Groovy
Recursive
A recursive closure must be pre-declared. <lang groovy>def rFib rFib = { it < 1 ? 0 : it == 1 ? 1 : rFib(it-1) + rFib(it-2) }</lang>
Iterative
<lang groovy>def iFib = { it < 1 ? 0 : it == 1 ? 1 : (2..it).inject([0,1]){i, j -> [i[1], i[0]+i[1]]}[1] }</lang>
Test program: <lang groovy>(0..20).each { println "${it}: ${rFib(it)} ${iFib(it)}" }</lang>
Output:
0: 0 0 1: 1 1 2: 1 1 3: 2 2 4: 3 3 5: 5 5 6: 8 8 7: 13 13 8: 21 21 9: 34 34 10: 55 55 11: 89 89 12: 144 144 13: 233 233 14: 377 377 15: 610 610 16: 987 987 17: 1597 1597 18: 2584 2584 19: 4181 4181 20: 6765 6765
HaXe
Iterative
<lang HaXe>static function fib(steps:Int, handler:Int->Void) { var current = 0; var next = 1;
for (i in 1...steps) { handler(current);
var temp = current + next; current = next; next = temp; } handler(current); }</lang>
As Iterator
<lang HaXe>class FibIter { public var current:Int; private var nextItem:Int; private var limit:Int;
public function new(limit) { current = 0; nextItem = 1; this.limit = limit; }
public function hasNext() return limit > 0
public function next() { limit--; var ret = current; var temp = current + nextItem; current = nextItem; nextItem = temp; return ret; } }</lang>
Used like:
<lang HaXe>for (i in new FibIter(10)) Lib.println(i);</lang>
Haskell
With lazy lists
This is a standard example how to use lazy lists. Here's the (infinite) list of all Fibonacci numbers:
<lang haskell>fib = 0 : 1 : zipWith (+) fib (tail fib)</lang>
The nth Fibonacci number is then just fib !! n. The above is equivalent to
<lang haskell>fib = 0 : 1 : go fib where go (a: t@(b:_)) = (a+b):go t</lang>
With matrix exponentiation
With the (rather slow) code from Matrix exponentiation operator
<lang haskell>import Data.List
xs <+> ys = zipWith (+) xs ys xs <*> ys = sum $ zipWith (*) xs ys
newtype Mat a = Mat {unMat :: a} deriving Eq
instance Show a => Show (Mat a) where
show xm = "Mat " ++ show (unMat xm)
instance Num a => Num (Mat a) where
negate xm = Mat $ map (map negate) $ unMat xm xm + ym = Mat $ zipWith (<+>) (unMat xm) (unMat ym) xm * ym = Mat [[xs <*> ys | ys <- transpose $ unMat ym] | xs <- unMat xm] fromInteger n = Mat fromInteger n</lang>
we can simply write
<lang haskell>fib 0 = 0 -- this line is necessary because "something ^ 0" returns "fromInteger 1", which unfortunately
-- in our case is not our multiplicative identity (the identity matrix) but just a 1x1 matrix of 1
fib n = last $ head $ unMat $ (Mat [[1,1],[1,0]]) ^ n</lang>
So, for example, the hundred-thousandth Fibonacci number starts with the digits
*Main> take 10 $ show $ fib (10^5) "2597406934"
With recurrence relations
Using Fib[m=3n+r] recurrence identities there's no space explosion and no memoization is necessary, given that 3n + 3 == 3(n+1) (*):
<lang haskell>fibsteps (a,b) n
| n <= 0 = (a,b) | True = fibsteps (b, a+b) (n-1)
fibnums :: [Integer] fibnums = map fst $ iterate (`fibsteps` 1) (0,1)
fibN2 :: Integer -> (Integer, Integer) fibN2 m | m < 10 = fibsteps (0,1) m fibN2 m = fibN2_next (n,r) (fibN2 n)
where (n,r) = quotRem m 3
fibN2_next (n,r) (f,g) | r==0 = (a,b) -- 3n ,3n+1
| r==1 = (b,c) -- 3n+1,3n+2
| r==2 = (c,d) -- 3n+2,3n+3 (*)
where
a = ( 5*f^3 + if even n then 3*f else (- 3*f) ) -- 3n
d = ( 5*g^3 + if even n then (- 3*g) else 3*g ) -- 3(n+1) (*)
b = ( g^3 + 3 * g * f^2 - f^3 ) -- 3n+1
c = ( g^3 + 3 * g^2 * f + f^3 ) -- 3n+2 </lang>
(fibN2 n) returns a pair (f,g) of two consecutive Fibonacci numbers, (Fib[n], Fib[n+1]):
*Main> take 10 $ show $ fst $ fibN2 (10^6) "1953282128"
Hope
Recursive
<lang hope>dec f : num -> num; --- f 0 <= 0; --- f 1 <= 1; --- f(n+2) <= f n + f(n+1);</lang>
Tail-recursive
<lang hope>dec fib : num -> num; --- fib n <= l (1, 0, n)
whererec l == \(a,b,succ c) => if c<1 then a else l((a+b),a,c)
|(a,b,0) => 0;</lang>
With lazy lists
This language, being one of Haskell's ancestors, also has lazy lists. Here's the (infinite) list of all Fibonacci numbers:
<lang hope>dec fibs : list num;
--- fibs <= fs whererec fs == 0::1::map (+) (tail fs||fs);</lang>
The nth Fibonacci number is then just fibs @ n.
HicEst
<lang hicest>REAL :: Fibonacci(10)
Fibonacci = ($==2) + Fibonacci($-1) + Fibonacci($-2) WRITE(ClipBoard) Fibonacci ! 0 1 1 2 3 5 8 13 21 34</lang>
Icon and Unicon
Icon has built-in support for big numbers. First, a simple recursive solution augmented by caching for non-negative input. This examples computes fib(1000) if there is no integer argument.
<lang Icon>procedure main(args)
write(fib(integer(!args) | 1000)
end
procedure fib(n)
static fCache
initial {
fCache := table()
fCache[0] := 0
fCache[1] := 1
}
/fCache[n] := fib(n-1) + fib(n-2)
return fCache[n]
end</lang>
The above solution is similar to the one provided fib in memrfncs
Now, an O(logN) solution. For large N, it takes far longer to convert the result to a string for output than to do the actual computation. This example computes fib(1000000) if there is no integer argument.
<lang Icon>procedure main(args)
write(fib(integer(!args) | 1000000))
end
procedure fib(n)
return fibMat(n)[1]
end
procedure fibMat(n)
if n <= 0 then return [0,0] if n = 1 then return [1,0] fp := fibMat(n/2) c := fp[1]*fp[1] + fp[2]*fp[2] d := fp[1]*(fp[1]+2*fp[2]) if n%2 = 1 then return [c+d, d] else return [d, c]
end</lang>
IDL
Recursive
<lang idl>function fib,n
if n lt 3 then return,1L else return, fib(n-1)+fib(n-2)
end</lang>
Execution time O(2^n) until memory is exhausted and your machine starts swapping. Around fib(35) on a 2GB Core2Duo.
Iterative
<lang idl>function fib,n
psum = (csum = 1uL) if n lt 3 then return,csum for i = 3,n do begin nsum = psum + csum psum = csum csum = nsum endfor return,nsum
end</lang>
Execution time O(n). Limited by size of uLong to fib(49)
Analytic
<lang idl>function fib,n
q=1/( p=(1+sqrt(5))/2 ) return,round((p^n+q^n)/sqrt(5))
end</lang>
Execution time O(1), only limited by the range of LongInts to fib(48).
J
The Fibonacci Sequence essay on the J Wiki presents a number of different ways of obtaining the nth Fibonacci number. Here is one: <lang j> fibN=: (-&2 +&$: -&1)^:(1&<) M."0</lang> Examples: <lang j> fibN 12 144
fibN i.31
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040</lang>
(This implementation is doubly recursive except that results are cached across function calls.)
Java
Iterative
<lang java>public static long itFibN(int n) {
if (n < 2)
return n;
long ans = 0;
long n1 = 0;
long n2 = 1;
for(n--; n > 0; n--)
{
ans = n1 + n2;
n1 = n2;
n2 = ans;
}
return ans;
}</lang>
Recursive
<lang java>public static long recFibN(final int n) {
return (n < 2) ? n : recFibN(n - 1) + recFibN(n - 2);
}</lang>
Analytic
This method works up to the 92nd Fibonacci number. After that, it goes out of range. <lang java>public static long anFibN(final long n) {
double p = (1 + Math.sqrt(5)) / 2; double q = 1 / p; return (long) ((Math.pow(p, n) + Math.pow(q, n)) / Math.sqrt(5));
}</lang>
Tail-recursive
<lang java>public static long fibTailRec(final int n) {
return fibInner(0, 1, n);
}
private static long fibInner(final long a, final long b, final int n) {
return n < 1 ? a : n == 1 ? b : fibInner(b, a + b, n - 1);
}</lang>
JavaScript
Recursive
One possibility familiar to Scheme programmers is to define an internal function for iteration through anonymous tail recursion: <lang javascript>function fib(n) {
return function(n,a,b) {
return n>0 ? arguments.callee(n-1,b,a+b) : a;
}(n,0,1);
}</lang>
Iterative
<lang javascript>function fib(n) {
var
a = 0,
b = 1,
t;
while (n-- > 0)
{
t = a;
a = b;
b += t;
}
return a;
}
var i; for (i = 0; i < 10; ++i)
alert(fib(i));</lang>
Memoization
<lang javascript>var fib = (function(cache){
return cache = cache || {}, function(n){
if (cache[n]) return cache[n];
else return cache[n] = n == 0 ? 0 : n < 0 ? -fib(-n)
: n <= 2 ? 1 : fib(n-2) + fib(n-1);
};
})(); </lang>
Y-Combinator
<lang javascript>function Y(dn) {
return (function(fn) {
return fn(fn);
}(function(fn) {
return dn(function() {
return fn(fn).apply(null, arguments);
});
}));
} var fib = Y(function(fn) {
return function(n) {
if (n === 0 || n === 1) {
return n;
}
return fn(n - 1) + fn(n - 2);
};
});</lang>
Joy
Recursive
<lang joy>DEFINE fib == [small]
[]
[pred dup pred]
[+]
binrec .</lang>
Iterative
<lang joy>DEFINE f == [1 0] dip [swap [+] unary] times popd .</lang>
Liberty BASIC
<lang lb>for i = 0 to 15
print fiboR(i),fiboI(i)
next i
function fiboR(n)
if n <= 1 then
fiboR = n
else
fiboR = fiboR(n-1) + fiboR(n-2)
end if
end function
function fiboI(n)
a = 0
b = 1
for i = 1 to n
temp = a + b
a = b
b = temp
next i
fiboI = a
end function
</lang>
Lisaac
<lang Lisaac>- fib(n : UINTEGER_32) : UINTEGER_64 <- (
+ result : UINTEGER_64;
(n < 2).if {
result := n;
} else {
result := fib(n - 1) + fib(n - 2);
};
result
);</lang>
Logo
<lang logo>to fib :n [:a 0] [:b 1]
if :n < 1 [output :a] output (fib :n-1 :b :a+:b)
end</lang>
Lua
<lang lua>--calculates the nth fibonacci number. Breaks for negative or non-integer n. function fibs(n)
return n < 2 and n or fibs(n - 1) + fibs(n - 2)
end
--more pedantic version, returns 0 for non-integer n function pfibs(n)
if n ~= math.floor(n) then return 0 elseif n < 0 then return pfibs(n + 2) - pfibs(n + 1) elseif n < 2 then return n else return pfibs(n - 1) + pfibs(n - 2) end
end
--tail-recursive function tfibs(i)
return (function a(n, u, s) return a(n-1,u+s,u) end)(i,1,0)
end
--table-recursive fib_n = setmetatable({1, 1}, {__index = function(z,n) return z[n-1] + z[n-2] end})</lang>
M4
<lang m4>define(`fibo',`ifelse(0,$1,0,`ifelse(1,$1,1, `eval(fibo(decr($1)) + fibo(decr(decr($1))))')')')dnl define(`loop',`ifelse($1,$2,,`$3($1) loop(incr($1),$2,`$3')')')dnl loop(0,15,`fibo')</lang>
Mathematica
Mathematica already has a built-in function Fibonacci, but a simple recursive implementation would be
<lang mathematica>fib[0] = 0 fib[1] = 1 fib[n_Integer] := fib[n - 1] + fib[n - 2]</lang>
An optimization is to cache the values already calculated:
<lang mathematica>fib[0] = 0 fib[1] = 1 fib[n_Integer] := fib[n] = fib[n - 1] + fib[n - 2]</lang>
MATLAB
Iterative
<lang MATLAB>function F = fibonacci(n)
Fn = [1 0]; %Fn(1) is F_{n-2}, Fn(2) is F_{n-1}
F = 0; %F is F_{n}
for i = (1:abs(n))
Fn(2) = F;
F = sum(Fn);
Fn(1) = Fn(2);
end
if n < 0
F = F*((-1)^(n+1));
end
end</lang>
Dramadah Matrix Method
The MATLAB help file suggests an interesting method of generating the Fibonacci numbers. Apparently the determinate of the Dramadah Matrix of type 3 (MATLAB designation) and size n-by-n is the nth Fibonacci number. This method is implimented below.
<lang MATLAB>function number = fibonacci2(n)
if n == 1
number = 1;
elseif n == 0
number = 0;
elseif n < 0
number = ((-1)^(n+1))*fibonacci2(-n);;
else
number = det(gallery('dramadah',n,3));
end
end</lang>
MAXScript
Iterative
<lang maxscript>fn fibIter n = (
if n < 2 then
(
n
)
else
(
fib = 1
fibPrev = 1
for num in 3 to n do
(
temp = fib
fib += fibPrev
fibPrev = temp
)
fib
)
)</lang>
Recursive
<lang maxscript>fn fibRec n = (
if n < 2 then
(
n
)
else
(
fibRec (n - 1) + fibRec (n - 2)
)
)</lang>
Mercury
<lang mercury>:- import_module int.
- - func fib(int) = int.
fib(N) = ( if N < 2 then N else fib(N-1) + fib(N-2) ). </lang>
Metafont
<lang metafont>vardef fibo(expr n) = if n=0: 0 elseif n=1: 1 else:
fibo(n-1) + fibo(n-2)
fi enddef;
for i=0 upto 10: show fibo(i); endfor end</lang>
Mirah
<lang mirah>def fibonacci(n:int)
return n if n < 2
fibPrev = 1
fib = 1
3.upto(Math.abs(n)) do
oldFib = fib
fib = fib + fibPrev
fibPrev = oldFib
end
fib * (n<0 ? int(Math.pow(n+1, -1)) : 1)
end
puts fibonacci 1 puts fibonacci 2 puts fibonacci 3 puts fibonacci 4 puts fibonacci 5 puts fibonacci 6 puts fibonacci 7 </lang>
ML/I
<lang ML/I>MCSKIP "WITH" NL "" Fibonacci - recursive MCSKIP MT,<> MCINS %. MCDEF FIB WITHS () AS <MCSET T1=%A1. MCGO L1 UNLESS 2 GR T1 %T1.<>MCGO L0 %L1.%FIB(%T1.-1)+FIB(%T1.-2).> fib(0) is FIB(0) fib(1) is FIB(1) fib(2) is FIB(2) fib(3) is FIB(3) fib(4) is FIB(4) fib(5) is FIB(5)</lang>
Modula-3
Recursive
<lang modula3>PROCEDURE Fib(n: INTEGER): INTEGER =
BEGIN
IF n < 2 THEN
RETURN n;
ELSE
RETURN Fib(n-1) + Fib(n-2);
END;
END Fib;</lang>
MUMPS
Iterative
<lang MUMPS>FIBOITER(N)
;Iterative version to get the Nth Fibonacci number ;N must be a positive integer ;F is the tree containing the values ;I is a loop variable. QUIT:(N\1'=N)!(N<0) "Error: "_N_" is not a positive integer." NEW F,I SET F(0)=0,F(1)=1 QUIT:N<2 F(N) FOR I=2:1:N SET F(I)=F(I-1)+F(I-2) QUIT F(N)</lang>
USER>W $$FIBOITER^ROSETTA(30) 832040
Nemerle
Recursive
<lang Nemerle>using System; using System.Console;
module Fibonacci {
Fibonacci(x : long) : long
{
|x when x < 2 => x
|_ => Fibonacci(x - 1) + Fibonacci(x - 2)
}
Main() : void
{
def num = Int64.Parse(ReadLine());
foreach (n in $[0 .. num])
WriteLine("{0}: {1}", n, Fibonacci(n));
}
}</lang>
Tail Recursive
<lang Nemerle>Fibonacci(x : long, current : long, next : long) : long {
match(x)
{
|0 => current
|_ => Fibonacci(x - 1, next, current + next)
}
}
Fibonacci(x : long) : long {
Fibonacci(x, 0, 1)
}</lang>
NetRexx
<lang NetRexx>/* NetRexx */
options replace format comments java crossref savelog symbols
numeric digits 210000 /*prepare for some big 'uns. */ parse arg x y . /*allow a single number or range.*/ if x == then do /*no input? Then assume -30-->+30*/
x = -30 y = -x end
if y == then y = x /*if only one number, show fib(n)*/ loop k = x to y /*process each Fibonacci request.*/
q = fib(k) w = q.length /*if wider than 25 bytes, tell it*/ say 'Fibonacci' k"="q if w > 25 then say 'Fibonacci' k "has a length of" w end k
exit
/*-------------------------------------FIB subroutine (non-recursive)---*/ method fib(arg) private static
parse arg n na = n.abs
if na < 2 then return na /*handle special cases. */ a = 0 b = 1
loop j = 2 to na s = a + b a = b b = s end j
if n > 0 | na // 2 == 1 then return s /*if positive or odd negative... */
else return -s /*return a negative Fib number. */
</lang>
NewLISP
Recursive
<lang newLisp>(define (fibonacci n) (if (< n 2) 1 (+ (fibonacci (- n 1)) (fibonacci (- n 2))))) (print(fibonacci 10)) ;;89</lang>
Nimrod
Analytic
<lang nimrod>proc Fibonacci(n: int): int64 =
var fn = float64(n) var p: float64 = (1.0 + sqrt(5.0)) / 2.0 var q: float64 = 1.0 / p return int64((pow(p, fn) + pow(q, fn)) / sqrt(5.0))</lang>
Iterative
<lang nimrod>proc Fibonacci(n: int): int64 =
var first: int64 = 0 var second: int64 = 1 var t: int64 = 0 while n > 1: t = first + second first = second second = t dec(n) result = second</lang>
Recursive
<lang nimrod>proc Fibonacci(n: int): int64 =
if n <= 2: result = 1 else: result = Fibonacci(n - 1) + Fibonacci(n - 2)</lang>
Tail-recursive
<lang nimrod>proc Fibonacci(n: int, current: int64, next: int64): int64 =
if n == 0: result = current else: result = Fibonacci(n - 1, next, current + next)
proc Fibonacci(n: int): int64 =
result = Fibonacci(n, 0, 1)</lang>
MASM
<lang MASM> TITLE i hate visual studio 4 (Fibs.asm)
- __ __/--------\
- >__ \ / | |\
- \ \___/ @ \ / \__________________
- \____ \ / \\\
- \____ Coded with love by
- |||
- \ Alexander Alvonellos |||
- | 9/29/2011 / ||
- | | MM
- | |--------------| |
- |< | |< |
- | | | |
- |mmmmmm| |mmmmm|
- Epic Win.
INCLUDE Irvine32.inc
.data BEERCOUNT = 48; Fibs dd 0, 1, BEERCOUNT DUP(0);
.code main PROC
- I am not responsible for this code.
- They made me write it, against my will.
;Here be dragons mov esi, offset Fibs; offset array; ;;were to start (start) mov ecx, BEERCOUNT; ;;count of items (how many) mov ebx, 4; ;;size (in number of bytes) call DumpMem;
mov ecx, BEERCOUNT; ;//http://www.wolframalpha.com/input/?i=F ib%5B47%5D+%3E+4294967295 mov esi, offset Fibs NextPlease:; mov eax, [esi]; ;//Get me the data from location at ESI add eax, [esi+4]; ;//add into the eax the data at esi + another double (next mem loc) mov [esi+8], eax; ;//Move that data into the memory location after the second number add esi, 4; ;//Update the pointer loop NextPlease; ;//Thank you sir, may I have another?
;Here be dragons
mov esi, offset Fibs; offset array; ;;were to start (start)
mov ecx, BEERCOUNT; ;;count of items (how many)
mov ebx, 4; ;;size (in number of bytes)
call DumpMem;
exit ; exit to operating system main ENDP
END main </lang>
Objeck
Recursive
<lang objeck>bundle Default {
class Fib {
function : Main(args : String[]), Nil {
for(i := 0; i <= 10; i += 1;) {
Fib(i)->PrintLine();
};
}
function : native : Fib(n : Int), Int {
if(n < 2) {
return n;
};
return Fib(n-1) + Fib(n-2);
}
}
}</lang>
OCaml
Iterative
<lang ocaml>let fib_iter n =
if n < 2 then
n
else let fib_prev = ref 1
and fib = ref 1 in
for num = 2 to n - 1 do
let temp = !fib in
fib := !fib + !fib_prev;
fib_prev := temp
done;
!fib</lang>
Recursive
<lang ocaml>let rec fib_rec n =
if n < 2 then n else fib_rec (n - 1) + fib_rec (n - 2)</lang>
The previous way is the naive form, because for most n the fib_rec is called twice, and it is not tail recursive because it adds the result of two function calls. The next version resolves these problems:
<lang ocaml>let fib n =
let rec fib_aux n a b =
match n with
| 0 -> a
| _ -> fib_aux (n-1) (a+b) a
in
fib_aux n 0 1</lang>
Arbitrary Precision
Using OCaml's Num module.
<lang ocaml>open Num
let fib =
let rec fib_aux f0 f1 = function | 0 -> f0 | 1 -> f1 | n -> fib_aux f1 (f1 +/ f0) (n - 1) in fib_aux (num_of_int 0) (num_of_int 1)</lang>
compile with:
ocamlopt nums.cmxa -o fib fib.ml
Octave
Recursive <lang octave>% recursive function fibo = recfibo(n)
if ( n < 2 ) fibo = n; else fibo = recfibo(n-1) + recfibo(n-2); endif
endfunction</lang>
Iterative <lang octave>% iterative function fibo = iterfibo(n)
if ( n < 2 )
fibo = n;
else
f = zeros(2,1);
f(1) = 0;
f(2) = 1;
for i = 2 : n
t = f(2);
f(2) = f(1) + f(2);
f(1) = t;
endfor
fibo = f(2);
endif
endfunction</lang>
Testing <lang octave>% testing for i = 0 : 20
printf("%d %d\n", iterfibo(i), recfibo(i));
endfor</lang>
OPL
<lang opl>FIBON: REM Fibonacci sequence is generated to the Organiser II floating point variable limit. REM This method was derived from (not copied...) the original OPL manual that came with the CM and XP in the mid 1980s. REM CLEAR/ON key quits. REM Mikesan - http://forum.psion2.org/ LOCAL A,B,C A=1 :B=1 :C=1 PRINT A, DO
C=A+B A=B B=C PRINT A,
UNTIL GET=1</lang>
Oz
Iterative
Using mutable references (cells). <lang oz>fun{FibI N}
Temp = {NewCell 0}
A = {NewCell 0}
B = {NewCell 1}
in
for I in 1..N do Temp := @A + @B A := @B B := @Temp end @A
end</lang>
Recursive
Inefficient (blows up the stack). <lang oz>fun{FibR N}
if N < 2 then N
else {FibR N-1} + {FibR N-2}
end
end</lang>
Tail-recursive
Using accumulators. <lang oz>fun{Fib N}
fun{Loop N A B}
if N == 0 then
B
else
{Loop N-1 A+B A}
end end
in
{Loop N 1 0}
end</lang>
Lazy-recursive
<lang oz>declare
fun lazy {FiboSeq}
{LazyMap
{Iterate fun {$ [A B]} [B A+B] end [0 1]}
Head}
end
fun {Head A|_} A end
fun lazy {Iterate F I}
I|{Iterate F {F I}}
end
fun lazy {LazyMap Xs F}
case Xs of X|Xr then {F X}|{LazyMap Xr F}
[] nil then nil
end
end
in
{Show {List.take {FiboSeq} 8}}</lang>
PARI/GP
Built-in
<lang parigp>fibonocci(n)</lang>
Matrix
<lang parigp>([1,1;1,0]^n)[1,2]</lang>
Analytic
This uses the Binet form. <lang parigp>fib(n)=my(phi=(1+sqrt(5))/2);round((phi^n-phi^-n)/sqrt(5))</lang> The second term can be dropped since the error is always small enough to be subsumed by the rounding. <lang parigp>fib(n)=round((1+sqrt(5))/2)^n/sqrt(5))</lang>
Algebraic
This is an exact version of the above formula. quadgen(5) represents and the number is stored in the form . imag takes the coefficient of . (real(quadgen(5)^n) would give the (n-1)-th Fibonacci number.)
<lang parigp>fib(n)=imag(quadgen(5)^n)</lang>
Combinatorial
This uses the generating function. It can be trivially adapted to give the first n Fibonacci numbers. <lang parigp>fib(n)=polcoeff(x/(1-x-x^2)+O(x^(n+1)),n)</lang>
Binary powering
<lang parigp>fib(n)={
if(n<=0, if(n,(-1)^(n+1)*fib(n),0) , my(v=lucas(n-1)); (2*v[1]+v[2])/5 )
}; lucas(n)={
if (!n, return([2,1])); my(v=lucas(n >> 1), z=v[1], t=v[2], pr=v[1]*v[2]); n=n%4; if(n%2, if(n==3,[v[1]*v[2]+1,v[2]^2-2],[v[1]*v[2]-1,v[2]^2+2]) , if(n,[v[1]^2+2,v[1]*v[2]+1],[v[1]^2-2,v[1]*v[2]-1]) )
};</lang>
Recursive
<lang parigp>fib(n)={
if(n<2,
if(n<0,
(-1)^(n+1)*fib(n)
,
n
)
,
fib(n-1)+fib(n)
)
};</lang>
Iterative
<lang parigp>fib(n)={
if(n<0,return((-1)^(n+1)*fib(n))); my(a=0,b=1,t); while(n, t=a+b; a=b; b=t; n-- ); a
};</lang>
One-by-one
This code is purely for amusement and requires n > 1. <lang parigp>fib(n)=my(k=0);while(n--,k++;while(!issquare(5*k^2+4)&&!issquare(5*k^2-4),k++));k</lang>
Pascal
Recursive
<lang pascal>function fib(n: integer): integer;
begin if (n = 0) or (n = 1) then fib := n else fib := fib(n-1) + fib(n-2) end;</lang>
Iterative
<lang pascal>function fib(n: integer): integer;
var f0, f1, f2, k: integer; begin f0 := 0; f1 := 1; for k := 2 to n do begin f2:= f0 + f1; f0 := f1; f1 := f2; end; fib := f2; end;</lang>
Perl
Iterative
<lang perl>sub fibIter {
my $n = shift; return $n if $n < 2;
my $fibPrev = 1; my $fib = 1; ($fibPrev, $fib) = ($fib, $fib + $fibPrev) for 2..$n-1; $fib;
}</lang>
Recursive
<lang perl>sub fibRec {
my $n = shift; $n < 2 ? $n : fibRec($n - 1) + fibRec($n - 2);
}</lang>
Perl 6
Iterative
<lang perl6>sub fib (Int $n --> Int) {
$n > 1 or return $n; my ($prev, $this) = 0, 1; ($prev, $this) = $this, $this + $prev for 1 ..^ $n; return $this;
}</lang>
Recursive
<lang perl6>proto fib (Int $n --> Int) {*} multi fib (0) { 0 } multi fib (1) { 1 } multi fib ($n) { fib($n - 1) + fib($n - 2) }</lang> (Unfortunately, rakudo does not yet implement the is cached trait, so this remains an inefficient solution.)
Analytic
<lang perl6>sub fib (Int $n --> Int) {
constant φ1 = 1 / constant φ = (1 + sqrt 5)/2; constant invsqrt5 = 1 / sqrt 5;
floor invsqrt5 * (φ**$n + φ1**$n);
}</lang>
List Generator (built in)
This constructs the fibonacci sequence as a lazy infinite array. <lang perl6>my @fib := 0, 1, *+* ... *;</lang>
If you really need a function for it: <lang perl6>sub fib ($n) { @fib[$n] }</lang>
PHP
Iterative
<lang php>function fibIter($n) {
if ($n < 2) {
return $n;
}
$fibPrev = 0;
$fib = 1;
foreach (range(1, $n-1) as $i) {
list($fibPrev, $fib) = array($fib, $fib + $fibPrev);
}
return $fib;
}</lang>
Recursive
<lang php>function fibRec($n) {
return $n < 2 ? $n : fibRec($n-1) + fibRec($n-2);
}</lang>
PicoLisp
Recursive
<lang PicoLisp>(de fibo (N)
(if (> 2 N)
1
(+ (fibo (dec N)) (fibo (- N 2))) ) )</lang>
Recursive with Cache
Using a recursive version doesn't need to be slow, as the following shows: <lang PicoLisp>(de fibo (N)
(cache '(NIL) (pack (char (hash N)) N) # Use a cache to accelerate
(if (> 2 N)
N
(+ (fibo (dec N)) (fibo (- N 2))) ) ) )
(bench (fibo 1000))</lang> Output: <lang PicoLisp>0.012 sec -> 43466557686937456435688527675040625802564660517371780402481729089536555417949 05189040387984007925516929592259308032263477520968962323987332247116164299644090 6533187938298969649928516003704476137795166849228875</lang>
Iterative
Recursive can only go so far until a stack overflow brings the whole thing crashing down. <lang PicoLisp>(de fibo (N)
(let (I 1 J 0)
(do N
(let (Tmp J)
(inc 'J I)
(setq I Tmp) ) )
J) )</lang>
PIR
Recursive:
<lang pir>.sub fib
.param int n .local int nt .local int ft if n < 2 goto RETURNN nt = n - 1 ft = fib( nt ) dec nt nt = fib(nt) ft = ft + nt .return( ft )
RETURNN:
.return( n ) end
.end
.sub main :main
.local int counter .local int f counter=0
LOOP:
if counter > 20 goto DONE f = fib(counter) print f print "\n" inc counter goto LOOP
DONE:
end
.end</lang>
Iterative (stack-based):
<lang pir>.sub fib
.param int n .local int counter .local int f .local pmc fibs .local int nmo .local int nmt
fibs = new 'ResizableIntegerArray' if n == 0 goto RETURN0 if n == 1 goto RETURN1 push fibs, 0 push fibs, 1 counter = 2
FIBLOOP:
if counter > n goto DONE nmo = pop fibs nmt = pop fibs f = nmo + nmt push fibs, nmt push fibs, nmo push fibs, f inc counter goto FIBLOOP
RETURN0:
.return( 0 ) end
RETURN1:
.return( 1 ) end
DONE:
f = pop fibs .return( f ) end
.end
.sub main :main
.local int counter .local int f counter=0
LOOP:
if counter > 20 goto DONE f = fib(counter) print f print "\n" inc counter goto LOOP
DONE:
end
.end</lang>
Pike
Ported from the Ruby example below ;)
<lang pike>int fibRec(int number){
if(number <= -2){
return pow(-1,(number+1)) * fibRec(abs(number));
} else if(number <= 1){
return abs(number);
} else {
return fibRec(number-1) + fibRec(number-2);
}
}</lang>
PL/I
<lang PL/I>/* Form the n-th Fibonacci number, n > 1. */ get list (n); f1 = 0; f2, f3 = 1; do i = 1 to n-2;
f3 = f1 + f2; f1 = f2; f2 = f3;
end; put skip list (f3);</lang>
PL/SQL
<lang PL/SQL>Create or replace Function fnu_fibonnaci(p_iNumber integer) return integer is
nuFib integer; nuP integer; nuQ integer;
Begin
if p_iNumber is not null then
if p_iNumber=0 then
nuFib:=0;
Elsif p_iNumber=1 then
nuFib:=1;
Else
nuP:=0;
nuQ:=1;
For nuI in 2..p_iNumber loop
nuFib:=nuP+nuQ;
nuP:=nuQ;
nuQ:=nuFib;
End loop;
End if;
End if;
return(nuFib);
End fnu_fibonnaci;</lang>
Pop11
<lang pop11>define fib(x); lvars a , b;
1 -> a;
1 -> b;
repeat x - 1 times
(a + b, b) -> (b, a);
endrepeat;
a;
enddefine;</lang>
PostScript
Enter the desired number for "n" and run through your favorite postscript previewer or send to your postscript printer:
<lang postscript>%!PS
% We want the 'n'th fibonacci number /n 13 def
% Prepare output canvas: /Helvetica findfont 20 scalefont setfont 100 100 moveto
%define the function recursively: /fib { dup
3 lt
{ pop 1 }
{ dup 1 sub fib exch 2 sub fib add }
ifelse
} def
(Fib\() show n (....) cvs show (\)=) show n fib (.....) cvs show
showpage</lang>
PowerBASIC
There seems to be a limitation (dare I say, bug?) in PowerBASIC regarding how large numbers are stored. 10E17 and larger get rounded to the nearest 10. For F(n), where ABS(n) > 87, is affected like this:
actual: displayed: F(88) 1100087778366101931 1100087778366101930 F(89) 1779979416004714189 1779979416004714190 F(90) 2880067194370816120 2880067194370816120 F(91) 4660046610375530309 4660046610375530310 F(92) 7540113804746346429 7540113804746346430
<lang powerbasic>FUNCTION fibonacci (n AS LONG) AS QUAD
DIM u AS LONG, a AS LONG, L0 AS LONG, outP AS QUAD STATIC fibNum() AS QUAD
u = UBOUND(fibNum) a = ABS(n)
IF u < 1 THEN
REDIM fibNum(1)
fibNum(1) = 1
u = 1
END IF
SELECT CASE a
CASE 0 TO 92
IF a > u THEN
REDIM PRESERVE fibNum(a)
FOR L0 = u + 1 TO a
fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2)
IF 88 = L0 THEN fibNum(88) = fibNum(88) + 1
NEXT
END IF
IF n < 0 THEN
fibonacci = fibNum(a) * ((-1)^(a+1))
ELSE
fibonacci = fibNum(a)
END IF
CASE ELSE
'Even without the above-mentioned bug, we're still limited to
'F(+/-92), due to data type limits. (F(93) = &hA94F AD42 221F 2702)
ERROR 6
END SELECT
END FUNCTION
FUNCTION PBMAIN () AS LONG
DIM n AS LONG
#IF NOT %DEF(%PB_CC32)
OPEN "out.txt" FOR OUTPUT AS 1
#ENDIF
FOR n = -92 TO 92
#IF %DEF(%PB_CC32)
PRINT STR$(n); ": "; FORMAT$(fibonacci(n), "#")
#ELSE
PRINT #1, STR$(n) & ": " & FORMAT$(fibonacci(n), "#")
#ENDIF
NEXT
CLOSE
END FUNCTION</lang>
PowerShell
Iterative
<lang powershell>function fib ($n) {
if ($n -eq 0) { return 0 }
if ($n -eq 1) { return 1 }
$m = 1
if ($n -lt 0) {
if ($n % 2 -eq -1) {
$m = 1
} else {
$m = -1
}
$n = -$n }
$a = 0 $b = 1
for ($i = 1; $i -lt $n; $i++) {
$c = $a + $b
$a = $b
$b = $c
}
return $m * $b
}</lang>
Recursive
<lang powershell>function fib($n) {
switch ($n) {
0 { return 0 }
1 { return 1 }
{ $_ -lt 0 } { return [Math]::Pow(-1, -$n + 1) * (fib (-$n)) }
default { return (fib ($n - 1)) + (fib ($n - 2)) }
}
}</lang>
Prolog
<lang prolog> fib(0, 0):-!. fib(1, 1):-!. fib(N, X):-N1 is N-1, N2 is N-2, fib(N1, X1), fib(N2, X2), X is X1+X2. </lang>
Continuation passing style
Works with SWI-Prolog and module lambda, written by Ulrich Neumerkel found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl <lang Prolog>:- use_module(lambda). fib(N, FN) :- cont_fib(N, _, FN, \_^Y^_^U^(U = Y)).
cont_fib(N, FN1, FN, Pred) :- ( N < 2 -> call(Pred, 0, 1, FN1, FN) ; N1 is N - 1, P = \X^Y^Y^U^(U is X + Y), cont_fib(N1, FNA, FNB, P), call(Pred, FNA, FNB, FN1, FN) ). </lang>
Pure
Tail Recursive
<lang pure>fib n = loop 0 1 n with
loop a b n = if n==0 then a else loop b (a+b) (n-1);
end;</lang>
PureBasic
Macro based calculation
<lang PureBasic>Macro Fibonacci (n) Int((Pow(((1+Sqr(5))/2),n)-Pow(((1-Sqr(5))/2),n))/Sqr(5)) EndMacro</lang>
Recursive
<lang PureBasic>Procedure FibonacciReq(n)
If n<2 ProcedureReturn n Else ProcedureReturn FibonacciReq(n-1)+FibonacciReq(n-2) EndIf
EndProcedure</lang>
Recursive & optimized with a static hash table
This will be much faster on larger n's, this as it uses a table to store known parts instead of recalculating them. On my machine the speedup compares to above code is
Fib(n) Speedup 20 2 25 23 30 217 40 25847 46 1156741
<lang PureBasic>Procedure Fibonacci(n)
Static NewMap Fib.i()
Protected FirstRecursion
If MapSize(Fib())= 0 ; Init the hash table the first run
Fib("0")=0: Fib("1")=1
FirstRecursion = #True
EndIf
If n >= 2
Protected.s s=Str(n)
If Not FindMapElement(Fib(),s) ; Calculate only needed parts
Fib(s)= Fibonacci(n-1)+Fibonacci(n-2)
EndIf
n = Fib(s)
EndIf
If FirstRecursion ; Free the memory when finalizing the first call
ClearMap(Fib())
EndIf
ProcedureReturn n
EndProcedure</lang>
Example
Fibonacci(0)= 0 Fibonacci(1)= 1 Fibonacci(2)= 1 Fibonacci(3)= 2 Fibonacci(4)= 3 Fibonacci(5)= 5 FibonacciReq(0)= 0 FibonacciReq(1)= 1 FibonacciReq(2)= 1 FibonacciReq(3)= 2 FibonacciReq(4)= 3 FibonacciReq(5)= 5
Purity
The following takes a natural number and generates an initial segment of the Fibonacci sequence of that length:
<lang Purity> data Fib1 = FoldNat
<
const (Cons One (Cons One Empty)),
(uncurry Cons) . ((uncurry Add) . (Head, Head . Tail), id)
>
</lang>
This following calculates the Fibonacci sequence as an infinite stream of natural numbers:
<lang Purity> type (Stream A?,,,Unfold) = gfix X. A? . X? data Fib2 = Unfold ((outl, (uncurry Add, outl))) ((curry id) One One) </lang>
As a histomorphism:
<lang Purity> import Histo
data Fib3 = Histo . Memoize
<
const One,
(p1 =>
<
const One,
(p2 => Add (outl $p1) (outl $p2)). UnmakeCofree
> (outr $p1)) . UnmakeCofree
>
</lang>
Python
Analytic
<lang python>from math import *
def analytic_fibonacci(n):
sqrt_5 = sqrt(5); p = (1 + sqrt_5) / 2; q = 1/p; return int( (p**n + q**n) / sqrt_5 + 0.5 )
for i in range(1,31):
print analytic_fibonacci(i),</lang>
Output:
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
Iterative
<lang python>def fibIter(n):
if n < 2:
return n
fibPrev = 1
fib = 1
for num in xrange(2, n):
fibPrev, fib = fib, fib + fibPrev
return fib</lang>
Recursive
<lang python>def fibRec(n):
if n < 2:
return n
else:
return fibRec(n-1) + fibRec(n-2)</lang>
Recursive with Memoization
<lang python>class fibMemo:
def __init__(self):
self.pad = {0:0, 1:1}
def __call__(self, n):
if not n in self.pad:
self.pad[n] = self.__call__(n-1) + self.__call__(n-2)
return self.pad[n]
fm = fibMemo() for i in range(1,31):
print fm(i),</lang>
Output:
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
Generative
<lang python>def fibGen():
f0, f1 = 0, 1
while True:
yield f0
f0, f1 = f1, f0+f1</lang>
Example use
<lang python>>>> fg = fibGen() >>> for x in range(9):
print fg.next()
0 1 1 2 3 5 8 13 21 >>></lang>
R
<lang R>recfibo <- function(n) {
if ( n < 2 ) n else recfibo(n-1) + recfibo(n-2)
}
iterfibo <- function(n) {
if ( n < 2 )
n
else {
f <- c(0, 1)
for (i in 2:n) {
t <- f[2]
f[2] <- sum(f)
f[1] <- t
}
f[2]
}
}
fib <- function(n)
if(n <= 2){if(n>=0) 1 else 0 } else Recall(n-1) + Recall(n-2)</lang>
<lang R>print.table(lapply(0:20, recfibo)) print.table(lapply(0:20, iterfibo))</lang>
Racket
Recursive <lang Racket>(define (fib n)
(if (< n 2)
1
(+ (fib (- n 1)) (fib (- n 2)))))</lang>
REALbasic
Pass n to this function where n is the desired number of iterations. This example uses the UInt64 datatype which is as unsigned 64 bit integer. As such, it overflows after the 92nd iteration. <lang REALbasic>Function fibo(n as integer) As UInt64
dim noOne as UInt64 = 1 dim noTwo as UInt64 = 1 dim sum As UInt64
for i as integer = 1 to n
sum = noOne + noTwo
noTwo = noOne
noOne = sum
Next
Return noOne</lang>
Retro
Recursive
<lang Retro>: fib ( n-m ) dup [ 0 = ] [ 1 = ] bi or if; [ 1- fib ] sip [ 2 - fib ] do + ;</lang>
Iterative
<lang Retro>: fib ( n-N )
[ 0 1 ] dip [ over + swap ] times drop ;</lang>
REXX
With 210,000 numeric digits, this REXX program can handle Fibonacci numbers past one million.
This version can handle negative Bibonacci numbers.
<lang rexx>
/*REXX program calculates the Nth Fibonacci number, N can be zero or neg*/
numeric digits 210000 /*prepare for some big 'uns. */
parse arg x y . /*allow a single number or range.*/
if x== then do; x=-30; y=-x; end /*no input? Then assume -30-->+30*/
if y== then y=x /*if only one number, show fib(n)*/
do k=x to y /*process each Fibonacci request.*/
q=fib(k)
w=length(q) /*if wider than 25 bytes, tell it*/
say 'Fibonacci' k"="q
if w>25 then say 'Fibonacci' k "has a length of" w
end
exit
/*─────────────────────────────────────FIB subroutine (non-recursive)───*/ fib: procedure; parse arg n; na=abs(n) if na<2 then return na /*handle special cases. */ a=0 b=1
do j=2 to na
s=a+b
a=b
b=s
end
if n>0 | na//2==1 then return s /*if positive or odd negative... */
else return -s /*return a negative Fib number. */
</lang>
Output when the following arguments were specified:
-30 100
Fibonacci -30=-832040 Fibonacci -29=514229 Fibonacci -28=-317811 Fibonacci -27=196418 Fibonacci -26=-121393 Fibonacci -25=75025 Fibonacci -24=-46368 Fibonacci -23=28657 Fibonacci -22=-17711 Fibonacci -21=10946 Fibonacci -20=-6765 Fibonacci -19=4181 Fibonacci -18=-2584 Fibonacci -17=1597 Fibonacci -16=-987 Fibonacci -15=610 Fibonacci -14=-377 Fibonacci -13=233 Fibonacci -12=-144 Fibonacci -11=89 Fibonacci -10=-55 Fibonacci -9=34 Fibonacci -8=-21 Fibonacci -7=13 Fibonacci -6=-8 Fibonacci -5=5 Fibonacci -4=-3 Fibonacci -3=2 Fibonacci -2=-1 Fibonacci -1=1 Fibonacci 0=0 Fibonacci 1=1 Fibonacci 2=1 Fibonacci 3=2 Fibonacci 4=3 Fibonacci 5=5 Fibonacci 6=8 Fibonacci 7=13 Fibonacci 8=21 Fibonacci 9=34 Fibonacci 10=55 Fibonacci 11=89 Fibonacci 12=144 Fibonacci 13=233 Fibonacci 14=377 Fibonacci 15=610 Fibonacci 16=987 Fibonacci 17=1597 Fibonacci 18=2584 Fibonacci 19=4181 Fibonacci 20=6765 Fibonacci 21=10946 Fibonacci 22=17711 Fibonacci 23=28657 Fibonacci 24=46368 Fibonacci 25=75025 Fibonacci 26=121393 Fibonacci 27=196418 Fibonacci 28=317811 Fibonacci 29=514229 Fibonacci 30=832040 Fibonacci 31=1346269 Fibonacci 32=2178309 Fibonacci 33=3524578 Fibonacci 34=5702887 Fibonacci 35=9227465 Fibonacci 36=14930352 Fibonacci 37=24157817 Fibonacci 38=39088169 Fibonacci 39=63245986 Fibonacci 40=102334155 Fibonacci 41=165580141 Fibonacci 42=267914296 Fibonacci 43=433494437 Fibonacci 44=701408733 Fibonacci 45=1134903170 Fibonacci 46=1836311903 Fibonacci 47=2971215073 Fibonacci 48=4807526976 Fibonacci 49=7778742049 Fibonacci 50=12586269025 Fibonacci 51=20365011074 Fibonacci 52=32951280099 Fibonacci 53=53316291173 Fibonacci 54=86267571272 Fibonacci 55=139583862445 Fibonacci 56=225851433717 Fibonacci 57=365435296162 Fibonacci 58=591286729879 Fibonacci 59=956722026041 Fibonacci 60=1548008755920 Fibonacci 61=2504730781961 Fibonacci 62=4052739537881 Fibonacci 63=6557470319842 Fibonacci 64=10610209857723 Fibonacci 65=17167680177565 Fibonacci 66=27777890035288 Fibonacci 67=44945570212853 Fibonacci 68=72723460248141 Fibonacci 69=117669030460994 Fibonacci 70=190392490709135 Fibonacci 71=308061521170129 Fibonacci 72=498454011879264 Fibonacci 73=806515533049393 Fibonacci 74=1304969544928657 Fibonacci 75=2111485077978050 Fibonacci 76=3416454622906707 Fibonacci 77=5527939700884757 Fibonacci 78=8944394323791464 Fibonacci 79=14472334024676221 Fibonacci 80=23416728348467685 Fibonacci 81=37889062373143906 Fibonacci 82=61305790721611591 Fibonacci 83=99194853094755497 Fibonacci 84=160500643816367088 Fibonacci 85=259695496911122585 Fibonacci 86=420196140727489673 Fibonacci 87=679891637638612258 Fibonacci 88=1100087778366101931 Fibonacci 89=1779979416004714189 Fibonacci 90=2880067194370816120 Fibonacci 91=4660046610375530309 Fibonacci 92=7540113804746346429 Fibonacci 93=12200160415121876738 Fibonacci 94=19740274219868223167 Fibonacci 95=31940434634990099905 Fibonacci 96=51680708854858323072 Fibonacci 97=83621143489848422977 Fibonacci 98=135301852344706746049 Fibonacci 99=218922995834555169026 Fibonacci 100=354224848179261915075
Output when the following arguments were specified:
10000
Fibonacci 10000=33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369 598274916066020998841839338646527313000888302692356736131351175792974378544137521305205043477016022647583189065278908551543661595829872796829875106312005754287834532155151038708182989 979161312785626503319548714021428753269818796204693609787990035096230229102636813149319527563022783762844154036058440257211433496118002309120828704608892396232883546150577658327125254 093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820 163702980893320999057079200643674262023897831114700540749984592503606335609338838319233867830561364353518921332797329081337326426526339897639227234078829281779535805709936910491754708 893184105614632233821746563732124822638309210329770164805472624384237486241145309381220656491403275108664339451751216152654536133311131404243685480510676584349352383695965342807176877 328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623 171031012919531697946076327375892535307725523759437884345040677155557790564504430166401194625809722167297586150269684431469520346149322911059706762432685159928347098912847067408620085 713501626031207190317208609408129832158107728207635318662461127824553720853236530577595643007251774431505153960090516860322034916322264088524885243315805153484962243484829938090507048 482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270 202235648464951961124602683139709750693826487066132645076650746115126775227486215986425307112984411826226610571635150692600298617049454250474913781151541399415506712562711971332527636 1939606902895650288268608362241082050562430701794976171121233066073310059947366875 Fibonacci 10000 has a length of 2090
Ruby
Iterative
<lang ruby>def fibIter(n)
return 0 if n == 0
fibPrev, fib = 1, 1
(n.abs - 2).times { fibPrev, fib = fib, fib + fibPrev }
fib * (n<0 ? (-1)**(n+1) : 1)
end</lang>
Recursive
<lang ruby>def fibRec(n)
if n <= -2 (-1)**(n+1) * fibRec(n.abs) elsif n <= 1 n.abs else fibRec(n-1) + fibRec(n-2) end
end</lang>
Recursive with Memoization
<lang ruby># Use the Hash#default_proc feature to
- lazily calculate the Fibonacci numbers.
fib = Hash.new do |f, n|
f[n] = if n <= -2
(-1)**(n+1) * f[n.abs]
elsif n <= 1
n.abs
else
f[n-1] + f[n-2]
end
end
- examples: fib[10] => 55, fib[-10] => (-55/1)</lang>
Matrix
<lang ruby>require 'matrix'
- To understand why this matrix is useful for Fibonacci numbers, remember
- that the definition of Matrix.**2 for any Matrix[[a, b], [c, d]] is
- is [[a*a + b*c, a*b + b*d], [c*a + d*b, c*b + d*d]]. In other words, the
- lower right element is computing F(k - 2) + F(k - 1) every time M is multiplied
- by itself (it is perhaps easier to understand this by computing M**2, 3, etc, and
- watching the result march up the sequence of Fibonacci numbers).
M = Matrix[[0, 1], [1,1]]
- Matrix exponentiation algorithm to compute Fibonacci numbers.
- Let M be Matrix [[0, 1], [1, 1]]. Then, the lower right element of M**k is
- F(k + 1). In other words, the lower right element of M is F(2) which is 1, and the
- lower right element of M**2 is F(3) which is 2, and the lower right element
- of M**3 is F(4) which is 3, etc.
- This is a good way to compute F(n) because the Ruby implementation of Matrix.**(n)
- uses O(log n) rather than O(n) matrix multiplications. It works by squaring squares
- ((m**2)**2)... as far as possible
- and then multiplying that by by M**(the remaining number of times). E.g., to compute
- M**19, compute partial = ((M**2)**2) = M**16, and then compute partial*(M**3) = M**19.
- That's only 5 matrix multiplications of M to compute M*19.
def self.fibMatrix(n)
return 0 if n <= 0 # F(0) return 1 if n == 1 # F(1) # To get F(n >= 2), compute M**(n - 1) and extract the lower right element. return CS::lower_right(M**(n - 1))
end
- Matrix utility to return
- the lower, right-hand element of a given matrix.
def self.lower_right matrix
return nil if matrix.row_size == 0 return matrix[matrix.row_size - 1, matrix.column_size - 1]
end</lang>
Generative
<lang ruby>require 'generator'
def fibGen
Generator.new do |g|
f0, f1 = 0, 1
loop do
g.yield f0
f0, f1 = f1, f0+f1
end
end
end</lang>
Usage:
irb(main):012:0> fg = fibGen
=> #<Generator:0xb7d3ead4 @cont_next=nil, @queue=[0], @cont_endp=nil, @index=0, @block=#<Proc:0xb7d41680@(irb):4>, @cont_yield=#<Continuation:0xb7d3e8a4>>
irb(main):013:0> 9.times { puts fg.next }
0
1
1
2
3
5
8
13
21
=> 9
"Fibers are primitives for implementing light weight cooperative concurrency in Ruby. Basically they are a means of creating code blocks that can be paused and resumed, much like threads. The main difference is that they are never preempted and that the scheduling must be done by the programmer and not the VM." [1]
<lang ruby>fib = Fiber.new do
a,b = 0,1 loop do Fiber.yield a a,b = b,a+b end
end 9.times {puts fib.resume}</lang>
SAS
<lang sas>/* building a table with fibonacci sequence */ data fib; a=0; b=1; do n=0 to 20; f=a; output; a=b; b=f+a; end; keep n f; run; </lang>
Sather
The implementations use the arbitrary precision class INTI. <lang sather>class MAIN is
-- RECURSIVE -- fibo(n :INTI):INTI pre n >= 0 is if n < 2.inti then return n; end; return fibo(n - 2.inti) + fibo(n - 1.inti); end;
-- ITERATIVE -- fibo_iter(n :INTI):INTI pre n >= 0 is n3w :INTI;
if n < 2.inti then return n; end;
last ::= 0.inti; this ::= 1.inti;
loop (n - 1.inti).times!;
n3w := last + this;
last := this;
this := n3w;
end;
return this;
end;
main is
loop i ::= 0.upto!(16);
#OUT + fibo(i.inti) + " ";
#OUT + fibo_iter(i.inti) + "\n";
end;
end;
end;</lang>
Scala
Recursive
<lang scala>def fib(i:Int):Int = i match{
case 0 => 0 case 1 => 1 case _ => fib(i-1) + fib(i-2)
}</lang>
Lazy sequence
<lang scala>//syntactic sugar for Stream.cons, this is unnecessary but makes the definition prettier //Stream.cons(head,stream) becomes head::stream //I think 2.8 will have #:: class PrettyStream[A](str: =>Stream[A]) {
def ::(hd: A) = Stream.cons(hd, str)
} implicit def streamToPrettyStream[A](str: =>Stream[A]) = new PrettyStream(str)
def fib: Stream[Int] = 0 :: 1 :: fib.zip(fib.tail).map{case (a,b) => a + b}</lang> Following code works in Scala 2.8: <lang scala>def fib: Stream[Int] = 0 #:: 1 #:: fib.zip(fib.tail).map{case (a,b) => a + b}</lang>
Tail recursive
<lang scala>def fib(i:Int):Int = {
def fib2(i:Int, a:Int, b:Int):Int = i match{
case 1 => b
case _ => fib2(i-1, b, a+b)
}
fib2(i,1,0)
}</lang>
Scheme
Iterative
<lang scheme>(define (fib-iter n)
(do ((num 2 (+ num 1))
(fib-prev 1 fib)
(fib 1 (+ fib fib-prev)))
((>= num n) fib)))</lang>
Recursive
<lang scheme>(define (fib-rec n)
(if (< n 2)
n
(+ (fib-rec (- n 1))
(fib-rec (- n 2)))))</lang>
This version is tail recursive: <lang scheme>(define (fib n)
(let loop ((a 0) (b 1) (n n))
(if (= n 0) a
(loop b (+ a b) (- n 1)))))
</lang>
Dijkstra Algorithm
<lang scheme>;;; Fibonacci numbers using Edsger Dijkstra's algorithm
(define (fib n)
(define (fib-aux a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-aux a
b
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))
(/ count 2)))
(else
(fib-aux (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
(fib-aux 1 0 0 1 n))</lang>
Seed7
Recursive
<lang seed7>const func integer: fib (in integer: number) is func
result
var integer: result is 1;
begin
if number > 2 then
result := fib(pred(number)) + fib(number - 2);
elsif number = 0 then
result := 0;
end if;
end func;</lang>
Original source: [2]
Iterative
This funtion uses a bigInteger result:
<lang seed7>const func bigInteger: fib (in integer: number) is func
result
var bigInteger: result is 1_;
local
var integer: i is 0;
var bigInteger: a is 0_;
var bigInteger: c is 0_;
begin
for i range 1 to pred(number) do
c := a;
a := result;
result +:= c;
end for;
end func;</lang>
Original source: [3]
Slate
<lang slate>n@(Integer traits) fib [
n <= 0 ifTrue: [^ 0]. n = 1 ifTrue: [^ 1]. (n - 1) fib + (n - 2) fib
].
slate[15]> 10 fib = 55. True</lang>
Smalltalk
<lang smalltalk>|fibo| fibo := [ :i |
|ac t|
ac := Array new: 2.
ac at: 1 put: 0 ; at: 2 put: 1.
( i < 2 )
ifTrue: [ ac at: (i+1) ]
ifFalse: [
2 to: i do: [ :l |
t := (ac at: 2).
ac at: 2 put: ( (ac at: 1) + (ac at: 2) ).
ac at: 1 put: t
].
ac at: 2.
]
].
0 to: 10 do: [ :i |
(fibo value: i) displayNl
]</lang>
SNOBOL4
Recursive
<lang snobol> define("fib(a)") :(fib_end) fib fib = lt(a,2) a :s(return) fib = fib(a - 1) + fib(a - 2) :(return) fib_end
while a = trim(input) :f(end) output = a " " fib(a) :(while) end</lang>
Tail-recursive
<lang SNOBOL4> define('trfib(n,a,b)') :(trfib_end) trfib trfib = eq(n,0) a :s(return)
trfib = trfib(n - 1, a + b, a) :(return)
trfib_end</lang>
Iterative
<lang SNOBOL4> define('ifib(n)f1,f2') :(ifib_end) ifib ifib = le(n,2) 1 :s(return)
f1 = 1; f2 = 1
if1 ifib = gt(n,2) f1 + f2 :f(return)
f1 = f2; f2 = ifib; n = n - 1 :(if1)
ifib_end</lang>
Analytic
Note: Snobol4+ lacks built-in sqrt( ) function.
<lang SNOBOL4> define('afib(n)s5') :(afib_end) afib s5 = sqrt(5)
afib = (((1 + s5) / 2) ^ n - ((1 - s5) / 2) ^ n) / s5
afib = convert(afib,'integer') :(return)
afib_end</lang>
Test and display all, Fib 1 .. 10
<lang SNOBOL4>loop i = lt(i,10) i + 1 :f(show)
s1 = s1 fib(i) ' ' ; s2 = s2 trfib(i,0,1) ' '
s3 = s3 ifib(i) ' '; s4 = s4 afib(i) ' ' :(loop)
show output = s1; output = s2; output = s3; output = s4 end</lang>
Output:
1 1 2 3 5 8 13 21 34 55 1 1 2 3 5 8 13 21 34 55 1 1 2 3 5 8 13 21 34 55 1 1 2 3 5 8 13 21 34 55
SNUSP
This is modular SNUSP (which introduces @ and # for threading).
Iterative
<lang snusp> @!\+++++++++# /<<+>+>-\ fib\==>>+<<?!/>!\ ?/\
#<</?\!>/@>\?-<<</@>/@>/>+<-\
\-/ \ !\ !\ !\ ?/#</lang>
Recursive
<lang snusp> /========\ />>+<<-\ />+<-\ fib==!/?!\-?!\->+>+<<?/>>-@\=====?/<@\===?/<#
| #+==/ fib(n-2)|+fib(n-1)|
\=====recursion======/!========/</lang>
Standard ML
Recursion
This version is tail recursive. <lang sml>fun fib n =
let
fun fib' (0,a,b) = a | fib' (n,a,b) = fib' (n-1,a+b,a)
in
fib' (n,0,1)
end</lang>
StreamIt
<lang streamit>void->int feedbackloop Fib {
join roundrobin(0,1);
body in->int filter {
work pop 1 push 1 peek 2 { push(peek(0) + peek(1)); pop(); }
};
loop Identity<int>;
split duplicate;
enqueue(0);
enqueue(1);
}</lang>
Tcl
Simple Version
These simple versions do not handle negative numbers -- they will return N for N < 2
Iterative
<lang tcl>proc fibiter n {
if {$n < 2} {return $n}
set prev 1
set fib 1
for {set i 2} {$i < $n} {incr i} {
lassign [list $fib [incr fib $prev]] prev fib
}
return $fib
}</lang>
Recursive
<lang tcl>proc fib {n} {
if {$n < 2} then {expr {$n}} else {expr {[fib [expr {$n-1}]]+[fib [expr {$n-2}]]} }
}</lang>
The following
: defining a procedure in the ::tcl::mathfunc namespace allows that proc to be used as a function in expr expressions.
<lang tcl>proc tcl::mathfunc::fib {n} {
if { $n < 2 } {
return $n
} else {
return [expr {fib($n-1) + fib($n-2)}]
}
}
- or, more tersely
proc tcl::mathfunc::fib {n} {expr {$n<2 ? $n : fib($n-1) + fib($n-2)}}</lang>
E.g.:
<lang tcl>expr {fib(7)} ;# ==> 13
namespace path tcl::mathfunc #; or, interp alias {} fib {} tcl::mathfunc::fib fib 7 ;# ==> 13</lang>
Tail-Recursive
In Tcl 8.6 a tailcall function is available to permit writing tail-recursive functions in Tcl. This makes deeply recursive functions practical. The availability of large integers also means no truncation of larger numbers. <lang tcl>proc fib-tailrec {n} {
proc fib:inner {a b n} {
if {$n < 1} {
return $a
} elseif {$n == 1} {
return $b
} else {
tailcall fib:inner $b [expr {$a + $b}] [expr {$n - 1}]
}
}
return [fib:inner 0 1 $n]
}</lang>
% fib-tailrec 100 354224848179261915075
Handling Negative Numbers
Iterative
<lang tcl>proc fibiter n {
if {$n < 0} {
set n [expr {abs($n)}]
set sign [expr {-1**($n+1)}]
} else {
set sign 1
}
if {$n < 2} {return $n}
set prev 1
set fib 1
for {set i 2} {$i < $n} {incr i} {
lassign [list $fib [incr fib $prev]] prev fib
}
return [expr {$sign * $fib}]
} fibiter -5 ;# ==> 5 fibiter -6 ;# ==> -8</lang>
Recursive
<lang tcl>proc tcl::mathfunc::fib {n} {expr {$n<-1 ? -1**($n+1) * fib(abs($n)) : $n<2 ? $n : fib($n-1) + fib($n-2)}} expr {fib(-5)} ;# ==> 5 expr {fib(-6)} ;# ==> -8</lang>
For the Mathematically Inclined
This works up to , after which the limited precision of IEEE double precision floating point arithmetic starts to show.
<lang tcl>proc fib n {expr {round((.5 + .5*sqrt(5)) ** $n / sqrt(5))}}</lang>
TI-83 BASIC
Unoptimized fibonacci program
<lang ti83b> :Disp "0" //Dirty, I know, however this does not interfere with the code
:Disp "1" :Disp "1" :1→A :1→B :0→C :Goto 1 :Lbl 1 :A+B→C :Disp C :B→A :C→B :Goto 1 </lang>
TI-89 BASIC
Unoptimized recursive implementation.
<lang ti89b>fib(n) Func
If n = 0 or n = 1 Then Return n ElseIf n ≥ 2 Then Return fib(n-1) + fib(n-2) EndIf
EndFunc</lang>
TUSCRIPT
<lang tuscript> $$ MODE TUSCRIPT ASK "What fibionacci number do you want?": searchfib="" IF (searchfib!='digits') STOP Loop n=0,{searchfib}
IF (n==0) THEN fib=fiba=n ELSEIF (n==1) THEN fib=fibb=n ELSE fib=fiba+fibb, fiba=fibb, fibb=fib ENDIF IF (n!=searchfib) CYCLE PRINT "fibionacci number ",n,"=",fib
ENDLOOP </lang> Output:
What fibionacci number do you want? >12 fibionacci number 12=144
Output:
What fibionacci number do you want? >31 fibionacci number 31=1346269
Output:
What fibionacci number do you want? >46 fibionacci 46=1836311903
UnixPipes
<lang bash>echo 1 |tee last fib ; tail -f fib | while read x do
cat last | tee -a fib | xargs -n 1 expr $x + |tee last
done</lang>
UNIX Shell
<lang bash>#!/bin/bash
a=0 b=1 max=$1
for (( n=1; "$n" <= "$max"; $((n++)) )) do
a=$(($a + $b)) echo "F($n): $a" b=$(($a - $b))
done</lang>
Recursive:
<lang bash>fib() {
local n=$1 [ $n -lt 2 ] && echo -n $n || echo -n $(( $( fib $(( n - 1 )) ) + $( fib $(( n - 2 )) ) ))
}</lang>
Ursala
All three methods are shown here, and all have unlimited precision. <lang Ursala>#import std
- import nat
iterative_fib = ~&/(0,1); ~&r->ll ^|\predecessor ^/~&r sum
recursive_fib = {0,1}^?<a/~&a sum^|W/~& predecessor^~/~& predecessor
analytical_fib =
%np+ -+
mp..round; ..mp2str; sep`+; ^CNC/~&hh take^\~&htt %np@t,
(mp..div^|\~& mp..sub+ ~~ @rlX mp..pow_ui)^lrlPGrrPX/~& -+
^\~& ^(~&,mp..sub/1.E0)+ mp..div\2.E0+ mp..add/1.E0,
mp..sqrt+ ..grow/5.E0+-+-</lang>
The analytical method uses arbitrary precision floating point arithmetic from the mpfr library and then converts the result to a natural number. Sufficient precision for an exact result is always chosen based on the argument. This test program computes the first twenty Fibonacci numbers by all three methods. <lang Ursala>#cast %nLL
examples = <.iterative_fib,recursive_fib,analytical_fib>* iota20</lang> output:
< <0,0,0>, <1,1,1>, <1,1,1>, <2,2,2>, <3,3,3>, <5,5,5>, <8,8,8>, <13,13,13>, <21,21,21>, <34,34,34>, <55,55,55>, <89,89,89>, <144,144,144>, <233,233,233>, <377,377,377>, <610,610,610>, <987,987,987>, <1597,1597,1597>, <2584,2584,2584>, <4181,4181,4181>>
V
Generate n'th fib by using binary recursion
<lang v>[fib
[small?] []
[pred dup pred]
[+]
binrec].</lang>
VBA
Like Visual Basic .NET, but with keyword "Public" and type Long instead of Decimal:
<lang VBA> Public Function Fib(n As Integer) As Long
Dim fib0, fib1, sum As Long
Dim i As Integer
fib0 = 0
fib1 = 1
For i = 1 To n
sum = fib0 + fib1
fib0 = fib1
fib1 = sum
Next
Fib = fib0
End Function </lang>
The (slow) recursive version:
<lang VBA> Public Function RFib(Term As Integer) As Long
If Term < 2 Then RFib = Term Else RFib = RFib(Term - 1) + RFib(Term - 2)
End Function </lang>
VBScript
Non-recursive, object oriented, generator
Defines a generator class, with a default Get property. Uses Currency for larger-than-Long values. Tests for overflow and switches to Double. Overflow information also available from class.
Class Definition:
<lang vb>class generator dim t1 dim t2 dim tn dim cur_overflow
Private Sub Class_Initialize cur_overflow = false t1 = ccur(0) t2 = ccur(1) tn = ccur(t1 + t2) end sub
public default property get generated on error resume next
generated = ccur(tn) if err.number <> 0 then generated = cdbl(tn) cur_overflow = true end if t1 = ccur(t2) if err.number <> 0 then t1 = cdbl(t2) cur_overflow = true end if t2 = ccur(tn) if err.number <> 0 then t2 = cdbl(tn) cur_overflow = true end if tn = ccur(t1+ t2) if err.number <> 0 then tn = cdbl(t1) + cdbl(t2) cur_overflow = true end if on error goto 0 end property
public property get overflow overflow = cur_overflow end property
end class</lang>
Invocation:
<lang vb>dim fib set fib = new generator dim i for i = 1 to 100 wscript.stdout.write " " & fib if fib.overflow then wscript.echo exit for end if next</lang>
Output:
<lang vbscript> 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 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393</lang>
Vedit macro language
Iterative
Calculate fibonacci(#1). Negative values return 0. <lang vedit>:FIBONACCI:
- 11 = 0
- 12 = 1
Repeat(#1) {
#10 = #11 + #12 #11 = #12 #12 = #10
} Return(#11)</lang>
Visual Basic .NET
Platform: .NET
<lang vbnet>Function Fib(ByVal n As Integer) As Decimal
Dim fib0, fib1, sum As Decimal
Dim i As Integer
fib0 = 0
fib1 = 1
For i = 1 To n
sum = fib0 + fib1
fib0 = fib1
fib1 = sum
Next
Fib = fib0
End Function</lang>
Recursive
<lang vbnet>Function Seq(ByVal Term As Integer)
If Term < 2 Then Return Term
Return Seq(Term - 1) + Seq(Term - 2)
End Function</lang>
Wrapl
Generator
<lang wrapl>DEF fib() (
VAR seq <- [0, 1]; EVERY SUSP seq:values; REP SUSP seq:put(seq:pop + seq[1])[-1];
);</lang> To get the 17th number: <lang wrapl>16 SKIP fib();</lang> To get the list of all 17 numbers: <lang wrapl>ALL 17 OF fib();</lang>
Iterator
Using type match signature to ensure integer argument: <lang wrapl>TO fib(n @ Integer.T) (
VAR seq <- [0, 1]; EVERY 3:to(n) DO seq:put(seq:pop + seq[1]); RET seq[-1];
);</lang>
XQuery
<lang xquery>declare function local:fib($n as xs:integer) as xs:integer {
if($n < 2) then $n else local:fib($n - 1) + local:fib($n - 2)
};</lang>
- Programming Tasks
- Arithmetic operations
- Recursion
- Memoization
- Classic CS problems and programs
- ActionScript
- AppleScript
- Ada
- ALGOL 68
- AutoHotkey
- AutoIt
- AWK
- BASIC
- Batch File
- Bc
- Befunge
- Brainf***
- Bracmat
- Brat
- C
- C++
- GMP
- C sharp
- Cat
- Chef
- CMake
- Clojure
- CoffeeScript
- Common Lisp
- D
- Dart
- Delphi
- DWScript
- E
- Ela
- Erlang
- Euphoria
- FALSE
- Factor
- Fancy
- Falcon
- Fantom
- Forth
- Fortran
- F Sharp
- GAP
- Gecho
- Go
- Groovy
- HaXe
- Haskell
- Hope
- HicEst
- Icon
- Unicon
- Icon Programming Library
- IDL
- J
- Java
- JavaScript
- Joy
- Liberty BASIC
- Lisaac
- Logo
- Lua
- M4
- Mathematica
- MATLAB
- MAXScript
- Mercury
- Metafont
- Mirah
- ML/I
- Modula-3
- MUMPS
- Nemerle
- NetRexx
- NewLISP
- Nimrod
- MASM
- Objeck
- OCaml
- Octave
- OPL
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PIR
- Pike
- PL/I
- PL/SQL
- Pop11
- PostScript
- PowerBASIC
- PowerShell
- Prolog
- Pure
- PureBasic
- Purity
- Python
- R
- Racket
- REALbasic
- Retro
- REXX
- Ruby
- SAS
- Sather
- Scala
- Scheme
- Seed7
- Slate
- Smalltalk
- SNOBOL4
- SNUSP
- Standard ML
- StreamIt
- Tcl
- TI-83 BASIC
- TI-89 BASIC
- TUSCRIPT
- UnixPipes
- UnixPipes examples needing attention
- Examples needing attention
- UNIX Shell
- Ursala
- V
- VBA
- VBScript
- Vedit macro language
- Visual Basic .NET
- Wrapl
- XQuery
- Arithmetic