Fibonacci numbers
Fibonacci numbers is a numerical sequence, in which first two elements are equal to 1, and each remaining number is equal to the sum of the previous two: F(1) = F(2) = 1, F(n) = F(n-1) + F(n-2).
(Note that this is different than the traditional definition of the Fibonacci function, where F(0) = F(1) = 1, but it doesn’t really matter, as the output is the same.)
The task is to output first 16 Fibonacci numbers in the following format:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …
Note that this example can be implemented in several ways:
- using the recurrence equation itself. The least efficient way which illustrates the usage of recurrent functions.
- saving calculated numbers in an array. Illustrates the usage of arrays.
- using Binet’s formula. Illustrates the usage of math functions.
Example for versions Borland C++ Builder 6, g++ 3.4.5, Microsoft Visual C++ 6, Microsoft Visual C++ 9 (2008)
This example uses recursive definition of Fibonacci numbers.
#include <iostream>
int fibonacci(int n)
{
return ( n<=2 ? 1 : fibonacci(n-1) + fibonacci(n-2) );
}
int main(void)
{
for (int n=1; n<=16; n++)
std::cout << fibonacci(n) << ", ";
std::cout << "..." << std::endl;
return 0;
}
Example for versions gcj 3.4.5, Sun Java 6
This example uses recursive definition of Fibonacci numbers.
public class Fibonacci {
static int fibonacci(int n)
{
return (n<=2 ? 1 : fibonacci(n-1) + fibonacci(n-2));
}
public static void main(String[] args)
{
for (int n=1; n<=16; n++)
System.out.print(fibonacci(n)+", ");
System.out.println("...");
}
}
Example for versions Oracle 10g SQL
Pure SQL doesn’t support loops, recursions or user-defined functions. Besides, concatenating fields from multiple rows of a table or a subquery is not a standard aggregate function. This example uses:
-
Binet’s formula and math functions
round,powerandsqrtto calculate n-th Fibonacci number; - pseudocolumn level to construct a pseudotable t1 containing numbers 1 through 16;
-
built-in function
SYS_CONNECT_BY_PATHto concatenate the resulting numbers in ascending order.
SELECT REPLACE(MAX(SYS_CONNECT_BY_PATH(fib||', ', '/')),'/','')||'...' fiblist
FROM (
SELECT n, fib, ROW_NUMBER()
OVER (ORDER BY n) r
FROM (select n, round((power((1+sqrt(5))*0.5, n)-power((1-sqrt(5))*0.5, n))/sqrt(5)) fib
from (select level n
from dual
connect by level <= 16) t1) t2
)
START WITH r=1
CONNECT BY PRIOR r = r-1;
Example for versions EsCo 0.511 (Brainfuck), Müller's Brainfuck 2.0
This example uses iterative definition of Fibonacci numbers. A high-level description of what it does is: store two last numbers in variables c4 and c5 (initially c4=0, c5=1), print the number stored in c5 (this operation takes the major part of the code), calculate next number (c6 = c5+c4), and move the numbers sequence one number back (c4 = c5, c5 = c6). A low-level description is given in the comments, notation “cXvY” meaning that after execution of the commands in the line the data pointer is at cell X, and the value at this cell is Y. A total of 12 memory cells is used.
This example uses one minor cheat: classic Brainfuck interpreter uses byte variables to store values of memory cells, so Fibonacci numbers 14 through 16 will cause overflow. Writing long arithmetics in Brainfuck is a bit of overkill, so in this example we assume that memory cells can store integer values.
++++++++++++++++++++++++++++++++++++++++++++ c1v44 : ASCII code of comma
>++++++++++++++++++++++++++++++++ c2v32 : ASCII code of space
>++++++++++++++++ c3v11 : quantity of numbers to be calculated
> c4v0 : zeroth Fibonacci number (will not be printed)
>+ c5v1 : first Fibonacci number
<< c3 : loop counter
[ block : loop to print (i)th number and calculate next one
>> c5 : the number to be printed
block : divide c5 by 10 (preserve c5)
> c6v0 : service zero
>++++++++++ c7v10 : divisor
<< c5 : back to dividend
[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<] c5v0 : divmod algo; results in 0 n d_n%d n%d n/d
>[<+>-] c5 : move dividend back to c5 and clear c6
>[-] c7v0 : clear c7
>> block : c9 can have two digits; divide it by ten again
>++++++++++ c10v10: divisor
< c9 : back to dividend
[->-[>+>>]>[+[-<+>]>+>>]<<<<<] c9v0 : another divmod algo; results in 0 d_n%d n%d n/d
>[-] c10v0 : clear c10
>>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]c12v0 : print nonzero n/d (first digit) and clear c12
<[++++++++++++++++++++++++++++++++++++++++++++++++.[-]] c11v0 : print nonzero n%d (second digit) and clear c11
<<<++++++++++++++++++++++++++++++++++++++++++++++++.[-] c8v0 : print any n%d (last digit) and clear c8
<<<<<<<.>. c1c2 : print comma and space
block : actually calculate next Fibonacci in c6
>>[>>+<<-] c4v0 : move c4 to c6 (don't need to preserve it)
>[>+<<+>-] c5v0 : move c5 to c6 and c4 (need to preserve it)
>[<+>-] c6v0 : move c6 with sum to c5
<<<- c3 : decrement loop counter
]
<<++... c1 : output three dots
Example for versions Microsoft SQL Server 2005
This example uses a kind of iterative definition of Fibonacci numbers, implemented with a recursive query. Each row of recursive query contains two consecutive numbers of the sequence, and next row is calculated as (last number, sum of numbers) of previous row. This way most numbers are stored twice, so only first number of each row is included in the result.
with fibonacci(a, b) as
(
select 1, 1
union all
select b, a+b from fibonacci where b < 1000
)
SELECT cast(a as varchar)+', ' AS [text()]
FROM fibonacci
FOR XML PATH ('')
Example for versions Interactive FP
This example works in a same way as the factorial one, but without readability functions added.
{ seq ( = @ [id, %1] -> %<1> ; concat @ [ seq @ - @ [id, %1] , [id] ] ) }
{ fibonacci ( < @ [id, %3] -> %1 ; + @ [ fibonacci @ - @ [id, %1], fibonacci @ - @ [id, %2] ] ) }
&fibonacci @ seq:16
Example for versions Corman Common Lisp 3.0, gcl 2.6.6
This example uses recursive definition of Fibonacci numbers and expands use of loop macro to finally clause (expression evaluated after the loop is done).
(defun fibonacci (n)
(if (< n 3)
1
(+ (fibonacci (- n 1)) (fibonacci (- n 2))) ) )
(loop for i from 1 to 16
do (format t "~D, " (fibonacci i))
finally (format t "...~%") )
Example for versions Corman Common Lisp 3.0, gcl 2.6.6
This example uses iterative definition of Fibonacci numbers, though expressed through recursive calls of fib-iter.
(defun fibonacci (n)
(defun fib-iter (a b count)
(if (zerop count)
b
(fib-iter (+ a b) a (- count 1)) ) )
(fib-iter 1 0 n) )
(loop for i from 1 to 16
do (format t "~D, " (fibonacci i))
finally (format t "...~%") )
Example for versions Microsoft Visual Basic 6
This example uses recursive definition of Fibonacci numbers.
Option Explicit
Declare Function AllocConsole Lib "kernel32" () As Long
Declare Function FreeConsole Lib "kernel32" () As Long
Declare Function CloseHandle Lib "kernel32" (ByVal hObject As Long) As Long
Declare Function GetStdHandle Lib "kernel32" (ByVal nStdHandle As Long) As Long
Declare Function WriteConsole Lib "kernel32" Alias "WriteConsoleA" _
(ByVal hConsoleOutput As Long, lpBuffer As Any, ByVal _
nNumberOfCharsToWrite As Long, lpNumberOfCharsWritten As Long, _
lpReserved As Any) As Long
Declare Function Sleep Lib "kernel32" (ByVal dwMilliseconds As Long) As Long
Public Function Fibonacci(ByVal n As Integer) As Integer
If (n <= 2) Then
Fibonacci = 1
Else
Fibonacci = Fibonacci(n - 1) + Fibonacci(n - 2)
End If
End Function
Private Sub Main()
'create a console instance
AllocConsole
'get handle of console output
Dim hOut As Long
hOut = GetStdHandle(-11&)
'output string to console output
Dim s As String
Dim i As Integer
For i = 1 To 16 Step 1
s = Fibonacci(i) & ", "
WriteConsole hOut, ByVal s, Len(s), vbNull, vbNull
Next i
s = "..." & vbCrLf
WriteConsole hOut, ByVal s, Len(s), vbNull, vbNull
'make a pause to look at the output
Sleep 2000
'close the handle and destroy the console
CloseHandle hOut
FreeConsole
End Sub
Example for versions QBasic 1.1, QuickBASIC 4.5
Numbers which have already been calculated are stored in array F and are retrieved from it to calculate the next ones. To get program output in required format, the numbers in the array are concatenated to form one string with required delimiters. STR$ function converts a number to a string.
DIM F(16)
F(1) = 1
F(2) = 1
FOR i = 3 TO 16:
F(i) = F(i - 1) + F(i - 2)
NEXT i
DIM S AS STRING
S = ""
FOR i = 1 TO 16:
S = S + STR$(F(i)) + ", "
NEXT i
S = S + "..."
PRINT S
Example for versions QBasic 1.1, QuickBASIC 4.5
This example uses recursive definition of Fibonacci numbers. Each call of PRINT function prints the arguments to a separate line and adds a space before and after printed number, so program output looks like this:
1 ,
1 ,
2 ,
3 ,
5 ,
8 ,
13 ,
21 ,
34 ,
55 ,
89 ,
144 ,
233 ,
377 ,
610 ,
987 ,
…
DECLARE FUNCTION fibonacci (n)
FOR i = 1 TO 16:
PRINT fibonacci(i); ", "
NEXT i
PRINT "..."
FUNCTION fibonacci (n)
IF (n <= 2) THEN
fibonacci = 1
ELSE
fibonacci = fibonacci(n - 1) + fibonacci(n - 2)
END IF
END FUNCTION
Example for versions QBasic 1.1, QuickBASIC 4.5
Fibonacci numbers are calculated using Binet’s formula. The resulting numbers can differ from actual ones slightly due to calculation imprecision; to remove this effect, we use function INT which truncates fractional part of the number.
DECLARE FUNCTION FIBONACCI (n)
DIM S AS STRING
S = ""
FOR i = 1 TO 16:
S = S + STR$(INT(FIBONACCI(i) + .1)) + ","
NEXT i
S = S + "..."
PRINT S
FUNCTION FIBONACCI (n)
p1 = ((1 + SQR(5)) * .5) ^ n
p2 = ((1 - SQR(5)) * .5) ^ n
FIBONACCI = (p1 - p2) / SQR(5)
END FUNCTION
Example for versions Lua 5.0.3
This example uses recursive definition of Fibonacci numbers.
function fibonacci(n)
if n<3 then
return 1
else
return fibonacci(n-1) + fibonacci(n-2)
end
end
for n = 1, 16 do
io.write(fibonacci(n), ", ")
end
io.write("...\n")
Example for versions Lua 5.0.3
Numbers which have already been calculated are stored in associative array fib and are retrieved from it to calculate the next ones. By default Lua associative arrays use 1-based integer keys, so fib = {1, 1} creates an array with indices 1 and 2.
fib = {1, 1}
for n = 3, 16 do
fib[n] = fib[n-1] + fib[n-2]
end
for n = 1, 16 do
io.write(fib[n], ", ")
end
io.write("...\n")
Example for versions Visual Prolog 7.2
Create a new project with UI Strategy “Console” and replace contents of files main.cl and main.pro with given code.
Here we define two new predicates — fibonacci(N,F) to calculate Nth Fibonacci number and loop(N) to output it. We don’t use memoization to store already calculated numbers, so this implementation is rather inefficient. Note the way the predicates are defined — each predicate is written as one clause using conjunction , and disjunction ; of elementary predicates (instead of breaking them in several clauses which use only disjunction).
% main.cl
class main
open core
predicates
classInfo : core::classInfo.
fibonacci : (integer N, integer F) procedure (i,o).
loop : (integer N) procedure (i).
predicates
run : core::runnable.
end class main
% main.pro
implement main
open core
constants
className = "main".
classVersion = "".
clauses
classInfo(className, classVersion).
fibonacci(N,F) :-
N < 3, !, F = 1;
fibonacci(N-1,F1), fibonacci(N-2,F2), F = F1 + F2.
loop(N) :-
( N = 1, !, fibonacci(1,F);
loop(N-1), fibonacci(N,F) ),
stdio::write(F, ", ").
clauses
run():-
console::init(),
loop(16),
stdio::write("..."),
programControl::sleep(1000),
succeed().
end implement main
goal
mainExe::run(main::run).
Example for versions Oracle 10g SQL
This example shows the use of model clause, available since Oracle 10g. It allows array-like processing of query rows. Each row has two columns — Fibonacci number itself (stored in f) and concatenation of all Fibonacci numbers less than or equal to the current Fibonacci number (stored in s). Iterative aggregation of Fibonacci numbers in the same query that they were generated is easier than aggregating them separately.
select max(s) || ', ...'
from
(select s
from dual
model
return all rows
dimension by ( 0 d )
measures ( cast(' ' as varchar2(200)) s, 0 f)
rules iterate (16)
( f[iteration_number] = decode(iteration_number, 0, 1, 1, 1, f[iteration_number-1] + f[iteration_number-2]),
s[iteration_number] = decode(iteration_number, 0, to_char(f[iteration_number]), s[iteration_number-1] || ', ' || to_char(f[iteration_number]))
)
);
Example for versions MySQL 3.23.57
Replace TABLE with name of any table you have access to, like mysql.help_topic.
select concat(group_concat(f separator ', '), ', ...')
from (select @f := @i + @j as f, @i := @j, @j := @f
from TABLE, (select @i := 1, @j := 0) sel1
limit 16) t
Example for versions Poplog 15.5 (Prolog)
Straightforward recursive implementation is too memory inefficient to be executed in Poplog, so this example shows a more advanced technique — recursion with memoization. An additional predicate memo(Goal) is defined so that the first time Goal is evaluated, the result of its evaluation is added to facts database, and next time it is questioned, it is not re-evaluated but taken as a known fact.
After this predicate fib(N,F) is defined recursively, but each call to fib is wrapped in memo, so for each value of N fib(N,F) is evaluated only once. With such approach printing calculated numbers can be done immediately after their calculation, without extra loop.
% fibonacci.pl
:- dynamic(stored/1).
memo(Goal) :-
stored(Goal) -> true;
Goal, assertz(stored(Goal)).
fib(1,1) :- !, write('1, ').
fib(2,1) :- !, write('1, ').
fib(N,F) :-
N1 is N-1, memo(fib(N1,F1)),
N2 is N-2, memo(fib(N2,F2)),
F is F1 + F2,
write(F), write(', ').
% interactive
[-fibonacci].
fib(16,X), write('...'), nl.
Example for versions Free Pascal 2.0.4, gpc 20070904, Turbo Pascal 1.0, Turbo Pascal 2.0, Turbo Pascal 3.0, Turbo Pascal 4.0, Turbo Pascal 5.0, Turbo Pascal 5.5, Turbo Pascal 6.0, Turbo Pascal 7.0
This example uses recursive definition of Fibonacci numbers.
program fibonacci;
function fib(n:integer): integer;
begin
if (n <= 2) then
fib := 1
else
fib := fib(n-1) + fib(n-2);
end;
var
i:integer;
begin
for i := 1 to 16 do
write(fib(i), ', ');
writeln('...');
end.
Example for versions ARIBAS 1.53
This example uses recursive definition of Fibonacci numbers.
ARIBAS uses integer type for variables by default, so type declaration can be omitted.
group(0) is used to cancel digit groups separation by underscores during output.
function fib(n);
begin
if (n < 3) then
return(1);
end;
return(fib(n-1)+fib(n-2));
end;
function fib1_16();
var n;
begin
for n := 1 to 16 do
write(fib(n): group(0), ", ");
end;
writeln("...");
end;
fib1_16().
Example for versions Python 2.5.2
This example uses recursive definition of Fibonacci numbers.
#! /usr/bin/env python
def fibonacci(n):
if n < 3:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
for n in range(1, 16 + 1):
print "%i," % fibonacci(n) ,
print "..."
Example for versions Microsoft Visual Basic .NET 9 (2008)
This example uses recursive definition of Fibonacci numbers.
Module Module1
Function Fibonacci(ByVal n As Integer) As Long
If n < 3 Then
Return 1
Else
Return Fibonacci(n - 1) + Fibonacci(n - 2)
End If
End Function
Sub Main()
For i As Integer = 1 To 16
Console.Write(Fibonacci(i) & ", ")
Next
Console.WriteLine("...")
End Sub
End Module
Example for versions Microsoft Visual C# 2008
This example uses recursive definition of Fibonacci numbers.
using System;
class Program
{
static long Fibonacci(int n)
{
if (n < 3)
return 1;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
static void Main(string[] args)
{
for (int i = 1; i < 17; i++)
Console.Write("{0}, ", Fibonacci(i));
Console.WriteLine("...");
}
}
Example for versions PHP 5.2.4
This example uses recursive definition of Fibonacci numbers.
<?php
function fibonacci($n)
{
if ($n < 3) {
return 1;
}
return fibonacci($n-1) + fibonacci($n-2);
}
for ($n = 1; $n <= 16; $n++) {
echo fibonacci($n) . ", ";
}
echo "...\n";
?>
Example for versions Poplog 15.5 (POP-11)
This example uses recursive definition of Fibonacci numbers and works in the same way as factorial example, except for that loop returns a string which contains a concatenation of all Fibonacci numbers up to n-th.
define fibonacci(n);
if n < 3
then 1
else fibonacci(n - 1) + fibonacci(n - 2)
endif
enddefine;
define loop(n);
if n>1
then loop(n-1) >< ', ' >< fibonacci(n)
else fibonacci(n)
endif;
enddefine;
loop(16) >< ', ...' =>
Example for versions Perl 6 (alpha)
Not the shortest possible implementation, but perhaps the easiest to read and understand.
sub fib { 1,1...{$^x + $^y} }
fib[^16], '...' ==> join(', ') ==> say;
Example for versions Euphoria v3.1.1, Euphoria v4
This example uses recursive definition of Fibonacci numbers.
function fibonacci(integer n)
atom result = 1
if n <= 2 then
result = 1
else
result = fibonacci(n-1) + fibonacci(n-2)
end if
return result
end function
for i = 1 to 16 do
printf(1, "%d, ", fibonacci(i))
end for
puts(1, "...\n")
Example for versions Euphoria v3.1.1, Euphoria v4
This example uses iterative definition of Fibonacci numbers.
function fibonacci(integer n)
sequence result
result = repeat(1, n)
for i = 3 to n do
result[i] = result[i-1] + result[i-2]
end for
return result
end function
sequence ans = fibonacci(16)
for i = 1 to length(ans) do
printf(1, "%d, ", ans[i])
end for
puts(1, "...\n")
Example for versions Oracle 10g SQL
This example implements iterative definition of Fibonacci numbers by means of PL/SQL. Already calculated numbers are stored in varray, PL/SQL analogue of array in other languages.
declare
type vector is varray(16) of number;
fib vector := vector();
i number;
s varchar2(100);
begin
fib.extend(16);
fib(1) := 1;
fib(2) := 1;
s := fib(1) || ', ' || fib(2) || ', ';
for i in 3..16 loop
fib(i) := fib(i-1) + fib(i-2);
s := s || fib(i) || ', ';
end loop;
dbms_output.put_line(s || '...');
end;
Example for versions Squeak 3.10
This code is a method of an object, and adds n Fibonacci numbers to an OrderedCollection called numbers.
Variable declarations are enclosed in vertical bars and don’t specify their type. Code blocks are enclosed in square brackets. The “^” carrot at the end returns the result from this method.
fibonacci: n
| numbers a b |
numbers := OrderedCollection new.
a := 1.
b := 1.
[ numbers size < n ] whileTrue: [
| temp |
numbers add: a.
temp := b.
b := a + b.
a := temp.
].
^ numbers.
Example for versions Squeak 3.10
This is a recursive method implementing the Fibonacci sequence, writing it to the given stream of numbers.
To invoke this method:
stream := WriteStream on: (Array new: 100). Fibonacci new fibonacci: 1 and: 1 writeTo: stream
There is no halting condition; the program will continue writing Fibonacci numbers until interrupted.
This example is far from optimal: the stream will automatically double the size of the array each time it is filled (a very expensive operation in Squeak), and the recursion continually consumes memory. The alternative iterative example is much more efficient.
fibonacci: n1 and: n2 writeTo: stream
stream nextPut: n1.
self fibonacci: n2 and: (n1+n2) writeTo: stream.
Example for versions REXX
This example uses recursive definition of Fibonacci numbers.
1 #!/usr/bin/rexx
2 /* Calculate Fibonacci using recursion */
3
4 numbers = ''
5
6 do n = 1 to 16
7 numbers = numbers fibonacci(n)","
8 end
9
10 say numbers"..."
11 exit
12
13 fibonacci: procedure
14 parse arg n .
15
16 if n < 3 then
17 n = 1
18
19 else
20 n = fibonacci(n-1) + fibonacci(n-2)
21 return n
Example for versions REXX
This example uses iterative definition of Fibonacci numbers.
In REXX, an uninitialized variable has its name in uppercase as its value; e.g. numbers = ‘NUMBERS’
Line 4: Arrays are called “stem variables”. The root of a stem ends with a period. Elements of a stem are named by adding a value to the stem; e.g. fib.1, fib.first, etc. Additional dimensions may be used by adding another period and value; e.g., fib.1.3; To initialize all possible stem instances, assign a value to the stem name; e.g., fib. = 0 or fib. = ”
1 #!/usr/bin/rexx
2 /* Calculate Fibonacci using an associative array */
3
4 fib. = ''
5 fib.1 = 1
6 fib.2 = 1
7 numbers = ''
8
9 do f = 3 to 16
10 e = f - 1; d = f - 2
11 fib.f = fib.e + fib.d
12 end
13
14 do n = 1 to 16
15 numbers = numbers fib.n','
16 fib.f = fib.e + fib.d
17 end
18
19 say numbers"..."
20 exit
Example for versions D1, D2, gdc 0.24
This example uses iterative definition of Fibonacci numbers.
module fibonacci;
import std.stdio;
ulong iterative(ulong x)
{
ulong prev1 = 1L;
ulong prev2 = 1L;
ulong result = x <= 2 ? 1L : 0L;
for ( ulong i = 3; i <= x; ++i )
{
result = prev1 + prev2;
prev1 = prev2;
prev2 = result;
}
return result;
}
int main()
{
for (uint i = 1; i < 17; i++)
{
writef("%s, ", iterative(i));
}
writefln("%s", "...");
return 0;
}
Example for versions D1, D2, gdc 0.24
This example uses recursive definition of Fibonacci numbers.
module fibonacci;
import std.stdio;
ulong recursive(ulong x)
{
return x <= 2 ? 1 : recursive( x - 2 ) + recursive( x - 1 );
}
int main()
{
for (uint i = 1; i < 17; i++)
{
writef("%s, ", recursive(i));
}
writefln("%s", "...");
return 0;
}
Example for versions j602
This example uses recursive definition of Fibonacci numbers.
load 'printf'
fibr=: 1:`(-&2 +&$: -&1)@.(1&<)"0
fstr=: '...' ,~ ,~^:4 '%d, '
fstr printf fibr i.16
Example for versions j602
This example uses iterative definition of Fibonacci numbers.
load 'printf'
fibi=: 3 : '(,+/@(_2&{.))^:y(0 1)'
fstr=: '...' ,~ ,~^:4 '%d, '
fstr printf }.fibi 15
Example for versions j602
This example uses Binet’s formula. g is the golden ratio.
load 'printf'
g=: -: >: %:5
fibb=: (%:5) %~ g&^ - (1-g)&^
fstr=: '...' ,~ ,~^:4 '%d, '
fstr printf fibb"0 >:i.16
Example for versions gfortran 4.5.0, Intel Visual Fortran 11.1
This example uses iterative definition of Fibonacci numbers. The tricky part is printing the calculated values in one line, without leading or trailing spaces. Format specifier (I3, A, $) means that first an integer is printed using exactly 3 positions, followed by a string. The final $ suppresses trailing carriage return, used by default, so that everything is printed in one line.
program Fibonacci
integer :: f1,f2,f3,i
i = 1
f1 = 0
f2 = 1
do
f3 = f2 + f1
f1 = f2
f2 = f3
i = i + 1
if (f1<10) then
print '(I1, A, $)', f1, ', '
elseif (f1<100) then
print '(I2, A, $)', f1, ', '
else
print '(I3, A, $)', f1, ', '
end if
if (i==17) then
exit
end if
end do
print *, '...'
end program Fibonacci
Example for versions SpiderMonkey (Firefox 3.5)
This example uses recursive definition of Fibonacci numbers and is meant to be executed from web-browser.
function fibonacci(n)
{ if (n<3)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}
var i;
document.clear();
for (i = 1; i <= 16; i++)
document.write(fibonacci(i) + ", ");
document.write("...<br />");
Example for versions GHC 6.10.4
This example uses one of the main Haskell features — lazy evaluations and infinite lists. Infinite list of Fibonacci numbers fibs is defined using zipWith function which applies its first argument (a function of two variables, in this case +) to pairs of corresponding elements of second and third arguments (lists). tail fibs returns tail of the list fibs (i.e., all elements except for the first one). Thus first element of the list returned by zipWith is a sum of first and second elements of list fibs and becomes its third element.
module Main where
import Text.Printf
fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
line n = printf "%d, " $ fibs !! n
main = do
sequence_ $ map line [1..16]
putStrLn "..."
Example for versions GHC 6.10.4
This example uses recursive definition of Fibonacci numbers via pairs of adjacent numbers in the sequence. Only first elements of the pairs are printed.
module Main where
import Text.Printf
fibNextPair :: (Int, Int) -> (Int, Int)
fibNextPair (x, y) = (y, x+y)
fibPair :: Int -> (Int, Int)
fibPair n
| n == 1 = (1, 1)
| otherwise = fibNextPair (fibPair (n-1))
line n = printf "%d, " $ (fst.fibPair) n
main = do
sequence_ $ map line [1..16]
putStrLn "..."
Example for versions gcc 3.4.5, gcc 3.4.5 (Objective-C)
This example uses recursive definition of Fibonacci numbers. Note the difference from C++ example: loop counter must be declared outside of the loop, and printf is used for output instead of std::out.
#include <stdio.h>
int fibonacci(int n)
{
return ( n<=2 ? 1 : fibonacci(n-1) + fibonacci(n-2) );
}
int main(void)
{
int n;
for (n=1; n<=16; n++)
printf("%d, ", fibonacci(n));
printf("...\n");
return 0;
}
Example for versions Furry Paws
This example works exactly like the one for Interactive FP.
one = eq.[id, ~1]
dec = sub.[id, ~1]
seq = one -> [~1] ; cat.[seq.dec, [id]]
fibonacci = lt.[id, ~3] -> ~1 ; add.[fibonacci.sub.[id, ~1], fibonacci.sub.[id, ~2]]
main = show.(return @fibonacci.(seq.~16))
Example for versions gnat 3.4.5
This example uses recursive definition of Fibonacci numbers.
with Ada.Text_IO, Ada.Integer_Text_IO;
procedure Fibonacci is
begin
declare
function Fib (N: Integer) return Integer is
begin
if N<3 then
return 1;
else
return Fib(N-1) + Fib(N-2);
end if;
end Fib;
i: Integer := 1;
begin
loop
Ada.Integer_Text_IO.Put (Item => Fib(i), Width => 1);
Ada.Text_IO.Put (", ");
i := i + 1;
exit when i=17;
end loop;
Ada.Text_IO.Put ("...");
end;
end Fibonacci;
Example for versions Scratch 1.4
This example uses recursive definition of Fibonacci numbers, since Scratch doesn’t have an easy way to define a function. Besides, Scratch is a graphical language, the print-screen contains the actual information about the program, source text is only a transcription.
set f1 to 1
set f2 to 1
set str to f1
repeat 15
set f3 to (f1 + f2)
set f1 to f2
set f2 to f3
set str to join (str (join (,) f1))
say join (str (...))
Example for versions UCBLogo 6.0
This example uses recursive definition of Fibonacci numbers. It defines two functions — fibonacci which calculates the value of Nth Fibonacci number and print_fibonacci which accumulates the numbers in a string and prints them.
to fibonacci :N
ifelse :N < 3 [output 1] [output sum fibonacci :N - 1 fibonacci :N - 2]
end
to print_fibonacci :i :N
make "str fibonacci :i
make "i sum :i 1
make "comma ",
repeat :N - :i + 1 [make "str (word :str :comma fibonacci :i)
make "i sum :i 1]
make "str word str ",...
print str
end
print_fibonacci 1 16
Example for versions Go gc
This example implements all three methods of calculating Fibonacci numbers — recursive, iterative and Binet’s formula. Besides, a generic function for printing results of using any of the functions is defined.
package main
import ("fmt"
"math")
//Fibonacci Recursive
func fibr(n int) int {
if n < 2 { return 1 }
return fibr(n-2) + fibr(n-1)
}
//Fibonacci Iterative
func fibi(n int) int {
var a, b int = 1, 1
for i := 0; i < n; i++ {
a, b = b, a+b
}
return a
}
//Fibonacci Binet
func fibb(n int) int {
g := (1 + math.Sqrt(5)) / 2
ret := (math.Pow(g, float64(n)) - math.Pow(1-g, float64(n))) / math.Sqrt(5)
return int(ret)
}
type fibfunc func(int) int
//Implements a general printing method for fibonacci functions
func printFib(fib fibfunc, a, b int) {
for i := a; i < b; i++ {
fmt.Printf("%d, ", fib(i))
}
fmt.Println("...")
}
func main() {
printFib(fibr, 0, 16)
printFib(fibi, 0, 16)
printFib(fibb, 1, 17)
}
Example for versions Scala 2.7.7-final
This example uses recursive definition of Fibonacci numbers.
object Fibonacci {
def fibonacci(n: Int): Int =
if (n < 3) 1
else fibonacci(n - 1) + fibonacci(n - 2)
def main(args: Array[String]) {
for {i <- List.range(1, 17)}
yield { print(fibonacci(i) + ", ") }
println("...")
}
}
Example for versions Scala 2.7.7-final
This example shows the usage of lazy evaluations and infinite lists in Scala. Infinite list of Fibonacci numbers is defined using functions .zip and .tail in the same way as in Haskell example.
lazy val fib: Stream[Int] = Stream.cons(1, Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))
fib.take(16).print
Example for versions gawk 3.1.6, mawk 1.3.3
This example uses iterative definition of Fibonacci numbers. fib is an associative array, and pr is a string.
BEGIN {
fib[1] = 1
fib[2] = 1
for (i=3; i<17; i++)
fib[i] = fib[i-1]+fib[i-2]
pr = ""
for (i=1; i<17; i++)
pr = pr fib[i] ", "
print pr "..."
}
Example for versions OCaml 3.11
naive recursive solution
let rec fibonacci n =
if n < 3 then
1
else
fibonacci (n-1) + fibonacci (n-2)
let () =
for n = 1 to 16 do
Printf.printf "%d\n" (fibonacci n)
done;
print_endline "..."
Example for versions perl 5.8.8
naive recursive solution
sub fibonacci {
my $n = shift;
$n < 3 ? 1 : fibonacci($n-1) + fibonacci($n-2)
}
foreach (1..16) {
print fibonacci($_), "\n";
}
Example for versions Ruby 1.8.5
This example uses recursive definition of Fibonacci numbers.
#! /usr/bin/env ruby
def fibonacci(n)
if n < 3
1
else
fibonacci(n - 1) + fibonacci(n - 2)
end
end
(1..16).each {|n| puts fibonacci(n)}
puts "..."
Example for versions S-lang 2.2.2
This example uses iterative definition of Fibonacci numbers and shows some more features of array processing in S-lang. f is explicitly declared as an array of 16 integer numbers. Elements 0 and 1 of f are set to 1; here [0:1] creates a list of indices to which the operation is applied. Intrinsic function string converts its argument to its string representation.
f = Integer_Type [16];
f[[0:1]] = 1;
for (i=2; i<16; i++)
f[i] = f[i-1] + f[i-2];
s = "...";
for (i=15; i>=0; i--)
s = string(f[i]) + ", " + s;
message (s);
Example for versions LÖVE 0.6.1
This example uses iterative definition of Fibonacci numbers.
function love.draw()
fib = {1, 1}
for n = 3, 16 do
fib[n] = fib[n-1] + fib[n-2]
end
str = ""
for n = 1, 16 do
str = str..fib[n]..", "
end
love.graphics.print(str.."...", 10, 20)
end
Example for versions Hanoi Love
This example uses iterative definition of Fibonacci numbers. Stack A is empty (used for popping 1 from it) and is used for temporary storages. Stack B holds printable characters (comma and space) and two last Fibonacci numbers. Stack C holds a 1 for each Fibonacci number to be printed (6 1’s to print 6 numbers). On each iteration one number is popped from C. If it is positive, top number f2 from stack B is popped, converted to ASCII character of the corresponding digit and printed. After this number f1 is popped from stack B and added to f2. Finally, numbers f2 and f1+f2 are pushed back in stack B. A low-level description of the example is given in the comments.
Hanoi Love interpreter uses byte variables to store values of memory cells, so a maximum of 13 Fibonacci numbers can be printed. However, printing multi-digit numbers in Hanoi Love is rather similar to Brainfuck, so only first six single-digit numbers are printed.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; .' B (space) regr = ASCII for space
...;;;;;;;;;;;;.' B (space comma) reg = ASCII for comma
..., A (empty) reg = 1
..'''''' C (6 ones for 6 numbers to print) reg = 1
..`.'...;.' B (space comma 0 1) reg = 1
., C (pop number to reg) reg = 1
.'... D (remembered this place)
: if this number is positive print top number in B and move to next Fibonacci number
..., B (space comma f1) reg = f2
.' C (f2) reg = f2
..;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; "' A (empty) reg = f2 in ASCII (printed)
., B (space comma) reg = f1
.' C (f2 f1) reg = f2
..., "' B (space) reg = comma (printed)
.' C (f2 f1 comma) reg = comma
..., "' ' B (space) reg = space (printed)
.,...' B (space comma) reg = comma
., C (f2) reg = f1
..' A (f1) reg = f1
.., C (empty) reg = f2
...' B (space comma f2) reg = f2
...; A (empty) reg = f1+f2
.' B (space comma f2 f1+f2)
., C (pop number to reg)
., D (get previous command location)
!
...,,,...;; "' "' "' pop everything from B and convert comma to point (printed three times)