Fibonacci Number Program

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