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). Support for negative n 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>
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
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; ENTIER( (p**n + q**n) / sqrt 5 ) );
Iterative
PROC iterative fibonacci = (INT n)INT:
CASE n+1 IN
0, 1, 1, 2, 3
OUT
[]INT init = (0, 1);
[0:1]INT cache := init[@0];
FOR i FROM UPB cache + 1 TO n DO
cache[i MOD 2] := cache[0] + cache[1]
OD;
cache[n MOD 2]
ESAC;
Recursive
PROC recursive fibonacci = (INT n)INT: ( n < 2 | n | fib(n-1) + fib(n-2));
Generative
<lang algol>MODE YIELDINT = PROC(INT)VOID; MODE FORINT = PROC(YIELDINT)VOID;
PROC for fibonacci = (INT n, YIELDINT yield)VOID: (
[0:1]INT cache := []INT(0,1)[@0]; yield(cache[0]); yield(cache[1]); FOR i FROM UPB cache + 1 TO n DO cache[i MOD 2] := cache[0] + cache[1]; yield(cache[i MOD 2]) OD
);
- FOR n IN fibonacci(30) DO #
for fibonacci(30, (INT n)VOID:
print((" ",whole(n,0)))
); 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
AutoHotkey
Search autohotkey.com: sequence
Iterative
Translated from c example <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>
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 n
sum = n1 + n2 n1 = n2 n2 = sum
NEXT k itFib = n1
END FUNCTION </lang>
This one calculates each value once, as needed, and stores the results in an array for later retreival. <lang qbasic>DECLARE FUNCTION fibonacci& (n AS INTEGER)
REDIM SHARED fibNum(1) AS LONG
fibNum(1) = 1
'*****sample inputs***** PRINT fibonacci(0) PRINT fibonacci(13) PRINT fibonacci(42) PRINT fibonacci(47) 'should be rejected PRINT fibonacci(-1) 'should be rejected '*****sample inputs*****
FUNCTION fibonacci& (n AS INTEGER)
SELECT CASE n
CASE 0 TO 46
SHARED fibNum() AS LONG
DIM u AS INTEGER, Loop0 AS INTEGER
u = UBOUND(fibNum)
IF n > u THEN
REDIM PRESERVE fibNum(n) AS LONG
FOR Loop0 = u + 1 TO n
fibNum(Loop0) = fibNum(Loop0 - 1) + fibNum(Loop0 - 2)
NEXT
END IF
fibonacci = fibNum(n)
CASE ELSE
'no negative numbers
'also, many BASICs are limited to signed 32-bit ints (LONG)
'fib(47)=&hB11924E1
fibonacci = -1
END SELECT
END FUNCTION</lang> Outputs:
0 233 267914296 -1 -1
This one uses a pre-generated list, requiring much less run-time processor usage. <lang qbasic>DATA 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) AS LONG
FOR n = 0 TO 46
READ fibNum(n)
NEXT
'*****sample inputs***** PRINT fibNum(0) PRINT fibNum(13) PRINT fibNum(42) '*****sample inputs***** </lang>
Recursive
<lang qbasic> FUNCTION recFib (n)
IF (n < 2) THEN
recFib = n
ELSE
recFib = recFib(n - 1) + recFib(n - 2)
END IF
END FUNCTION </lang>
bc
iterative
#! /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
Befunge
00:.1:.>:"@"8**++\1+:67+`#@_v
^ .:\/*8"@"\%*8"@":\ <
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>
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)
{if (n < 2) return n;
long long unsigned last = 0, this = 1, new;
for (unsigned 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 <functional>
- include <iostream>
unsigned int fibonacci(unsigned int n) {
if (n == 0) return 0; int *array = new int[n+1]; array[0] = 0; array[1] = 1; std::transform(array, array+n-1, array+1, array+2, std::plus<int>()); // "array" now contains the Fibonacci sequence from 0 up int result = array[n]; delete [] array; return result;
} </lang>
Far-fetched version using adjacent_difference: <lang cpp>
- include <numeric>
- include <functional>
- include <iostream>
unsigned int fibonacci(unsigned int n) {
if (n == 0) return 0; int *array = new int[n]; array[0] = 1; std::adjacent_difference(array, array+n-1, array+1, std::plus<int>()); // "array" now contains the Fibonacci sequence from 1 up int result = array[n-1]; delete [] array; return result;
} </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>
C#
Recursive
<lang csharp>static long recFib(int n) {
if (n < 2) return n; return recFib(n - 1) + recFib(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>
D
Here are four versions of Fibonacci Number generating functions.
FibD has an argument limit of magnitude 82 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.
All four functions have support for negative arguments.
<lang d>
module fibonacci ;
import std.stdio ;
import std.math ;
import std.conv ;
long FibD(int m) { // Direct Calculation, correct for abs(m) <= 82
const real sqrt5r = 0.44721359549995793928L ; // 1 / sqrt(5) const real golden = 1.6180339887498948482L ; // (1 + sqrt(5)) / 2 ; real sign = (m < 0) && (1 & m ^ 1) ? -1.0L : 1.0L ; return rndtol(pow(golden, abs(m)) * sign * sqrt5r) ;
} long FibI(int m) { // Iterative
int sign = (m < 0) && (1 & m ^ 1) ? -1 : 1 ;
int n = m < 0 ? -m : m ;
if (n < 2)
return n ;
long prevFib = 0 ;
long thisFib = 1 ;
for(int i = 1 ; i < n ;i++) {
long tmp = thisFib ;
thisFib += prevFib ;
prevFib = tmp ;
}
return thisFib*sign ;
} long FibR(int m) { // Recursive
if (m == 0 || m == 1) return m ; return (m >= 0) ? FibR(m-1) + FibR(m-2) : (1 & m ^ 1) ? - FibR(-m) : FibR(-m) ;
} long FibO(int m) { // Optimized Recursive
static long[] fib = [0,1] ;
int sign = (m < 0) && (1 & m ^ 1) ? -1 : 1 ; int n = m < 0 ? -m : m ;
if(n >= fib.length ) fib ~= FibO(n-2) + FibO(n-1) ; return fib[n]*sign ;
} void main(string[] args) {
int k = args.length > 1 ? toInt(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), FibO(k - 1), FibO(k - 2) ) ;
writefln("O : %20d <- %20d + %20d", FibO(k), FibO(k - 1), FibO(k - 2) ) ;
} </lang> Output for n = 83:
Fib( 83) = D : 99194853094755496 <- 61305790721611591 + 37889062373143906 I : 99194853094755497 <- 61305790721611591 + 37889062373143906 O : 99194853094755497 <- 61305790721611591 + 37889062373143906
E
def fib(n) {
var s := [0, 1]
for _ in 0..!n {
def [a, b] := s
s := [b, a+b]
}
return s[0]
}
(This version defines fib(0) = 0 because OEIS A000045 does.)
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>
FALSE
[0 1[@$][1-@@\$@@+\]#%%]f:
Forth
: fib ( n -- fib ) 0 1 rot 0 ?do over + swap loop drop ;
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.
#light
open Microsoft.FSharp.Math
let fibonacci n : bigint =
let rec f a b n =
match n with
| 0I -> a
| 1I -> b
| n -> (f b (a + b) (n - 1I))
f 0I 1I n
> fibonacci 100I ;; val it : bigint = 354224848179261915075I
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
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.
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"
IDL
Recursive
<lang>
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>
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>
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
See J Wiki: Fibonacci Sequence.
Java
Iterative
<lang java5> 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 java5> public static long recFibN(int n){
if(n < 2) return n;
return 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(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>
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;
} for (var i=0; i<10; ++i) alert(fib(i)); </lang>
Joy
DEFINE fib ==
[small]
[]
[pred dup pred]
[+]
binrec .
Logo
to fib_acc :n :a :b if :n < 1 [output :a] output fib_acc :n-1 :b :a+:b end to fib :n output fib_acc :n 0 1 end
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
fib[0] = 0 fib[1] = 1 fib[n_Integer] := fib[n - 1] + fib[n - 2]
An optimization is to cache the values already calculated:
fib[0] = 0 fib[1] = 1 fib[n_Integer] := fib[n] = fib[n - 1] + fib[n - 2]
MAXScript
Iterative
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
)
)
Recursive
fn fibRec n =
(
if n < 2 then
(
n
)
else
(
fibRec (n - 1) + fibRec (n - 2)
)
)
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>
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>
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, a, b) with
| (0, a, b) -> 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 n =
let rec fib_aux f0 f1 count =
match count with
| 0 -> f0
| 1 -> f1
| _ -> fib_aux f1 (f1 +/ f0) (count - 1)
in
fib_aux (num_of_int 0) (num_of_int 1) n
</lang>
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>
Oz
fun{FibI N} %% Iterative using Cell
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 %% return result
end
fun{Fibi N} %% Iterative(or Recursive?) by arguments swapping
fun{FibIter N A B}
if N == 0 then B
else {FibIter N-1 A+B A} end
end
in
if N < 2 then N
else {FibIter N 1 0} end
end
fun{FibR N} %% Simple Recursive
if N < 2 then N
else {FibR N-1} + {FibR N-2} end
end
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, fm1, k: integer; begin f0 := 0; fm1 := 1; for k := 1 to n do begin f1:= fm1 + f0; fm1 := f0; f0 := f1 end; fib := f0 end;
</lang>
Perl
Iterative
<lang perl> sub fibIter {
my $n = shift;
if ($n < 2) {
return $n;
}
my $fibPrev = 1;
my $fib = 1;
for (2..$n) {
($fibPrev, $fib) = ($fib, $fib + $fibPrev);
}
return $fib;
} </lang>
Recursive
<lang perl> sub fibRec {
my $n = shift; return $n <= 2 ? 1 : fibRec($n-1) + fibRec($n-2);
} </lang>
Pop11
define fib(x);
lvars a , b;
1 -> a;
1 -> b;
repeat x - 1 times
(a + b, b) -> (b, a);
endrepeat;
a;
enddefine;
PostScript
Enter the desired number for "n" and run through your favorite postscript previewer or send to your postscript printer:
<lang> %!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>
Prolog
<lang prolog>fib(0, 0). fib(1, 1). fib(N, X) :- N>1, N1 is N-1, N2 is N-2, fib(N1, X1), fib(N2, X2), X is X1+X2.</lang>
Python
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>
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>
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>
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>
Example use
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
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)
(letrec ((fib_aux (lambda (n a b)
(if (= n 0)
a
(fib_aux (- n 1) b (+ a b))))))
(fib_aux n 0 1)))
</lang>
Dijkstra Algorithm
<lang scheme>
- Fibonacci numbers using Edsger Dijkstra's algorithm
- http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF
(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>
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>
SNUSP
Iterative
@!\+++++++++# /<<+>+>-\
fib\==>>+<<?!/>!\ ?/\
#<</?\!>/@>\?-<<</@>/@>/>+<-\
\-/ \ !\ !\ !\ ?/#
Recursive
/========\ />>+<<-\ />+<-\
fib==!/?!\-?!\->+>+<<?/>>-@\=====?/<@\===?/<#
| #+==/ fib(n-2)|+fib(n-1)|
\=====recursion======/!========/
Standard ML
Recursion
This version is tail recursive.
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
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>
UnixPipes
Uses fib and last as file buffers for computation. could have made fib as a fifo and changed tail -f to cat fib but it is not line buffered.
<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>
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 numbers 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
[fib
[small?] []
[pred dup pred]
[+]
binrec].
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>
- Clarified and Needing Review
- Programming Tasks
- Arithmetic operations
- Recursion
- Classic CS problems and programs
- ActionScript
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BASIC
- Bc
- Befunge
- Brainf***
- C
- C++
- GMP
- C sharp
- Common Lisp
- D
- E
- Erlang
- FALSE
- Forth
- Fortran
- F Sharp
- Groovy
- Haskell
- IDL
- J
- Java
- JavaScript
- Joy
- Logo
- M4
- Mathematica
- MAXScript
- Metafont
- Modula-3
- OCaml
- Octave
- Oz
- Pascal
- Perl
- Pop11
- PostScript
- Prolog
- Python
- R
- Ruby
- Scheme
- Slate
- Smalltalk
- SNUSP
- Standard ML
- Tcl
- UnixPipes
- UNIX Shell
- Ursala
- V
- Vedit macro language
- Visual Basic .NET