Fibonacci Number Program

Implementation of the algorithm in all programming languages.

by Scriptol.com

Mathematician  Leonardo Fibonacci posed the following problem in his treatise Liber Abaci:
"How many pairs of rabbits will be produced in a year, beginning with a single pair, if in every month each pair bears a new pair which becomes productive from the second month on?"
The answer is given below by algorithms in the most popular and new programming languages...

Ada  Algol   Asp   Awk   Basic  Boo  C   C++   C#   Caml   Cobol  CoffeeScript  Dart  Eiffel  Erlang   F#   Forth   Fortran  Go  Haskell   Java   JavaScript   Julia   Lisp   Lua   Oberon   Objective C   OCaml   Oz   Pascal   Perl  PHP   Prolog   Python  Rebol   Rexx  Ruby  Rust  Scala   Scheme  Scriptol   Smalltalk   Swift   Tcl   TypeScript   WebAssembly

Ada

Recursive 
function fib(n : integer) return integer is
begin
  if n < 2 then
    return n;
  else
    return fib(n-1) + fib(n-2);
  end if;
end fib;
Iterative 
function fib(n : integer) return integer is
  first  : integer := 0;
  second : integer := 1;
  tmp    : integer;
  begin
    for i in 1..n loop
      tmp    := first + second;
      first  := second;
      second := tmp;
    end loop;
  return first;
end fib;

Algol 68

PROC print fib = (INT n) VOID :
    BEGIN
        INT a := 0;
        INT b := 1;
        FOR i TO n DO
            print((whole(i, 0), " => ", whole(b, 0), new line));
            INT c = a + b;
            a := b;
            b := c
        OD
    END;

print fib(10)

Asp

Recursive 
function fibo(byval i) 
    if (i = 0 or i = 1) then 
        fibo = i 
    else 
        fibo = fibo(i - 1) + fibo(i - 2) 
    end If 
end function 


<% for num = 1 to n 
= fibo(num)
%>
Iterative 

<table>
<%
  dim a = 1
  dim b = 1
  dim num
  dim d
  for num = 1 to 12
    d = a + b
    a = b - 1
    b = d
    response.Write("<tr><td> " & num & "</td><td>" & a & "</td></tr>") 
  next
%> 
</table>

Awk 


function fib(n)
{
 if(n < 2) return(n);
 return(fib(n-2) + fib(n-1));
}
BEGIN
{
 printf("%d\n", fib(10));
 exit;
}

Basic 

x = 1
y = 1
n = 100
FOR x = 1 to n
  z = x + y      
  x = y
  y = z
  PRINT z + 1
NEXT x

C

Recursive 
int fib(int n){
  if (n < 2)
    return n;
  else
    return fib(n-1) + fib(n-2);
}

printf("%d\n", fib(10));
Iterative 
int fib(int n) {
  int first = 0, second = 1;

  int tmp;
  while (n--) {
    tmp = first+second;
    first = second;
    second = tmp;
  }
  return first;
}

C++

Recursive 
int fib(int n) {
  if (n < 2)
    return n;
  else
    return fib(n-1) + fib(n-2);
}
cout << fib(10) << endl;
Iterative 
int fibonacci(int n){
  int u = 0;
  int v = 1;
  int i, t;
  for(i = 2; i <= n; i++) {
    t = u + v;
    u = v;
    v = t;
  }
  return v;
}

C#

Recursive 
using System;

class App 
{

  public static int fibo(int n) 
  {
    return (n < 2) ? n : fibo(n-2) + fibo(n-1);
  }
  public static int Main(String[] args) 
  {
    int limit;
    int f;
    limit = System.Convert.ToInt32(args[0]);
    if(limit < 1) limit = 1;
    f = fibo(limit);
    Console.WriteLine(f.ToString()+"\n");
    return(0);
 }
}
Iterative 
public class Fibonacci
{
  public static void Main()
  {
    int oldnum = 1;
    int currnum = 1;

    int nextNumber;

    System.Console.Write(currnum + " ");

    while (currnum < 50)
    {
      System.Console.Write(currnum + " ");

      nextNumber = currnum + oldnum;

      oldnum = currnum;
      currnum = nextNumber;
    }
   }
}

Cobol


IDENTIFICATION DIVISION.
  PROGRAM-ID. FIBONACCI.

ENVIRONMENT DIVISION.
DATA DIVISION.

  WORKING-STORAGE SECTION.
  77 N  PIC 9(18).
  77 N1 PIC Z(18).
  77 M  PIC 9(18) VALUE 1.
  77 O  PIC 9(18).
  77 I  PIC 9(4) VALUE 1.
  77 Q  PIC X.

PROCEDURE DIVISION.
  PARA-A.
    DISPLAY ( 1 , 1 ) ERASE.
    DISPLAY ( 2 , 1 ) "FIBONACCI NUMBERS FROM 1 TO 100 ARE:".
    MOVE 0 TO N.
    DISPLAY " ".
    DISPLAY 0.
    DISPLAY 1.
    MOVE 0 TO O.

  PARA-B.
    COMPUTE N = O + M.
    MOVE N TO N1.
    MOVE M TO O.
    MOVE N TO M.
    DISPLAY N1.
    ADD 1 TO I.
    IF I = 21
      DISPLAY "PRESS TAB KEY TO VIEW NEXT PAGE."
      ACCEPT Q.
    IF I = 41
      DISPLAY "PRESS TAB KEY TO VIEW NEXT PAGE."
      ACCEPT Q.
    IF I = 61
      DISPLAY "PRESS TAB KEY TO VIEW NEXT PAGE."
      ACCEPT Q.
    IF I = 81
      DISPLAY "PRESS TAB KEY TO VIEW NEXT PAGE."
      ACCEPT Q
    IF I = 99
      GO TO STOP-PARA
    ELSE
      GO TO PARA-B.
  STOP-PARA.
  DISPLAY " ".
  STOP RUN.

CoffeeScript

fibo = (n) -> 
   if n is 0 or n is 1 return n
   fibo(n-1)+ fibo(n-2)

for i in [1..16]
    console.log fibo(i)

Dart

int fibo(int i) {
  if (i < 2) return i;
  return fibo(i - 2) + fibo(i - 1);
}

Eiffel

Recursive 
class FIBONACCI 
feature 
fib (k: INTEGER): INTEGER is
-- Fibonnaci numbers 
  require 
  pre_fib: k >= 0 do 
  if k = 0 then
    Result := 0 
  else
    if k = 1 then
      Result := 1 
    else 
      Result := fib (k-2) + fib (k-1) end 
end; 
-- fib
Iterative 

fibiter (k: INTEGER): INTEGER is
-- Fibonacci 
require
  pre_fib: k > 0 
local 
  j, p, c, n: INTEGER 
do from 
   p := 0; 
   c := 1; 
   j := 1 
  until 
    j = k 
  loop 
     n := p + c; 
     p := c; 
     c := n; 
     j := j + 1 
  end; 
  Result := c 
end; 
-- fib1

Erlang

-module(fibo).
-export([main/1]).

main() -> main(['1']).
main([Arg]) ->
    Num = list_to_integer(atom_to_list(Arg)),
    io:fwrite("~w\n", [fibo(Num)]),
    halt(0).

fibo(N) when N < 2 -> 1;
fibo(N) -> fibo(N-2) + fibo(N-1).

F# (F Sharp)

let rec fibo x =
    match x with
        0 -> 1
      | 1 -> 1
      | n -> fibo(x - 1) + fibo(x - 2);;

fibo 10;;

Forth

\ read NUM from last command line argument
0. argc @ 1- arg >number 2drop drop constant NUM

\ compute fibonacci numbers
: fib  Récursif
    dup 2 <
    if
    drop 1
    else
    dup
        2 - fib
    swap
    1 - fib
    +
    then ;

NUM fib 1 u.r cr

bye

A very short version: 


\ Nombres de Fibonacci par Bill Spight
: FIBO   ( n -- n1 n0) \ n >= 0, n0 = Fibo(n), n1 = Fibo(n-1)
  DUP 0= IF 1 SWAP ELSE 1- RECURSE TUCK + ENDIF ;

Fortran

  PROGRAM F2A
      I=35; K=I
      CALL F(I)
      PRINT *,K,'th Fibonacci number is',I
      STOP
      END PROGRAM
C
C Subroutine F(I) calculates the I'th Fibonacci number

C
      SUBROUTINE F(I)
      DIMENSION A(I+1)
      A(1)=1; A(2)=1
      DO1J=3,I+1
      A(J)=A(J-1)+A(J-2)
1     CONTINUE
      I=A(I+1)
      RETURN
      END SUBROUTINE

Go

package main
import(
 "fmt"
 "math"
)

func fibo(n int) int {
  if n < 2 {
   return n
  }
  return fibo(n-2) + fibo(n-1)
}

Haskell

module Main where
import System.Environment

fibo = 1 : 1 : zipWith (+) fibo (tail fibo)

main = do
    args <- getArgs
    print (fibo !! (read(args!!0)-1))

Java

public class fibo 
{
    public static void main(String args[]) 
    {
      int N = Integer.parseInt(args[0]);
      System.out.println(fib(N));
    }
    public static int fib(int n) 
    {
      if (n < 2) return(n);
      return( fib(n-2) + fib(n-1) );
    }
}

Source code

JavaScript

function fibo(n) 
{
    if (n < 2) return n
    return fibo(n-2) + fibo(n-1)
}

for(var i = 1; i < x ; i++)
{
   document.write(i + " = " + fibo(i) + "<br>")
}

Julia

Recursive

fibo(n) = n < 2 ? n : fibo(n-1) + fibo(n-2)

Iterative

function fibo(n)
  x,y = (0,1)
  for i = 1:n
    x,y = (y, x+y)
  end
  return x
end


for n=1:10 
  println(fibo(n))
end

Lisp 

 (defun fibo (x)
 "
   Calcule le nombre de  fibonacci pour x
 "
     (if (<= x 2)
           1 
     (+ (fibo (- x 2))(fibo (1- x)))))

     (loop for i from 1 to x do 
          (print (fibo i)))

Lua 

function fibo(n)
   if (n < 2) then return(1) end
   return( fibo(n-2) + fibo(n-1) ) 
end  
N = tonumber((arg and arg[1])) or 1 
write(fibo(N), "\n")

Oberon 

MODULE fibonacci; 
(* n premiers nombres de Fibonacci *) 
CONST n=151; 
VAR Fibs: 
  ARRAY n+1 OF INTEGER; 
  i,j : INTEGER; 
BEGIN 
  j:=0; 
  Fibs[0]:=0; 
  Fibs[1]:=1; 
  i:=2; 
  WHILE i <= n DO 
    Fibs[i]:= Fibs[i-2] + Fibs[i-1]; 
    i:=i+1; 
  END; 
  i:=0; 
  WHILE i <= n DO 
    Write(Fibs[i]); 
    i:=i+1; 
  END; 
END fibonacci.

Objective C

int i, a = 1, b = 0;
int top = 50;

for(i = 2; i < top; i++) {
  fibo = a + b;
  a = b;
  b = fibo;
  printf("fibo(%d) %d\n", i, fibo);
}

Ocaml 

let rec fib n =
  if n < 2 then 1
  else fib (n - 2) + fib (n - 1)

let _ =
  let n =
    try int_of_string Sys.argv.(1)
    with Invalid_argument _ -> 1 in
  Printf.printf "%d\n" (fib n)

Oz

functor
import System Application
define
fun {Fib N}
    case N
    of 0 then 1
    [] 1 then 1
    else {Fib N-2} + {Fib N-1} end
end
in 
    local A in
        [A] = {Application.getArgs plain}
        {System.printInfo {Fib {String.toInt A}}}
    end
    {Application.exit 0}
end

Pascal

Recursive 

program fibo;     
var
 result : longint;
 num,i, error: integer;
 strnum: string;

function fib(n : integer) : longint;
begin
    if n <= 2 then fib := 1
    else fib := fib(n-2) + fib(n-1);
end;

begin
if ParamCount = 0 then
begin
  writeln('Enter integer:');
  readln(strnum);
  val(strnum,num,error);
end else 
begin
 val (ParamStr(1), num, error);
end;
for i := 1 to num do
begin
  result:= fib(i);
  writeln(i, ' : ', result);
end;

end.
Source code

Perl

Iterative using bigint 
#! /usr/bin/perl
use bigint;

my ($a, $b) = (0, 1);
for (;;) 
{
    print "$a\n";
    ($a, $b) = ($b, $a+$b);
}
Recursive 
sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}
Iterative 
sub fibo
{
    my ($n, $a, $b) = (shift, 0, 1);
    ($a, $b) = ($b, $a + $b) while $n-- > 0;
    $a;
}

PHP

Recursive 

<?php
function fibo($n)
{
    return(($n < 2) ? 1 : fibo($n - 1) + fibo($n - 2));
}
$n = ($argc == 2) ? $argv[1] : 1;
$r = fibo($n);
print "$r\n";
?>
Iterative 

function fibonacci($length) 
{
   for( $l = array(1,1), $i = 2, $x = 0; $i < $length; $i++ )
   {
        $l[] = $l[$x++] + $l[$x];
   }              
   return $l;
} 

for{ $x=0; $x< $fibmax; $x++) echo "fib(" , $x , ") ", fibonacci($x), "\n"

Prolog

Recursive 

fibo(N, 1) :-, N<2, !. 
fibo(N, R) :-
N1 is N-1, N2 is N-2,
 fibo(N1, R1),fibo(N2, R2),
 R is R1 + R2.

Python

Recursive 

import sys

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

def main():
    limit = int(sys.argv[1])
    print(fib(limit))
main()
With generator 
def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

Rebol 


Fib: func [N] 
[
  return either N < 2  [ n ] [ (Fib N - 2) + (Fib N - 1) ]
]

NUM: to-integer to-string system/script/args
NUM: either NUM < 1 [ 1 ] [ NUM ]
R: Fib NUM
write %output.rebol rejoin [ R ]

Rexx 


parse arg n
If n < 1 Then Do
    n = 1
End

R = fib(N)
say R
exit

fib:
    Procedure
    parse arg n
    if n < 2 return n
    return fib(n-2) + fib(n-1)

Ruby

Recursive 
def fibo(n)
  return n if n <= 1
  return fibo(n-1) + fibo(n-2)
end

puts fibo(16)
Iterative 
def fib(num)
   i, j = 0, 1
   while i <= num
     yield i
     i, j = j, i + j
   end
end

fib(10) {|i| puts i}

Rust

fn fibo(n: int) -> int {
  if (n <= 1) {
    ret n;
  } 
  else {
    ret fibo(n - 1) + fibo(n - 2);
  }
}

print(fmt!("%d ", fibo(10)));

Scala

Recursive 

object Fibonacci with Application 
{

  def fibo(n: Int): Int =
    if (n < 2) n
    else fibo(n - 1) + fibo(n - 2);

  Console.println("fib("+ x +") = " + fib(x));
};
Iterative 

object Fibonacci with Application 
{
  def fibo(n: Int): Int =
    if (n < 2) 1
    else 
    {
      def iter(x: Int, prev: Int, result: Int): Int =
        if (x > n) result
        else iter(x + 1, result, prev + result);
      iter(3, 1, 2)
    };
  Console.println("fib("+ x +") = " + fib(x));
};

Scheme

Recursive 
(define fibo
 (lambda (x)
   (if (< x 2)
     x
     (+ (fibo (- x 1)) (fibo (- x 2))))))
Iterative 
(define (fibo x) 
  (define (fibo-iter x a b)
     (if (= x 0) 
            a 
           (fibo-iter (- x 1) b (+ a b))))
  (fibo-iter x 0 1))
Display 
(define (fibo-run a b) 
  (display a)
  (newline)
  (fibo-run b (+ a b)))

(define fibo-run-all (fibo-run 0 1)))

Scriptol

Recursive 
# Recursive Fibonacci function

constant int fmax = 16

int fib(int n)
   if n <= 1 return n
return fib(n - 1) + fib(n - 2)

for int i in 1..fmax          // loop in a range
    print "fib($i)= " , fib(i)
/for
Iterative 
int fibonacci(int n)
    int u = 0
    int v = 1
    int t

    for int i in 2 .. n
        t = u + v
        u = v
        v = t
    /for
return v

for int x in 1..fibmax echo "fib(" , x , ") ", fibonacci(x), "\n"

Smalltalk 


^self <= 2
    ifTrue: [1]
    ifFalse: [(self - 1) fibonacci + (self - 2) fibonacci]

Swift

func fib(n: Int) -> Int {
  if n <= 1 {
    return n
  }
  return (fib(n - 1) + fib(n - 2))
}

for x in 10 {
  print(fib(x))
}

Tcl 


proc fib {n} {
    if {$n < 2} {
    return $n
    } else {
    return [expr {[fib [expr {$n-2}]] + [fib [expr {$n-1}]]}]
    }
}

set N [lindex $argv 0]
if {$N < 1} { set N 1 }
puts [fib $N]

TypeScript

function fibo(n : number) : number {
    if (n < 2) return n
    return fibo(n-2) + fibo(n-1)
}

WebAssembly

(module
 (export "fib" (func $fib))
 (func $fib (param $n i32) (result i32)
  (if (i32.lt_s (get_local $n)(i32.const 2))
   (return (i32.const 1)
   )
  )
  (return (i32.add
    (call $fib (i32.sub (get_local $n)(i32.const 2)))
    (call $fib (i32.sub (get_local $n)(i32.const 1)))
   )
  )
 )
)

See also