Factorial

From Rosetta Code

Jump to: navigation, search
Task
Factorial
You are encouraged to solve this task according to the task description, using any language you may know.
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.

Contents

[edit] ActionScript

[edit] Iterative

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;
}

[edit] Recursive

public static function factorial(n:int):int
{
   if (n < 0)
       return 0;
 
   if (n == 0)
       return 1;
 
   return n * factorial(n - 1);
}

[edit] Ada

[edit] Iterative

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;

[edit] Recursive

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;

[edit] Numerical Approximation

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;

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)

[edit] ALGOL 68

[edit] Iterative

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

[edit] Numerical Approximation

[edit] ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny 

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)$;
 
test:(
  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

[edit] 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
; ~

[edit] AmigaE

Recursive solution: 

PROC fact(x) IS IF x>=2 THEN x*fact(x-1) ELSE 1
 
PROC main()
  WriteF('5! = \d\n', fact(5))
ENDPROC

Iterative: 

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

[edit] AppleScript

[edit] Iterative

on factorial(x)
	if x < 0 then return 0
	set R to 1
	repeat while x > 1
		set {R, x} to {R * x, x - 1}
	end repeat
	return R
end factorial

[edit] Recursive

on factorial(x)
	if x < 0 then return 0
	if x > 1 then return x * (my factorial(x - 1))
	return 1
end factorial

[edit] AutoHotkey

[edit] Iterative

MsgBox % factorial(4)
 
factorial(n)
{
  result := 1 
  Loop, % n
    result *= A_Index
  Return result 
}

[edit] Recursive

MsgBox % factorial(4)
 
factorial(n)
{
  return n > 1 ? n-- * factorial(n) : 1
}

[edit] AWK

Recursive 

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

Iterative 

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

[edit] BASIC

[edit] Iterative

Works with: FreeBASIC Works with: RapidQ 

 
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
 

[edit] Recursive

Works with: FreeBASIC Works with: RapidQ 

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

[edit] bc

#! /usr/bin/bc -q
 
define f(x) { if (x <= 1) return (1); return (f(x-1) * x); }
f(1000)
quit

[edit] Befunge

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

[edit] C

[edit] Iterative 

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

[edit] Recursive 

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

[edit] Tail Recursive

Safe with some compilers (e.g. GCC with -O2, LLVM's clang) 

int fac_aux(int n, int acc) {
  if (n < 1)
    return acc;
  else
    return fac_aux(n-1, acc*n);
}
 
int factorial(int n) {
  return fac_aux(n, 1);
}

[edit] C++

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

#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>());
}

[edit] Iterative

This version of the program is iterative, with a do-while loop. 

 
long long int Factorial(long long int m_nValue)
   {
       long long int result=m_nValue;
       long long int result_next;
       long long int pc = m_nValue;
       do
       {
           result_next = result*(pc-1);
           result = result_next;
           pc--;
       }while(pc>2);
       m_nValue = result;
       return m_nValue;
   }
 

[edit] C#

[edit] Recursive

 
class Program {
     static long fact(int n) {         
         if (n == 0) return 1;
         return n * fact(n - 1);
     }     
 
     static void Main(string[] args) {
         System.Console.WriteLine(fact(5)); //Example
     }     
}

[edit] Iterative

 
class Program {
    static long fact(int n) {        
        long f = 1; 
        for( int i = 2; i<=n; i++) f=f*i;    
        return f;
    }     
 
    static void Main(string[] args) {
        System.Console.WriteLine(fact(5)); //Example
    }    
}

[edit] Chef

Caramel Factorials.
 
Only reads one value.
 
Ingredients.
1 g Caramel
2 g Factorials
 
Method.
Take Factorials from refrigerator.
Put Caramel into 1st mixing bowl.
Verb the Factorials.
Combine Factorials into 1st mixing bowl.
Verb Factorials until verbed.
Pour contents of the 1st mixing bowl into the 1st baking dish.
 
Serves 1.

[edit] Clojure

[edit] Folding 

(defn factorial [x]
  (apply * (range 2 (inc x)))
)

Or, in more idiomatical functional style: 

(defn factorial [x]
  (reduce * (range 2 (inc x)))
)

[edit] Recursive 

(defn factorial [x]
  (if (< x 2)
      1
      (* x (factorial (dec x)))))

[edit] Tail recursive 

(defn factorial [x]
  (loop [x x
         acc 1]
    (if (< x 2)
        acc
        (recur (dec x) (* acc x)))))

[edit] Common Lisp

Recursive: 

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

Iterative: 

(defun factorial (n)
  "Calculates N!"
  (loop for result = 1 then (* result i)
     for i from 2 to n 
     finally (return result)))

[edit] D

import std.stdio: writeln;
import std.metastrings: toStringNow;
import std.algorithm: reduce, iota;
 
// iterative
int factorial(int n) {
    int result = 1;
    foreach (i; 1 .. n+1)
        result *= i;
    return result;
}
 
// recursive
int recFactorial(int n) {
    if (n == 0)
        return 1;
    else
        return n * recFactorial(n - 1);
}
 
// functional-style
int fact(int n) {
    return reduce!q{a * b}(iota(1, n+1));
}
 
// tail recursive (at run-time, with DMD)
int tfactorial(int n) {
    static int facAux(int n, int acc) {
        if (n < 1)
            return acc;
        else
            return facAux(n - 1, acc * n);
    }
    return facAux(n, 1);
}
 
// computed and printed at compile-time
pragma(msg, toStringNow!(factorial(15)));
pragma(msg, toStringNow!(recFactorial(15)));
pragma(msg, toStringNow!(fact(15)));
pragma(msg, toStringNow!(tfactorial(15)));
 
void main() {
    // computed and printed at run-time
    writeln(factorial(15));
    writeln(recFactorial(15));
    writeln(fact(15));
    writeln(tfactorial(15));
}

[edit] Dylan

define method factorial(n)
  reduce1(\*, range(from: 1, to: n));
end

[edit] E

pragma.enable("accumulator")
def factorial(n) {
  return accum 1 for i in 2..n { _ * i }
}

[edit] Emacs Lisp

 
(defun fact (n)
  "n is an integer, this function returns n!, that is n * (n - 1)
* (n - 2)....* 4 * 3 * 2 * 1"
  (cond
   ((= n 1) 1)
   (t (* n (fact (1- n))))))
 


[edit] Erlang

With a fold: 

lists:foldl(fun(X,Y) -> X*Y end, 1, lists:seq(1,N)).

With a recursive function: 

fac(1) -> 1;
fac(N) -> N * fac(N-1).

With a tail-recursive function: 

fac(N) -> fac(N-1,N).
fac(1,N) -> N;
fac(I,N) -> fac(I-1,N*I).

[edit] Factor

Translation of: Haskell 

USING: math.ranges sequences ;
 
: factorial ( n -- n ) [1,b] product ;

The [1,b] word takes a number from the stack and pushes a range, which is then passed to product.

[edit] FALSE

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

Recursive: 

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

[edit] Forth

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

[edit] 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

[edit] F#

This is a fast tail-recursive implementation. 

let factorial n : bigint =
    let rec f a n =
        match n with
        | 0I -> a
        | n -> (f (a * n) (n - 1I))
    f 1I n
> factorial 8I;;
val it : bigint = 40320I
> factorial 800I;;
val it : bigint = 771053011335386004144639397775028360595556401816010239163410994033970851827093069367090769795539033092647861224230677444659785152639745401480184653174909762504470638274259120173309701702610875092918816846985842150593623718603861642063078834117234098513725265045402523056575658860621238870412640219629971024686826624713383660963127048195572279707711688352620259869140994901287895747290410722496106151954257267396322405556727354786893725785838732404646243357335918597747405776328924775897564519583591354080898117023132762250714057271344110948164029940588827847780442314473200479525138318208302427727803133219305210952507605948994314345449325259594876385922128494560437296428386002940601874072732488897504223793518377180605441783116649708269946061380230531018291930510748665577803014523251797790388615033756544830374909440162270182952303329091720438210637097105616258387051884030288933650309756289188364568672104084185529365727646234588306683493594765274559497543759651733699820639731702116912963247441294200297800087061725868223880865243583365623482704395893652711840735418799773763054887588219943984673401051362280384187818611005035187862707840912942753454646054674870155072495767509778534059298038364204076299048072934501046255175378323008217670731649519955699084482330798811049166276249251326544312580289357812924825898217462848297648349400838815410152872456707653654424335818651136964880049831580548028614922852377435001511377656015730959254647171290930517340367287657007606177675483830521499707873449016844402390203746633086969747680671468541687265823637922007413849118593487710272883164905548707198762911703545119701275432473548172544699118836274377270607420652133092686282081777383674487881628800801928103015832821021286322120460874941697199487758769730544922012389694504960000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000I

[edit] Genyris

[edit] Recursive 

def factorial (n)
    if (< n 2) 1
      * n
        factorial (- n 1)

[edit] Golfscript

Iterative (uses folding) 

{.!{1}{,{)}%{*}*}if}:fact;
5fact puts # test

Recursive 

{.1<{;1}{.(fact*}if}:fact;

[edit] Groovy

[edit] Recursive

A recursive closure must be pre-declared. 

def rFact
rFact = { (it > 1) ? it * rFact(it - 1) : 1 }

Test program: 

(0..6).each { println "${it}: ${rFact(it)}" }

Output: 

0: 1
1: 1
2: 2
3: 6
4: 24
5: 120
6: 720

[edit] Iterative 

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

Test program: 

(0..6).each { println "${it}: ${iFact(it)}" }

Output: 

0: 1
1: 1
2: 2
3: 6
4: 24
5: 120
6: 720

[edit] 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]

See also: The Evolution of a Haskell Programmer

Or, if you wanted to generate a list of all the factorials: 

factorials = scanl (*) 1 [1..]

Or, written without library functions: 

 
factorial :: Integral -> Integral
factorial 0 = 1
factorial n = n * factorial (n-1)
 

[edit] HicEst

WRITE(Clipboard) factorial(6)  ! pasted: 720
 
FUNCTION factorial(n)
   factorial = 1
   DO i = 2, n
      factorial = factorial * i
   ENDDO
END

[edit] IDL

function fact,n
   return, product(lindgen(n)+1)
end

[edit] Icon and Unicon

[edit] Icon

[edit] Recursive

procedure factorial(n)     
   n := integer(n) | runerr(101, n)
   if n < 0 then fail
   return if n = 0 then 1 else n*factorial(n-1)
end

[edit] Iterative

The Library: Icon Programming Library factors provides the following iterative procedure which can be included with 'link factors': 

procedure factorial(n)			#: return n! (n factorial)
   local i
   n := integer(n) | runerr(101, n)
   if n < 0 then fail
   i := 1
   every i *:= 1 to n
   return i
end

[edit] Unicon

The Icon solution works in Unicon.

[edit] J

[edit] Operator 

  ! 8             NB.  Built in factorial operator
40320

[edit] Iterative / Functional 

   */1+i.8
40320

[edit] Recursive 

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

[edit] 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...

[edit] Java

[edit] Iterative

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;
}

[edit] Recursive

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);
}

[edit] JavaScript

Several solutions are possible in JavaScript:

[edit] Iterative 

function factorial(n) {
  var x = 1;
  for (var i=2; i<n; i++) {
    x *= n;
  }
  return x;
}

[edit] Recursive 

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

[edit] Functional

Works with: JavaScript version 1.8 (See MDC) 

function factorial(n) {
  var nums = [1];
  for (var i=2; i<=n; i++) { // No built-in function to generate array of numbers a to n :(
    nums.push(n);
  }
  return nums.reduce(function(a, b) {return a*b});
}

[edit] Lisaac

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

[edit] Logo

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

[edit] Lua

[edit] Recursive

 
function fact(n)
  return n > 0 and n * fact(n-1) or 1
end
 

[edit] Tail Recursive

 
function fact(n, acc)
  acc = acc or 1
  if n == 0 then
    return acc
  end
  return fact(n-1, n*acc)
end
 

[edit] M4

define(`factorial',`ifelse(`$1',0,1,`eval($1*factorial(decr($1)))')')dnl
dnl
factorial(5)

Output: 

120

[edit] 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.

[edit] Recursive 

factorial[n_Integer] := n*factorial[n-1]
factorial[0] = 1

[edit] Iterative (direct loop) 

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

[edit] Iterative (list) 

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

[edit] MATLAB

The factorial function is built-in to MATLAB. The built-in function is only accurate for N <= 21 due to the precision limitations of floating point numbers. 

answer = factorial(N)

A possible iterative solution: 

  function b=factorial(a)
	b=1;	
	for i=1:a	
	    b=b*i;
	end

[edit] MAXScript

[edit] Iterative 

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

[edit] Recursive 

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

[edit] Modula-3

[edit] Iterative

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;

[edit] Recursive

PROCEDURE FactRec(n: CARDINAL): CARDINAL =
  VAR result := 1;
 
  BEGIN
    IF n > 1 THEN
      result := n * FactRec(n - 1);
    END;
    RETURN result;
  END FactRec;


[edit] MUMPS

[edit] Iterative

 
factorial(num)	New ii,result
	If num<0 Quit "Negative number"
	If num["." Quit "Not an integer"
	Set result=1 For ii=1:1:num Set result=result*ii
	Quit result
 
Write $$factorial(0) ; 1
Write $$factorial(1) ; 1
Write $$factorial(2) ; 2
Write $$factorial(3) ; 6
Write $$factorial(10) ; 3628800
Write $$factorial(-6) ; Negative number
Write $$factorial(3.7) ; Not an integer

[edit] Recursive

factorial(num)	;
	If num<0 Quit "Negative number"
	If num["." Quit "Not an integer"
	If num<2 Quit 1
	Quit num*$$factorial(num-1)
 
Write $$factorial(0) ; 1
Write $$factorial(1) ; 1
Write $$factorial(2) ; 2
Write $$factorial(3) ; 6
Write $$factorial(10) ; 3628800
Write $$factorial(-6) ; Negative number
Write $$factorial(3.7) ; Not an integer


[edit] Nial

(from Nial help file) 

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

Using it 

|fact 4
=24

[edit] Niue

[edit] Recursive

[ dup 1 > [ dup 1 - factorial * ] when ] 'factorial ;
 
( test )
4 factorial . ( => 24 )
10 factorial . ( => 3628800 )
 

[edit] Objeck

[edit] Iterative

 
bundle Default {
  class Fact {
    function : Main(args : String[]) ~ Nil {
      5->Factorial()->PrintLine();
    }
  }
}
 

[edit] OCaml

[edit] Recursive

let rec factorial n =
  if n <= 0 then 1
  else n * factorial (n-1)

The following is tail-recursive, so it is effectively iterative: 

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

[edit] Iterative

It can be done using explicit state, but this is usually discouraged in a functional language: 

let factorial n =
  let result = ref 1 in
  for i = 1 to n do
    result := !result * i
  done;
  !result

[edit] 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));

Output: 

30414093201713018969967457666435945132957882063457991132016803840
30414093201713375576366966406747986832057064836514787179557289984
30414093201713375576366966406747986832057064836514787179557289984

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

[edit] Oz

[edit] Folding 

fun {Fac1 N}
   {FoldL {List.number 1 N 1} Number.'*' 1}
end

[edit] Tail recursive 

fun {Fac2 N}
   fun {Loop N Acc}
      if N < 1 then Acc
      else
	 {Loop N-1 N*Acc}
      end
   end
in
   {Loop N 1}
end

[edit] Iterative 

fun {Fac3 N}
   Result = {NewCell 1}
in
   for I in 1..N do
      Result := @Result * I
   end
   @Result
end

[edit] Pascal

[edit] Iterative 

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

[edit] Recursive 

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

[edit] Perl

[edit] Iterative 

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;
}

[edit] Recursive 

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

[edit] Functional 

use List::Util qw(reduce);
sub factorial
{
  my $n = shift;
  reduce { $a * $b } 1, 1 .. $n
}

[edit] Perl 6

Works with: Rakudo version #22 "Thousand Oaks" 

sub postfix:<!> { [*] 1..$^n }
 
say 5!;  #prints 120

[edit] PHP

[edit] Iterative 

<?php
function factorial($n) {
  if ($n < 0) {
    return 0;
  }
 
  $factorial = 1;
  for ($i = $n; $i >= 1; $i--) {
    $factorial = $factorial * $i;
  }
 
  return $factorial;
}
?>

[edit] Recursive 

<?php
function factorial($n) {
  if ($n < 0) {
    return 0;
  }
 
  if ($n == 0) {
    return 1;
  }
 
  else {
    return $n * factorial($n-1);
  }
}
?>

[edit] One-Liner 

<?php
function factorial($n) {
  return $n == 0 ? 1 : array_product(range(1, $n));
}
?>

[edit] Library

Requires the GMP library to be compiled in: 

gmp_fact($n)

[edit] PicoLisp

(de fact (N)
   (if (=0 N)
      1
      (* N (fact (dec N))) ) )

or: 

(de fact (N)
   (apply * (range 1 N) )

[edit] PL/I

 
factorial: procedure (N) returns (fixed decimal (30));
   declare N fixed binary nonassignable;
   declare i fixed decimal (10);
   declare F fixed decimal (30);
 
   if N < 0 then signal error;
   F = 1;
   do i = 2 to N;
      F = F * i;
   end;
   return (F);
end factorial;
 

[edit] Prolog

Works with: SWI Prolog 

fact(X, 1) :- X<2.
fact(X, F) :- Y is X-1, fact(Y,Z), F is Z*X.

[edit] PostScript

[edit] Recursive

/factorial{
/num exch def
num 0 eq
{1}
{num num 1 sub factorial mul}
ifelse
}def
 
5 factorial =
 

[edit] PowerShell

[edit] Recursive

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

[edit] Iterative

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

[edit] 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. 

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

[edit] Pure

[edit] Recursive

fact n = n*fact (n-1) if n>0;
       = 1 otherwise;
let facts = map fact (1..10); facts;

[edit] Tail Recursive

fact n = loop 1 n with
  loop p n = if n>0 then loop (p*n) (n-1) else p;
end;

[edit] PureBasic

[edit] Iterative

Procedure factorial(n)
  Protected i, f = 1
  For i = 2 To n
    f = f * i
  Next
  ProcedureReturn f
EndProcedure

[edit] Recursive

Procedure Factorial(n)
  If n < 2
    ProcedureReturn 1
  Else
    ProcedureReturn n * Factorial(n - 1)
  EndIf
EndProcedure

[edit] Python

[edit] Library

Works with: Python version 2.6+, 3.x 

import math
math.factorial(n)

[edit] Iterative

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

[edit] Functional

from operator import mul
 
def factorial(n):
    return reduce(mul, xrange(1,n+1), 1)

Sample output: 

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

[edit] Numerical Approximation

The following sample uses Lanczos approximation from wp:Lanczos_approximation 

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))

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)

[edit] Recursive

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

[edit] Q

[edit] Iterative

[edit] Point-free

f:(*/)1+til@

or 

f:(*)over 1+til@

or 

f:prd 1+til@

[edit] As a function

f:{(*/)1+til x}

[edit] Recursive

f:{$[x=1;1;x*.z.s x-1]}


[edit] R

[edit] Recursive 

fact <- function(n) {
  if ( n <= 1 ) 1
  else n * fact(n-1)
}

[edit] Iterative

factIter <- function(n) {
  f = 1
  for (i in 2:n) f <- f * i
  f
}

[edit] Numerical Approximation

R has a native gamma function and a wrapper for that function that can produce factorials. E.g. 

print(factorial(50)) # 3.041409e+64

[edit] REBOL

rebol [
    Title: "Factorial"
    Author: oofoe
    Date: 2009-12-10
    URL: http://rosettacode.org/wiki/Factorial_function
]
 
; Standard recursive implementation.
 
factorial: func [n][
	either n > 1 [n * factorial n - 1] [1]
]
 
; Iteration.
 
ifactorial: func [n][
	f: 1
	for i 2 n 1 [f: f * i]
	f
]
 
; Automatic memoization.
; I'm just going to say up front that this is a stunt. However, you've
; got to admit it's pretty nifty. Note that the 'memo' function
; works with an unlimited number of arguments (although the expected
; gains decrease as the argument count increases).
 
memo: func [
	"Defines memoizing function -- keeps arguments/results for later use."
	args [block!] "Function arguments. Just specify variable names."
	body [block!] "The body block of the function."
	/local m-args m-r
][
	do compose/deep [
		func [
			(args)
			/dump "Dump memory."
		][
			m-args: []
			if dump [return m-args]
 
			if m-r: select/only m-args reduce [(args)] [return m-r]
 
			m-r: do [(body)]
			append m-args reduce [reduce [(args)] m-r]
			m-r
		]
	]
]
 
mfactorial: memo [n][
	either n > 1 [n * mfactorial n - 1] [1]
]
 
; Test them on numbers zero to ten.
 
for i 0 10 1 [print [i ":" factorial i  ifactorial i  mfactorial i]]

Output: 

0 : 1 1 1
1 : 1 1 1
2 : 2 2 2
3 : 6 6 6
4 : 24 24 24
5 : 120 120 120
6 : 720 720 720
7 : 5040 5040 5040
8 : 40320 40320 40320
9 : 362880 362880 362880
10 : 3628800 3628800 3628800

More on memoization...

[edit] Ruby

[edit] Recursive

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

[edit] Iterative

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

[edit] Functional

def factorial_functional(n)
  (1..n).reduce(1, :*)
end

[edit] Performance

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

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)

[edit] Sather

class MAIN is
 
  -- recursive
  fact(a: INTI):INTI is
    if a < 1.inti then return 1.inti; end;
    return a * fact(a - 1.inti);
  end;
 
  -- iterative
  fact_iter(a:INTI):INTI is
    s ::= 1.inti;
    loop s := s * a.downto!(1.inti); end;
    return s;
  end;
 
  main is
    a :INTI := 10.inti;
    #OUT + fact(a) + " = " + fact_iter(a) + "\n";
  end;
end;


[edit] Scala

[edit] Imperative

def factorial(n: Int)={
  var res = 1
  if(n > 0)
    for(i <- 1 to n)
      res *=i 
  res
}
 

[edit] Recursive

def factorial(n: Int): Int ={
  if(n == 0) 1
  else n * factorial(n-1)
}

[edit] Folding

def factorial(n: Int) = (2 to n).foldLeft(1)(_*_) 
 

[edit] Scheme

[edit] Recursive

(define (factorial n)
  (if (<= n 0)
      1
      (* n (factorial (- n 1)))))

The following is tail-recursive, so it is effectively iterative: 

(define (factorial n)
  (let loop ((i 1)
             (accum 1))
    (if (> i n)
        accum
        (loop (+ i 1) (* accum i)))))

[edit] Iterative

(define (factorial n)
  (do ((i 1 (+ i 1))
       (accum 1 (* accum i)))
      ((> i n) accum)))

[edit] Sisal

Solution using a fold: 

define main
 
function main(x : integer returns integer)
 
  for a in 1, x
    returns
      value of product a
  end for
 
end function

Simple example using a recursive function: 

define main
 
function main(x : integer returns integer)
 
  if x = 0 then
    1
  else
    x * main(x - 1)
  end if
 
end function

[edit] Slate

This is already implemented in the core language as:

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)]
].

Here is another way to implement it: 

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

The output: 

slate[5]> 100 factorial.
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

[edit] Smalltalk

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

[edit] Iterative with fold

Works with: GNU 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.

[edit] Recursive

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)
  ]
].

[edit] SNOBOL4

Works with: Macro Spitbol Works with: CSnobol

Note: Snobol4+ overflows after 7! because of signed short int limitation.

[edit] Recursive

        define('rfact(n)') :(rfact_end)
rfact   rfact = le(n,0) 1 :s(return)
        rfact = n * rfact(n - 1) :(return)
rfact_end

[edit] Tail-recursive

        define('trfact(n,f)') :(trfact_end)
trfact  trfact = le(n,0) f :s(return)
        trfact = trfact(n - 1, n * f) :(return)
trfact_end

[edit] Iterative

        define('ifact(n)') :(ifact_end)
ifact   ifact = 1
if1     ifact = gt(n,0) n * ifact :f(return)
        n = n - 1 :(if1)
ifact_end

Test and display factorials 0 .. 10 

loop    i = le(i,10) i + 1 :f(end)
        output = rfact(i) ' ' trfact(i,1) ' ' ifact(i) :(loop)
end

Output: 

1 1 1
2 2 2
6 6 6
24 24 24
120 120 120
720 720 720
5040 5040 5040
40320 40320 40320
362880 362880 362880
3628800 3628800 3628800
39916800 39916800 39916800

[edit] Standard ML

[edit] Recursive

fun factorial n =
  if n <= 0 then 1
  else n * factorial (n-1)

The following is tail-recursive, so it is effectively iterative: 

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

[edit] Tcl

Works with: Tcl version 8.5
Use Tcl 8.5 for its built-in arbitrary precision integer support.

[edit] Iterative

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

[edit] Recursive

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

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: 

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

[edit] Iterative with caching

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
}

[edit] Performance Analysis

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]"

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

[edit] 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}}

[edit] UNIX Shell

Works with: bash 

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

[edit] 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. 

#import nat
 
good_factorial   = ~&?\1! product:-1^lrtPC/~& iota
better_factorial = ~&?\1! ^T(~&lSL,@rS product:-1)+ ~&Z-~^*lrtPC/~& iota

test program: 

#cast %nL
 
test = better_factorial* <0,1,2,3,4,5,6,7,8>

output: 

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

[edit] VBScript

Optimized with memoization, works for numbers up to 170 (because of the limitations on Doubles), exits if -1 is input 

Dim lookupTable(170), returnTable(170), currentPosition, input
currentPosition = 0
 
Do While True
	input = InputBox("Please type a number (-1 to quit):")
	MsgBox "The factorial of " & input & " is " & factorial(CDbl(input))
Loop
 
Function factorial (x)
	If x = -1 Then
		WScript.Quit 0
	End If
	Dim temp
	temp = lookup(x)
	If x <= 1 Then
		factorial = 1
	ElseIf temp <> 0 Then
		factorial = temp
	Else
		temp = factorial(x - 1) * x
		store x, temp
		factorial = temp
	End If
End Function
 
Function lookup (x)
	Dim i
	For i = 0 To currentPosition - 1
		If lookupTable(i) = x Then
			lookup = returnTable(i)
			Exit Function
		End If
	Next
	lookup = 0
End Function
 
Function store (x, y)
	lookupTable(currentPosition) = x
	returnTable(currentPosition) = y
	currentPosition = currentPosition + 1
End Function
 

[edit] x86 Assembly

Works with: nasm

[edit] Iterative

global factorial
section .text
 
; Input in ECX register (greater than 0!)
; Output in EAX register
factorial:
  mov   eax, 1
.factor:
  mul   ecx
  loop  .factor
  ret

[edit] Recursive

global fact
section .text
 
; Input and output in EAX register
fact:
  cmp    eax, 1
  je    .done   ; if eax == 1 goto done
 
  ; inductive case
  push  eax  ; save n (ie. what EAX is)
  dec   eax  ; n - 1
  call  fact ; fact(n - 1)
  pop   ebx  ; fetch old n
  mul   ebx  ; multiplies EAX with EBX, ie. n * fac(n - 1)
  ret
 
.done:
  ; base case: return 1
  mov   eax, 1
  ret

[edit] Tail Recursive

global factorial
section .text
 
; Input in ECX register
; Output in EAX register
factorial:
  mov   eax, 1  ; default argument, store 1 in accumulator
 
.base_case:
  test  ecx, ecx
  jnz   .inductive_case  ; return accumulator if n == 0
  ret
 
.inductive_case:
  mul   ecx         ; accumulator *= n
  dec   ecx         ; n -= 1
  jmp   .base_case  ; tail call
Retrieved from "http://rosettacode.org/wiki/Factorial"
Personal tools
Support