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.

ABAP

Iterative

<lang ABAP>form factorial using iv_val type i.

 data: lv_res type i value 1.
 do iv_val times.
   multiply lv_res by sy-index.
 enddo.

 iv_val = lv_res.

endform.</lang>

Recursive

<lang ABAP>form fac_rec using iv_val type i.

 data: lv_temp type i.

 if iv_val = 0.
   iv_val = 1.
 else.
   lv_temp = iv_val - 1.
   perform fac_rec using lv_temp.
   multiply iv_val by lv_temp.
 endif.

endform.</lang>

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

<lang algol68>PROC factorial = (INT upb n)LONG LONG INT:(

 LONG LONG INT z := 1;
 FOR n TO upb n DO z *:= n OD;
 z

); ~</lang>

Numerical Approximation

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

<lang algol68>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

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

<lang algol68>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

~</lang>

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>

AppleScript

Iterative

<lang AppleScript>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</lang>

Recursive

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

AutoHotkey

Iterative

<lang AutoHotkey>MsgBox % factorial(4)

factorial(n) {

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

}</lang>

Recursive

<lang AutoHotkey>MsgBox % factorial(4)

factorial(n) {

 return n > 1 ? n-- * factorial(n) : 1

}</lang>

AutoIt

Iterative

<lang AutoIt>;AutoIt Version: 3.2.10.0 MsgBox (0,"Factorial",factorial(6)) Func factorial($int)

   If $int < 0 Then
     Return 0
  EndIf
  $fact = 1
  For $i = 1 To $int
       $fact = $fact * $i
  Next
  Return $fact

EndFunc </lang>

Recursive

<lang AutoIt>;AutoIt Version: 3.2.10.0 MsgBox (0,"Factorial",factorial(6)) Func factorial($int)

  if $int < 0 Then
     return 0
  Elseif $int == 0 Then
     return 1
  EndIf
  return $int * factorial($int - 1)

EndFunc </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>

Batch File

   @echo off
   set /p x=
   set /a fs=%x%-1
   set y=%x%
   FOR /L %%a IN (%fs%, -1, 1) DO SET /a y*=%%a
   if %x% EQU 0 set y=1
   echo %y%
   pause
   exit

bc

<lang bc>#! /usr/bin/bc -q

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

Befunge

<lang befunge>&1\> :v v *<

  ^-1:_$>\:|
        @.$<</lang>

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>

Tail Recursive

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

<lang c>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);

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

Iterative

This version of the program is iterative, with a do-while loop. <lang cpp> 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;
  }

</lang>

C#

Iterative

<lang csharp>using System;

class Program {

   static int Factorial(int number)
   {
       int accumulator = 1;
       for (int factor = 1; factor <= number; factor++)
       {
           accumulator *= factor;
       }
       return accumulator;
   }

   static void Main()
   {
       Console.WriteLine(Factorial(10));
   }

}</lang>

Recursive

<lang csharp>using System;

class Program {

   static int Factorial(int number)
   {
       return number == 0 ? 1 : number * Factorial(number - 1);
   }

   static void Main()
   {
       Console.WriteLine(Factorial(10));
   }

}</lang>

Tail Recursive

<lang csharp>using System;

class Program {

   static int Factorial(int number)
   {
       return Factorial(number, 1);
   }

   static int Factorial(int number, int accumulator)
   {
       return number == 0 ? accumulator : Factorial(number - 1, number * accumulator);
   }

   static void Main()
   {
       Console.WriteLine(Factorial(10));
   }

}</lang>

Functional

<lang csharp>using System; using System.Linq;

class Program {

   static int Factorial(int number)
   {
       return Enumerable.Range(1, number).Aggregate((accumulator, factor) => accumulator * factor);
   }

   static void Main()
   {
       Console.WriteLine(Factorial(10));
   }

}</lang>

Chef

<lang 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.</lang>

CLIPS

(deffunction factorial (?a)
   (if (or (not (integerp ?a)) (< ?a 0)) then
       (printout t "Factorial Error!" crlf)
    else
       (if (= ?a 0) then
           1
        else
           (* ?a (factorial (- ?a 1))))))

Clojure

Folding

<lang lisp>(defn factorial [x]

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

)</lang>

Or, in more idiomatical functional style: <lang lisp>(defn factorial [x]

 (reduce * (range 2 (inc x)))

)</lang>

Recursive

<lang lisp>(defn factorial [x]

 (if (< x 2)
     1
     (* x (factorial (dec x)))))</lang>

Tail recursive

<lang lisp>(defn factorial [x]

 (loop [x x
        acc 1]
   (if (< x 2)
       acc
       (recur (dec x) (* acc 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

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

}</lang>

Dylan

<lang dylan>define method factorial(n)

 reduce1(\*, range(from: 1, to: n));

end</lang>

E

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

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

}</lang>

Emacs Lisp

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

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

Factor

Translation of: Haskell

<lang factor>USING: math.ranges sequences ;

factorial ( n -- n ) [1,b] product ;</lang>

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

FALSE

<lang false>[1\[$][$@*\1-]#%]f: ^'0- f;!.</lang> Recursive: <lang false>[$1=~[$1-f;!*]?]f:</lang>

Fancy

<lang fancy>def class Number {

 def factorial {
   1 upto: self . product
 }

}

print first ten factorials

1 upto: 10 do_each: |i| {

 i to_s ++ "! = " ++ (i factorial) println

}</lang>

Forth

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

<lang fortran> 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

GAP

<lang gap># Built-in Factorial(5);

An implementation

fact := n -> Product([1 .. n]);</lang>

Genyris

Recursive

<lang genyris>def factorial (n)

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

GML

<lang GML>argument0 = n j = 1 for(i = 1; i <= n; i += 1)

   j *= i

return j

Golfscript

Iterative (uses folding) <lang golfscript>{.!{1}{,{)}%{*}*}if}:fact; 5fact puts # test</lang>

Recursive <lang golfscript>{.1<{;1}{.(fact*}if}:fact;</lang>

Go

Built in function currently uses a simple divide and conquer technique. It's a step up from sequential multiplication. <lang go> package main

import (

   "big"
   "fmt"

)

func factorial(n int64) *big.Int {

   var z big.Int
   return z.MulRange(1, n)

}

func main() {

   fmt.Println(factorial(100))

} </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: <lang haskell>factorial n = product [1..n]</lang>

Or, written explicitly as a fold: <lang haskell>factorial n = foldl (*) 1 [1..n]</lang>

Or, if you wanted to generate a list of all the factorials: <lang haskell>factorials = scanl (*) 1 [1..]</lang>

Or, written without library functions:

<lang haskell> factorial :: Integral -> Integral factorial 0 = 1 factorial n = n * factorial (n-1) </lang>

HicEst

<lang hicest>WRITE(Clipboard) factorial(6) ! pasted: 720

FUNCTION factorial(n)

  factorial = 1
  DO i = 2, n
     factorial = factorial * i
  ENDDO

END</lang>

IDL

<lang idl>function fact,n

  return, product(lindgen(n)+1)

end</lang>

Icon and Unicon

Works with: Unicon

Recursive

<lang Icon>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 </lang>

Iterative

The

Library: Icon Programming Library

factors provides the following iterative procedure which can be included with 'link factors':

<lang Icon>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</lang>

J

Operator

<lang j> ! 8 NB. Built in factorial operator 40320</lang>

Iterative / Functional

Recursive

Generalization

Factorial, like most of J's primitives, is generalized:

<lang j> ! 8 0.8 _0.8 NB. Generalizes as the gamma function 40320 0.931384 4.59084

 ! 800x          NB.  Also arbitrarily large

7710530113353860041446393977750283605955564018160102391634109940339708518270930693670907697955390330926478612242306774446597851526397454014801846531749097625044706382742591201733097017026108750929188168469858421505936237186038616420630788341172340985137252...</lang>

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;
  }
  return (n < 2) ? 1 : n * fact(n-1);

} </lang>

JavaScript

Several solutions are possible in JavaScript:

Iterative

<lang javascript>function factorial(n) {

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

}</lang>

Recursive

<lang javascript>function factorial(n) {

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

}</lang>

Functional

Works with: JavaScript version 1.8

(See MDC)

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

}</lang>

Korn Shell

Iterative

<lang korn>function factorial {

 typeset n=$1 f=1 i
 for ((i=2; i < n; i++)); do
   (( f *= i ))
 done
 echo $f

}</lang>

Recursive

<lang korn>function factorial {

 typeset n=$1
 (( n < 2 )) && echo 1 && return
 echo $(( 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

<lang logo>to factorial :n

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

end</lang>

Lua

Recursive

<lang lua> function fact(n)

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

end </lang>

Tail Recursive

<lang lua> function fact(n, acc)

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

end </lang>

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

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. <lang matlab>answer = factorial(N)</lang>

A possible iterative solution:

<lang matlab> function b=factorial(a) b=1; for i=1:a b=b*i; end</lang>

MAXScript

Iterative

<lang maxscript>fn factorial n = (

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

)</lang>

Recursive

<lang maxscript>fn factorial_rec n = (

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

)</lang>

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>

MUMPS

Iterative

<lang MUMPS> 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</lang>

Recursive

<lang MUMPS>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</lang>

Nial

(from Nial help file) <lang nial>fact is recur [ 0 =, 1 first, pass, product, -1 +]</lang> Using it <lang nial>|fact 4 =24</lang>

Niue

Recursive

<lang Niue>[ dup 1 > [ dup 1 - factorial * ] when ] 'factorial ;

( test ) 4 factorial . ( => 24 ) 10 factorial . ( => 3628800 ) </lang>

Objeck

Iterative

<lang objeck> bundle Default {

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

} </lang>

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)

Oz

Folding

<lang oz>fun {Fac1 N}

  {FoldL {List.number 1 N 1} Number.'*' 1}

end</lang>

Tail recursive

<lang oz>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</lang>

Iterative

<lang oz>fun {Fac3 N}

  Result = {NewCell 1}

in

  for I in 1..N do
     Result := @Result * I
  end
  @Result

end</lang>

PARI/GP

Built-in function, uses binary splitting. <lang>n!</lang>

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

Works with: Rakudo version #22 "Thousand Oaks"

<lang perl6>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>

One-Liner

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

 return $n == 0 ? 1 : array_product(range(1, $n));

} ?></lang>

Library

Requires the GMP library to be compiled in: <lang php>gmp_fact($n)</lang>

PicoLisp

<lang PicoLisp>(de fact (N)

  (if (=0 N)
     1
     (* N (fact (dec N))) ) )</lang>

or: <lang PicoLisp>(de fact (N)

  (apply * (range 1 N) )</lang>

Piet

Codel width: 25

This is the text code. It is a bit difficult to write as there are some loops and loops doesn't really show well when I write it down as there is no way to explicitly write a loop in the language. I have tried to comment as best to show how it works <lang>push 1 not in(number) duplicate not // label a pointer // pointer 1 duplicate push 1 subtract push 1 pointer push 1 noop pointer duplicate // the next op is back at label a

push 1 // this part continues from pointer 1 noop push 2 // label b push 1 rot 1 2 duplicate not pointer // pointer 2 multiply push 3 pointer push 3 pointer push 3 push 3 pointer pointer // back at label b

pop // continues from pointer 2 out(number) exit</lang>

PL/I

<lang 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; </lang>

Prolog

Works with: SWI Prolog

PostScript

Recursive

<lang postscript>/factorial{ /num exch def num 0 eq {1} {num num 1 sub factorial mul} ifelse }def

5 factorial = </lang>

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>

Pure

Recursive

<lang pure>fact n = n*fact (n-1) if n>0;

      = 1 otherwise;

let facts = map fact (1..10); facts;</lang>

Tail Recursive

<lang pure>fact n = loop 1 n with

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

end;</lang>

PureBasic

Iterative

<lang PureBasic>Procedure factorial(n)

 Protected i, f = 1
 For i = 2 To n
   f = f * i
 Next
 ProcedureReturn f

EndProcedure</lang>

Recursive

<lang PureBasic>Procedure Factorial(n)

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

EndProcedure</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:

<lang python>>>> 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>

Q

Iterative

Point-free

As a function

Recursive

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>

REBOL

<lang 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]]</lang>

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

REXX

<lang REXX> /REXX program computes the factorial of argument. The program */ /* automatically adjusts the number of digits for large products.*/

numeric digits 100 /*start with 100 digits. */ parse arg x /*get the argument. */ if x= then call er 'no argument specified' if arg()>1 |,

  words(x)>1       then call er 'too many arguments specified.'

if \datatype(x,'N') then call er 'argument' x "must be numeric" if \datatype(x,'W') then call er 'argument' x "must be a whole number" if x<0 then call er 'argument' x "must not be negative"

!=1 /*define factorial produce so far.*/

 do j=2 to x                     /*compute factorial the hard way. */
 !=!*j                           /*multiple the factorial with J.  */
 if pos('E',!)==0 then iterate   /*is ! in exponential notation?   */
 parse var ! 'E' digs            /*pick off the factorial exponent.*/
 numeric digits digs+digs%10     /*  and incease it by ten percent.*/
 end

say x'! is ('length(!) "digits):" say !/1 /*normalize the factorial product.*/ exit

er: say; say '*** error! ***'; say arg(1); say; exit 13 </lang> Output:

(sample DOS prompt)

C:\►fact 1000
1000! is (2568 digits):
40238726007709377354370243392300398571937486421071463254379991042993851239862902
05920442084869694048004799886101971960586316668729948085589013238296699445909974
24504087073759918823627727188732519779505950995276120874975462497043601418278094
64649629105639388743788648733711918104582578364784997701247663288983595573543251
31853239584630755574091142624174743493475534286465766116677973966688202912073791
43853719588249808126867838374559731746136085379534524221586593201928090878297308
43139284440328123155861103697680135730421616874760967587134831202547858932076716
91324484262361314125087802080002616831510273418279777047846358681701643650241536
91398281264810213092761244896359928705114964975419909342221566832572080821333186
11681155361583654698404670897560290095053761647584772842188967964624494516076535
34081989013854424879849599533191017233555566021394503997362807501378376153071277
61926849034352625200015888535147331611702103968175921510907788019393178114194545
25722386554146106289218796022383897147608850627686296714667469756291123408243920
81601537808898939645182632436716167621791689097799119037540312746222899880051954
44414282012187361745992642956581746628302955570299024324153181617210465832036786
90611726015878352075151628422554026517048330422614397428693306169089796848259012
54583271682264580665267699586526822728070757813918581788896522081643483448259932
66043367660176999612831860788386150279465955131156552036093988180612138558600301
43569452722420634463179746059468257310379008402443243846565724501440282188525247
09351906209290231364932734975655139587205596542287497740114133469627154228458623
77387538230483865688976461927383814900140767310446640259899490222221765904339901
88601856652648506179970235619389701786004081188972991831102117122984590164192106
88843871218556461249607987229085192968193723886426148396573822911231250241866493
53143970137428531926649875337218940694281434118520158014123344828015051399694290
15348307764456909907315243327828826986460278986432113908350621709500259738986355
42771967428222487575867657523442202075736305694988250879689281627538488633969099
59826280956121450994871701244516461260379029309120889086942028510640182154399457
15680594187274899809425474217358240106367740459574178516082923013535808184009699
63725242305608559037006242712434169090041536901059339838357779394109700277534720
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000

C:\►

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)

Sather

<lang 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;</lang>

Scala

Imperative

<lang scala>def factorial(n: Int)={

 var res = 1
 if(n > 0)
   for(i <- 1 to n)
     res *=i 
 res

} </lang>

Recursive

<lang scala>def factorial(n: Int): Int ={

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

} </lang>

Folding

<lang scala>def factorial(n: Int) = (2 to n).foldLeft(1)(_*_) </lang>

Using Pimp My Library

<lang scala>// Scala's extension-method syntax is a bit verbose, // but it is often worth it. // It is called the Pimp My Library pattern

object Factorials {

 // Implicit conversions may not be declared in top scope
 // because they often wreak havoc on other code.
 implicit def int2fac(i : Int) = new {
   def ! = if (i <= 1) 1
           else i * ((i - 1) !)
 }

} // example use import Factorials._

for(n <- 1 to 20) println(n !) </lang>

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>

Folding

<lang scheme>;Using a generator and a function that apply generated values to a function taking two arguments

A generator knows commands 'next? and 'next

(define (range a b) (let ((k a)) (lambda (msg) (cond ((eq? msg 'next?) (<= k b)) ((eq? msg 'next) (cond ((<= k b) (set! k (+ k 1)) (- k 1)) (else 'nothing-left)))))))

Similar to List.fold_left in OCaml, but uses a generator

(define (fold fun a gen) (let aux ((a a)) (if (gen 'next?) (aux (fun a (gen 'next))) a)))

Now the factorial function

(define (factorial n) (fold * 1 (range 1 n)))

(factorial 8)

40320</lang>

Sisal

Solution using a fold:

<lang sisal>define main

function main(x : integer returns integer)

 for a in 1, x
   returns
     value of product a
 end for

end function</lang>

Simple example using a recursive function:

<lang sisal>define main

function main(x : integer returns integer)

 if x = 0 then
   1
 else
   x * main(x - 1)
 end if

end function</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>

SNOBOL4

Works with: Macro Spitbol

Works with: CSnobol

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

Recursive

<lang SNOBOL4> define('rfact(n)') :(rfact_end) rfact rfact = le(n,0) 1 :s(return)

       rfact = n * rfact(n - 1) :(return)

rfact_end</lang>

Tail-recursive

<lang SNOBOL4> define('trfact(n,f)') :(trfact_end) trfact trfact = le(n,0) f :s(return)

       trfact = trfact(n - 1, n * f) :(return)

trfact_end</lang>

Iterative

<lang SNOBOL4> define('ifact(n)') :(ifact_end) ifact ifact = 1 if1 ifact = gt(n,0) n * ifact :f(return)

       n = n - 1 :(if1)

ifact_end</lang>

Test and display factorials 0 .. 10

<lang SNOBOL4>loop i = le(i,10) i + 1 :f(end)

       output = rfact(i) ' ' trfact(i,1) ' ' ifact(i) :(loop)

end</lang>

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

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.

<lang ti89b>factorial(x) Func

 Return Π(y,y,1,x)

EndFunc</lang>

Π 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

<lang bash>fact () {

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

}</lang>

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>

VBScript

Optimized with memoization, works for numbers up to 170 (because of the limitations on Doubles), exits if -1 is input <lang VBScript>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 </lang>

Wrapl

Product

Recursive

Folding

x86 Assembly

Works with: nasm

Iterative

<lang asm>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</lang>

Recursive

<lang asm>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</lang>

Tail Recursive

<lang asm>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</lang>