Factorial

The Factorial Function of a positive integer, n, is defined as the product of the sequence n, n-1, n-2, ...1 and the factorial of zero, 0, is defined as being 1.

Write a function to return the factorial of a 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 trapping negative n errors is optional.

ActionScript

Iterative

<lang actionscript> public static function factorial(n:int):int {

   if (n < 0)
       return 0;

   var fact:int = 1;
   for (var i:int = 1; i <= n; i++)
       fact *= i;

   return fact;

} </lang>

Recursive

<lang actionscript> public static function factorial(n:int):int {

  if (n < 0)
      return 0;

  if (n == 0)
      return 1;
  
  return n * factorial(n - 1);

} </lang>

Ada

Iterative

<lang ada> function Factorial (N : Positive) return Positive is

  Result : Positive := N;
  Counter : Natural := N - 1;

begin

  for I in reverse 1..Counter loop
     Result := Result * I;
  end loop;
  return Result;

end Factorial; </lang>

Recursive

<lang ada> function Factorial(N : Positive) return Positive is

  Result : Positive := 1;

begin

  if N > 1 then
     Result := N * Factorial(N - 1);
  end if;
  return Result;

end Factorial; </lang>

Numerical Approximation

<lang ada> with Ada.Numerics.Generic_Complex_Types; with Ada.Numerics.Generic_Complex_Elementary_Functions; with Ada.Numerics.Generic_Elementary_Functions; with Ada.Text_IO.Complex_Io; with Ada.Text_Io; use Ada.Text_Io;

procedure Factorial_Numeric_Approximation is

  type Real is digits 15;
  package Complex_Pck is new Ada.Numerics.Generic_Complex_Types(Real);
  use Complex_Pck;
  package Complex_Io is new Ada.Text_Io.Complex_Io(Complex_Pck);
  use Complex_IO;
  package Cmplx_Elem_Funcs is new Ada.Numerics.Generic_Complex_Elementary_Functions(Complex_Pck);
  use Cmplx_Elem_Funcs;
  
  function Gamma(X : Complex) return Complex is
     package Elem_Funcs is new Ada.Numerics.Generic_Elementary_Functions(Real);
     use Elem_Funcs;
     use Ada.Numerics;
     -- Coefficients used by the GNU Scientific Library
     G : Natural := 7;
     P : constant array (Natural range 0..G + 1) of Real := (
        0.99999999999980993, 676.5203681218851, -1259.1392167224028,
        771.32342877765313, -176.61502916214059, 12.507343278686905,
        -0.13857109526572012, 9.9843695780195716e-6, 1.5056327351493116e-7);
     Z : Complex := X;
     Cx : Complex;
     Ct : Complex;
  begin
     if Re(Z) < 0.5 then
        return Pi / (Sin(Pi * Z) * Gamma(1.0 - Z));
     else
        Z := Z - 1.0;
        Set_Re(Cx, P(0));
        Set_Im(Cx, 0.0);
        for I in 1..P'Last loop
           Cx := Cx + (P(I) / (Z + Real(I)));
        end loop;
        Ct := Z + Real(G) + 0.5;
        return Sqrt(2.0 * Pi) * Ct**(Z + 0.5) * Exp(-Ct) * Cx;
     end if;
  end Gamma;
  
  function Factorial(N : Complex) return Complex is
  begin
     return Gamma(N + 1.0);
  end Factorial;
  Arg : Complex;

begin

  Put("factorial(-0.5)**2.0 = ");
  Set_Re(Arg, -0.5);
  Set_Im(Arg, 0.0);
  Put(Item => Factorial(Arg) **2.0, Fore => 1, Aft => 8, Exp => 0);
  New_Line;
  for I in 0..9 loop
     Set_Re(Arg, Real(I));
     Set_Im(Arg, 0.0);
     Put("factorial(" & Integer'Image(I) & ") = ");
     Put(Item => Factorial(Arg), Fore => 6, Aft => 8, Exp => 0);
     New_Line;
  end loop;

end Factorial_Numeric_Approximation; </lang> Output:

factorial(-0.5)**2.0 = (3.14159265,0.00000000)
factorial( 0) = (     1.00000000,     0.00000000)
factorial( 1) = (     1.00000000,     0.00000000)
factorial( 2) = (     2.00000000,     0.00000000)
factorial( 3) = (     6.00000000,     0.00000000)
factorial( 4) = (    24.00000000,     0.00000000)
factorial( 5) = (   120.00000000,     0.00000000)
factorial( 6) = (   720.00000000,     0.00000000)
factorial( 7) = (  5040.00000000,     0.00000000)
factorial( 8) = ( 40320.00000000,     0.00000000)
factorial( 9) = (362880.00000000,     0.00000000)

ALGOL 68

Iterative

PROC factorial = (INT upb n)LONG LONG INT:(
  LONG LONG INT z := 1;
  FOR n TO upb n DO z *:= n OD;
  z
);

Numerical Approximation

# Coefficients used by the GNU Scientific Library #
INT g = 7;
[]REAL p = []REAL(0.99999999999980993, 676.5203681218851, -1259.1392167224028, 
  771.32342877765313, -176.61502916214059, 12.507343278686905, 
  -0.13857109526572012, 9.9843695780195716e-6, 1.5056327351493116e-7)[@0];

PROC complex gamma = (COMPL in z)COMPL: (
  # Reflection formula #
  COMPL z := in z;
  IF re OF z < 0.5 THEN
    pi / (complex sin(pi*z)*complex gamma(1-z))
  ELSE
    z -:= 1;
    COMPL x := p[0];
    FOR i TO g+1 DO x +:= p[i]/(z+i) OD;
    COMPL t := z + g + 0.5;
    complex sqrt(2*pi) * t**(z+0.5) * complex exp(-t) * x
  FI
);

OP ** = (COMPL z, p)COMPL: ( z=0|0|complex exp(complex ln(z)*p) );
PROC factorial = (COMPL n)COMPL: complex gamma(n+1);

FORMAT compl fmt = $g(-16, 8)"⊥"g(-10, 8)$;
printf(($q"factorial(-0.5)**2="f(compl fmt)l$, factorial(-0.5)**2));
FOR i TO 9 DO
  printf(($q"factorial("d")="f(compl fmt)l$, i, factorial(i)))
OD

Output:

factorial(-0.5)**2=      3.14159265⊥0.00000000
factorial(1)=      1.00000000⊥0.00000000
factorial(2)=      2.00000000⊥0.00000000
factorial(3)=      6.00000000⊥0.00000000
factorial(4)=     24.00000000⊥0.00000000
factorial(5)=    120.00000000⊥0.00000000
factorial(6)=    720.00000000⊥0.00000000
factorial(7)=   5040.00000000⊥0.00000000
factorial(8)=  40320.00000000⊥0.00000000
factorial(9)= 362880.00000000⊥0.00000000

Recursive

PROC factorial = (INT n)LONG LONG INT:
  CASE n+1 IN
    1,1,2,6,24,120,720 # a brief lookup #
  OUT
    n*factorial(n-1)
  ESAC
;

AmigaE

Recursive solution: <lang amigae>PROC fact(x) IS IF x>=2 THEN x*fact(x-1) ELSE 1

PROC main()

 WriteF('5! = \d\n', fact(5))

ENDPROC</lang>

Iterative: <lang amigae>PROC fact(x)

 DEF r, y
 IF x < 2 THEN RETURN 1
 r := 1; y := x;
 FOR x := 2 TO y DO r := r * x

ENDPROC r</lang>

AutoHotkey

Iterative

<lang AutoHotkey> MsgBox % factorial(4)

factorial(n) {

 result := 1 
 Loop, % n
   result *= A_Index
 Return result

} </lang>

AWK

Recursive <lang awk>function fact_r(n) {

 if ( n <= 1 ) return 1;
 return n*fact_r(n-1);

}</lang>

Iterative <lang awk>function fact(n) {

 if ( n < 1 ) return 1;
 r = 1
 for(m = 2; m <= n; m++) {
   r *= m;
 }
 return r

}</lang>

BASIC

Iterative

Works with: FreeBASIC

Works with: RapidQ

<lang freebasic> FUNCTION factorial (n AS Integer) AS Integer

   DIM f AS Integer, i AS Integer
   f = 1
   FOR  i = 2 TO n
       f = f*i
   NEXT i
   factorial = f

END FUNCTION </lang>

Recursive

Works with: FreeBASIC

Works with: RapidQ

<lang freebasic> FUNCTION factorial (n AS Integer) AS Integer

   IF n < 2 THEN
       factorial = 1
   ELSE
       factorial = n * factorial(n-1)
   END IF

END FUNCTION </lang>

bc

#! /usr/bin/bc -q

define f(x) { if (x <= 1) return (1); return (f(x-1) * x); }
f(1000)
quit

Befunge

&1\>  :v v *<
   ^-1:_$>\:|
         @.$<

C

Iterative

<lang c> int factorial(int n) {

 int result = 1;
 for (int i = 1; i <= n; ++i)
   result *= i;
 return result;

} </lang>

Recursive

<lang c> int factorial(int n) {

 if (n == 0)
   return 1;
 else
   return n*factorial(n-1);

} </lang>

C++

The C versions work unchanged with C++, however, here is another possibility using the STL and boost: <lang cpp>

include <boost/iterator/counting_iterator.hpp>
include <algorithm>

int factorial(int n) {

 // last is one-past-end
 return std::accumulate(boost::counting_iterator<int>(1), boost::counting_iterator<int>(n+1), 1, std::multiplies<int>());

} </lang>

C#

Recursive

<lang csharp>using System;

class Program {

   static long fact(int n) {        
       if (n == 0) return 1;
       return n * fact(n - 1);
   }

   static void Main(string[] args) {
       Console.WriteLine(fact(5)); //Example
   }

}</lang>

Clojure

<lang clojure> (defn factorial [x]

 (apply * (range 2 (inc x)))

) </lang>

Common Lisp

Recursive: <lang lisp>(defun fact (n)

   (if (< n 2)
       1
       (* n (fact(- n 1)))
   )

)</lang>

Iterative: <lang lisp>(defun factorial (n)

 "Calculates N!"
 (loop for result = 1 then (* result i)
    for i from 2 to n 
    finally (return result)))</lang>

D

D solution would be similar to C version, but the most known example for factorial is the one using templates calculated during compilation. pragma() compiler directive is used to print calculated value.

<lang D> template itoa(ulong i) {

   static if (i < 10) const char[] itoa = "" ~ cast(char)(i + '0');
   else const char[] itoa = itoa!(i / 10) ~ itoa!(i % 10);

}

template factorial(uint n) {

   static assert(n < 21, "too much for me");
   static if (n == 1) const ulong factorial = 1;
   else const ulong factorial = n * factorial!(n-1);

}

pragma (msg, itoa!(factorial!(20)));

void main() {} </lang>

E

<lang e>pragma.enable("accumulator") def factorial(n) {

 return accum 1 for i in 2..n { _ * i }

}</lang>

Erlang

With a fold: <lang erlang> lists:foldl(fun(X,Y) -> X*Y end, 1, lists:seq(1,N)). </lang>

With a recursive function: <lang erlang> fac(1) -> 1; fac(N) -> N * fac(N-1).</lang>

With a tail-recursive function: <lang erlang> fac(N) -> fac(N-1,N). fac(1,N) -> N; fac(I,N) -> fac(I-1,N*I).</lang>

FALSE

[1\[$][$@*\1-]#%]f:
^'0- f;!.

Recursive:

[$1=~[$1-f;!*]?]f:

Forth

: fac ( n -- n! ) 1 swap 1+ 1 ?do i * loop ;

Fortran

Works with: Fortran version 90 and later

A simple one-liner is sufficient

nfactorial = PRODUCT((/(i, i=1,n)/))

Works with: Fortran version 77 and later

     INTEGER FUNCTION FACT(N)
     INTEGER N, I
     FACT = 1
     DO 10, I = 1, N
       FACT = FACT * I
10   CONTINUE
     RETURN
     END

</lang>

F#

This is a fast tail-recursive implementation. <lang fsharp>let factorial n : bigint =

   let rec f a n =
       match n with
       | 0I -> a
       | n -> (f (a * n) (n - 1I))
   f 1I n</lang>

> factorial 8I;;
val it : bigint = 40320I
> factorial 800I;;
val it : bigint = 771053011335386004144639397775028360595556401816010239163410994033970851827093069367090769795539033092647861224230677444659785152639745401480184653174909762504470638274259120173309701702610875092918816846985842150593623718603861642063078834117234098513725265045402523056575658860621238870412640219629971024686826624713383660963127048195572279707711688352620259869140994901287895747290410722496106151954257267396322405556727354786893725785838732404646243357335918597747405776328924775897564519583591354080898117023132762250714057271344110948164029940588827847780442314473200479525138318208302427727803133219305210952507605948994314345449325259594876385922128494560437296428386002940601874072732488897504223793518377180605441783116649708269946061380230531018291930510748665577803014523251797790388615033756544830374909440162270182952303329091720438210637097105616258387051884030288933650309756289188364568672104084185529365727646234588306683493594765274559497543759651733699820639731702116912963247441294200297800087061725868223880865243583365623482704395893652711840735418799773763054887588219943984673401051362280384187818611005035187862707840912942753454646054674870155072495767509778534059298038364204076299048072934501046255175378323008217670731649519955699084482330798811049166276249251326544312580289357812924825898217462848297648349400838815410152872456707653654424335818651136964880049831580548028614922852377435001511377656015730959254647171290930517340367287657007606177675483830521499707873449016844402390203746633086969747680671468541687265823637922007413849118593487710272883164905548707198762911703545119701275432473548172544699118836274377270607420652133092686282081777383674487881628800801928103015832821021286322120460874941697199487758769730544922012389694504960000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000I

Genyris

Recursive

<lang python>def factorial (n)

   if (< n 2) 1
     * n
       factorial (- n 1)</lang>

Groovy

Recursive

A recursive closure must be pre-declared. <lang groovy>def rFact rFact = { (it > 1) ? it * rFact(it - 1) : 1 } </lang>

Test program: <lang groovy>(0..6).each { println "${it}: ${rFact(it)}" }</lang>

Output:

Iterative

<lang groovy>def iFact = { (it > 1) ? (2..it).inject(1) { i, j -> i*j } : 1 }</lang>

Test program: <lang groovy>(0..6).each { println "${it}: ${iFact(it)}" }</lang>

Output:

Haskell

The simplest description: factorial is the product of the numbers from 1 to n:

factorial n = product [1..n]

Or, written explicitly as a fold:

factorial n = foldl (*) 1 [1..n]

J

Operator

  ! 8             NB.  Built in factorial operator
40320

Iterative / Functional

   */1+i.8
40320

Recursive

  (*$:@:<:)^:(1&<) 8
40320

Generalization

Factorial, like all J's primitives, is generalized:

  ! 8 0.8 _0.8    NB.  Generalizes as the gamma function
40320 0.931384 4.59084
  ! 800x          NB.  Also arbitrarily large
7710530113353860041446393977750283605955564018160102391634109940339708518270930693670907697955390330926478612242306774446597851526397454014801846531749097625044706382742591201733097017026108750929188168469858421505936237186038616420630788341172340985137252...

Java

Iterative

<lang java5>public static long fact(int n){

  if(n < 0){
     System.err.println("No negative numbers");
     return 0;
  }
  long ans = 1;
  for(int i = 1;i <= n;i++){
     ans *= i;
  }
  return ans;

}</lang>

Recursive

<lang java5>public static long fact(int n){

  if(n < 0){
     System.err.println("No negative numbers");
     return 0;
  }
  if(n == 0) return 1;
  return n * fact(n-1);

}</lang>

JavaScript

<lang javascript>function factorial(n) {

 return n<2 ? 1 : n * factorial(n-1);

}</lang>

Lisaac

<lang Lisaac> - factorial x : INTEGER : INTEGER <- (

 + result : INTEGER;
 (x <= 1).if {
   result := 1;
 } else {
   result := x * factorial(x - 1);
 };
 result

); </lang>

Logo

to factorial :n
  if :n < 2 [output 1]
  output :n * factorial :n-1
end

M4

<lang M4> define(`factorial',`ifelse(`$1',0,1,`eval($1*factorial(decr($1)))')')dnl dnl factorial(5) </lang>

Output:

Mathematica

Note that Mathematica already comes with a factorial function, which can be used as e.g. 5! (gives 120). So the following implementations are only of pedagogical value.

Recursive

<lang mathematica> factorial[n_Integer] := n*factorial[n-1] factorial[0] = 1 </lang>

Iterative (direct loop)

<lang mathematica> factorial[n_Integer] :=

 Block[{i, result = 1}, For[i = 1, i <= n, ++i, result *= i]; result]

</lang>

Iterative (list)

factorial[n_Integer] := Block[{i}, Times @@ Table[i, {i, n}]]

MAXScript

Iterative

fn factorial n =
(
    if n == 0 then return 1
    local fac = 1
    for i in 1 to n do
    (
        fac *= i
    )
    fac
)

Recursive

fn factorial_rec n =
(
    local fac = 1
    if n > 1 then
    (
        fac = n * factorial_rec (n - 1)
    )
    fac
)

Modula-3

Iterative

<lang modula3>PROCEDURE FactIter(n: CARDINAL): CARDINAL =

 VAR
   result := n;
   counter := n - 1;
   
 BEGIN
   FOR i := counter TO 1 BY -1 DO
     result := result * i;
   END;
   RETURN result;
 END FactIter;</lang>

Recursive

<lang modula3>PROCEDURE FactRec(n: CARDINAL): CARDINAL =

 VAR result := 1;

 BEGIN
   IF n > 1 THEN
     result := n * FactRec(n - 1);
   END;
   RETURN result;
 END FactRec;</lang>

Nial

(from Nial help file)

fact is recur [ 0 =, 1 first, pass, product, -1 +]

Using it

|fact 4
=24

OCaml

Recursive

<lang ocaml>let rec factorial n =

 if n <= 0 then 1
 else n * factorial (n-1)</lang>

The following is tail-recursive, so it is effectively iterative: <lang ocaml>let factorial n =

 let rec loop i accum =
   if i > n then accum
   else loop (i + 1) (accum * i)
 in loop 1 1</lang>

Iterative

It can be done using explicit state, but this is usually discouraged in a functional language: <lang ocaml>let factorial n =

 let result = ref 1 in
 for i = 1 to n do
   result := !result * i
 done;
 !result</lang>

Octave

<lang octave>% built in factorial printf("%d\n", factorial(50));

% let's define our recursive... function fact = my_fact(n)

 if ( n <= 1 )
   fact = 1;
 else
   fact = n * my_fact(n-1);
 endif

endfunction

printf("%d\n", my_fact(50));

% let's define our iterative function fact = iter_fact(n)

 fact = 1;
 for i = 2:n
   fact = fact * i;
 endfor

endfunction

printf("%d\n", iter_fact(50));</lang>

Output:

30414093201713018969967457666435945132957882063457991132016803840
30414093201713375576366966406747986832057064836514787179557289984
30414093201713375576366966406747986832057064836514787179557289984

(Built-in is fast but use an approximation for big numbers)

Pascal

Iterative

<lang pascal> function factorial(n: integer): integer;

var
 i, result: integer;
begin
 result := 1;
 for i := 1 to n do
  result := result * i;
 factorial := result
end;

</lang>

Recursive

<lang pascal> function factorial(n: integer): integer;

begin
 if n = 0
  then
   factorial := 1
  else
   factorial := n*factorial(n-1)
end;

</lang>

Perl

Iterative

<lang perl>sub factorial {

 my $n = shift;
 my $result = 1;
 for (my $i = 1; $i <= $n; ++$i)
 {
   $result *= $i;
 };
 $result;

}

using a .. range

sub factorial {

   my $r = 1;
   $r *= $_ for 1..shift;
   $r;

}</lang>

Recursive

<lang perl>sub factorial {

 my $n = shift;
 ($n == 0)? 1 : $n*factorial($n-1);

}</lang>

Functional

<lang perl>use List::Util qw(reduce); sub factorial {

 my $n = shift;
 reduce { $a * $b } 1, 1 .. $n

}</lang>

Perl 6

Reduction Operator

<lang perl>sub postfix:<!> { [*] 1..$^n }

say 5!; #prints 120 </lang>

PHP

Iterative

<lang php> <?php function factorial($n) {

 if ($n < 0) {
   return 0;
 }

 $factorial = 1;
 for ($i = $n; $i >= 1; $i--) {
   $factorial = $factorial * $i;
 }

 return $factorial;

} ?> </lang>

Recursive

<lang php> <?php function factorial($n) {

 if ($n < 0) {
   return 0;
 }

 if ($n == 0) {
   return 1;
 }

 else {
   return $n * factorial($n-1);
 }

} ?> </lang>

Prolog

Works with: SWI Prolog

PowerShell

Recursive

<lang powershell>function Get-Factorial ($x) {

   if ($x -eq 0) {
       return 1
   }
   return $x * (Get-Factorial ($x - 1))

}</lang>

Iterative

<lang powershell>function Get-Factorial ($x) {

   if ($x -eq 0) {
       return 1
   } else {
       $product = 1
       1..$x | ForEach-Object { $product *= $_ }
       return $product
   }

}</lang>

Evaluative

Works with: PowerShell version 2

This one first builds a string, containing 1*2*3... and then lets PowerShell evaluate it. A bit of mis-use but works. <lang powershell>function Get-Factorial ($x) {

   if ($x -eq 0) {
       return 1
   }
   return (Invoke-Expression (1..$x -join '*'))

}</lang>

Python

Library

Works with: Python version 2.6+, 3.x

<lang python>import math math.factorial(n)</lang>

Iterative

<lang python>def factorial(n):

   if n == 0:
       return 1
   z=n
   while n>1:
       n=n-1
       z=z*n
   return z

</lang>

Functional

<lang python>from operator import mul

def factorial(n):

   return reduce(mul, xrange(1,n+1), 1)

</lang>

Sample output:

>>> for i in range(6):
    print i, factorial(i)
   
0 1
1 1
2 2
3 6
4 24
5 120
>>>

</lang>

Numerical Approximation

The following sample uses Lanczos approximation from wp:Lanczos_approximation <lang python> from cmath import *

Coefficients used by the GNU Scientific Library

g = 7 p = [0.99999999999980993, 676.5203681218851, -1259.1392167224028,

    771.32342877765313, -176.61502916214059, 12.507343278686905,
    -0.13857109526572012, 9.9843695780195716e-6, 1.5056327351493116e-7]

def gamma(z):

 z = complex(z)
 # Reflection formula
 if z.real < 0.5:
   return pi / (sin(pi*z)*gamma(1-z))
 else:
   z -= 1
   x = p[0]
   for i in range(1, g+2):
     x += p[i]/(z+i)
   t = z + g + 0.5
   return sqrt(2*pi) * t**(z+0.5) * exp(-t) * x

def factorial(n):

 return gamma(n+1)

print "factorial(-0.5)**2=",factorial(-0.5)**2 for i in range(10):

 print "factorial(%d)=%s"%(i,factorial(i))

</lang> Output:

factorial(-0.5)**2= (3.14159265359+0j)
factorial(0)=(1+0j)
factorial(1)=(1+0j)
factorial(2)=(2+0j)
factorial(3)=(6+0j)
factorial(4)=(24+0j)
factorial(5)=(120+0j)
factorial(6)=(720+0j)
factorial(7)=(5040+0j)
factorial(8)=(40320+0j)
factorial(9)=(362880+0j)

Recursive

<lang python>def factorial(n):

   z=1
   if n>1:
       z=n*factorial(n-1)
   return z

</lang>

R

Recursive

<lang R>fact <- function(n) {

 if ( n <= 1 ) 1
 else n * fact(n-1)

} </lang>

Iterative

<lang R> factIter <- function(n) {

 f = 1
 for (i in 2:n) f <- f * i
 f

}</lang>

Numerical Approximation

R has a native gamma function and a wrapper for that function that can produce factorials. E.g. <lang R>print(factorial(50)) # 3.041409e+64</lang>

Ruby

Recursive

<lang ruby>def factorial_recursive(n)

 n.zero? ? 1 : n * factorial_recursive(n - 1)

end</lang>

Iterative

<lang ruby>def factorial_iterative(n)

 n.downto(2).inject(1) {|factorial, i| factorial *= i}

end</lang>

Functional

<lang ruby>def factorial_functional(n)

 (1..n).reduce(1, :*)

end</lang>

Performance

<lang ruby>require 'benchmark'

n = 400 m = 10000

Benchmark.bm(12) do |b|

 b.report('recursive:')  {m.times {factorial_recursive(n)}}
 b.report('iterative:')  {m.times {factorial_iterative(n)}}
 b.report('functional:') {m.times {factorial_functional(n)}}

end</lang>

Output

                  user     system      total        real
recursive:   14.875000   0.000000  14.875000 ( 14.914000)
iterative:   14.203000   0.000000  14.203000 ( 14.451000)
functional:   9.125000   0.000000   9.125000 (  9.354000)

Scheme

Recursive

<lang scheme>(define (factorial n)

 (if (<= n 0)
     1
     (* n (factorial (- n 1)))))</lang>

The following is tail-recursive, so it is effectively iterative: <lang scheme>(define (factorial n)

 (let loop ((i 1)
            (accum 1))
   (if (> i n)
       accum
       (loop (+ i 1) (* accum i)))))</lang>

Iterative

<lang scheme>(define (factorial n)

 (do ((i 1 (+ i 1))
      (accum 1 (* accum i)))
     ((> i n) accum)))</lang>

Slate

This is already implemented in the core language as:

<lang slate> n@(Integer traits) factorial "The standard recursive definition." [

 n isNegative ifTrue: [error: 'Negative inputs to factorial are invalid.'].
 n <= 1
   ifTrue: [1]
   ifFalse: [n * ((n - 1) factorial)]

]. </lang>

Here is another way to implement it:

<lang slate> n@(Integer traits) factorial2 [

 n isNegative ifTrue: [error: 'Negative inputs to factorial are invalid.'].
 (1 upTo: n by: 1) reduce: [|:a :b| a * b]

]. </lang>

The output:

<lang slate> slate[5]> 100 factorial. 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 </lang>

Smalltalk

Smalltalk Number class already has a factorial method; however, let's see how we can implement it by ourselves.

Iterative with fold

Works with: GNU Smalltalk

<lang smalltalk>Number extend [

 my_factorial [
   (self < 2) ifTrue: [ ^1 ]
              ifFalse: [ |c|
                c := OrderedCollection new.
                2 to: self do: [ :i | c add: i ].

^ (c fold: [ :a :b | a * b ] )

              ]
 ]

].

7 factorial printNl. 7 my_factorial printNl.</lang>

Recursive

<lang smalltalk>Number extend [

 my_factorial [
   self < 0 ifTrue: [ self error: 'my_factorial is defined for natural numbers' ].
   self isZero ifTrue: [ ^1 ].
   ^self * ((self - 1) my_factorial)
 ]

].</lang>

Standard ML

Recursive

<lang sml>fun factorial n =

 if n <= 0 then 1
 else n * factorial (n-1)</lang>

The following is tail-recursive, so it is effectively iterative: <lang sml>fun factorial n = let

 fun loop (i, accum) =
   if i > n then accum
   else loop (i + 1, accum * i)

in

 loop (1, 1)

end</lang>

Tcl

Works with: Tcl version 8.5

Use Tcl 8.5 for its built-in arbitrary precision integer support.

Iterative

<lang tcl>proc ifact n {

   for {set i $n; set sum 1} {$i >= 2} {incr i -1} {
       set sum [expr {$sum * $i}]
   }
   return $sum

}</lang>

Recursive

<lang tcl>proc rfact n {

   expr {$n < 2 ? 1 : $n * [rfact [incr n -1]]}

}</lang>

The recursive version is limited by the default stack size to roughly 850!

When put into the tcl::mathfunc namespace, the recursive call stays inside the expr language, and thus looks clearer:

<lang Tcl>proc tcl::mathfunc::fact n {expr {$n < 2? 1: $n*fact($n-1)}}</lang>

Iterative with caching

<lang tcl>proc ifact_caching n {

   global fact_cache
   if { ! [info exists fact_cache]} {
       set fact_cache {1 1}
   }
   if {$n < [llength $fact_cache]} {
       return [lindex $fact_cache $n]
   }
   set i [expr {[llength $fact_cache] - 1}]
   set sum [lindex $fact_cache $i]
   while {$i < $n} {
       incr i
       set sum [expr {$sum * $i}]
       lappend fact_cache $sum
   }
   return $sum

}</lang>

Performance Analysis

<lang tcl>puts [ifact 30] puts [rfact 30] puts [ifact_caching 30]

set n 400 set iterations 10000 puts "calculate $n factorial $iterations times" puts "ifact: [time {ifact $n} $iterations]" puts "rfact: [time {rfact $n} $iterations]"

for the caching proc, reset the cache between each iteration so as not to skew the results

puts "ifact_caching: [time {ifact_caching $n; unset -nocomplain fact_cache} $iterations]"</lang> Output:

265252859812191058636308480000000
265252859812191058636308480000000
265252859812191058636308480000000
calculate 400 factorial 10000 times
ifact: 661.4324 microseconds per iteration
rfact: 654.7593 microseconds per iteration
ifact_caching: 613.1989 microseconds per iteration

TI-89 BASIC

TI-89 BASIC also has the factorial function built in: x! is the factorial of x.

factorial(x)
Func
  Return Π(y,y,1,x)
EndFunc

Π is the standard product operator: $\overbrace {\Pi (\mathrm {expr} ,i,a,b)} ^{\mathrm {TI-89} }=\overbrace {\prod _{i=a}^{b}\mathrm {expr} } ^{\text{Math notation}}$

UNIX Shell

Works with: bash

fact ()
{
  if [ $1 -eq 0 ];
    then echo 1;
    else echo $(($1 * $(fact $(($1-1)) ) ));
  fi;
}

Ursala

There is already a library function for factorials, but they can be defined anyway like this. The good method treats natural numbers as an abstract type, and the better method factors out powers of 2 by bit twiddling. <lang Ursala>

import nat

good_factorial = ~&?\1! product:-1^lrtPC/~& iota better_factorial = ~&?\1! ^T(~&lSL,@rS product:-1)+ ~&Z-~^*lrtPC/~& iota</lang> test program: <lang Ursala>#cast %nL

test = better_factorial* <0,1,2,3,4,5,6,7,8></lang> output:

<1,1,2,6,24,120,720,5040,40320>