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. Support for trapping negative n errors is optional.

0815

This is an iterative solution which outputs the factorial of each number supplied on standard input.

<lang 0815>}:r: Start reader loop.

 |~  	    Read n,  
 #:end:    if n is 0 terminates
 >=        enqueue it as the initial product, reposition.
 }:f:      Start factorial loop.
   x<:1:x- Decrement n.
   {=*>    Dequeue product, position n, multiply, update product.
 ^:f:
 {+%       Dequeue incidental 0, add to get Y into Z, output fac(n).
 <:a:~$    Output a newline.

^:r:</lang>

Output:

seq 6 | 0815 fac.0
1
2
6
18
78
2d0

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

Aime

Iterative

<lang aime>integer factorial(integer n) {

   integer i, result;

   result = 1;
   i = 1;
   while (i < n) {
       i += 1;
       result *= i;
   }

   return result;

}</lang>

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

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>

Applesoft BASIC

Iterative

<lang ApplesoftBasic>100 N = 4 : GOSUB 200"FACTORIAL 110 PRINT N 120 END

200 N = INT(N) 210 IF N > 1 THEN FOR I = N - 1 TO 2 STEP -1 : N = N * I : NEXT I 220 RETURN</lang>

Recursive

<lang ApplesoftBasic> 10 A = 768:L = 7

20  DATA 165,157,240,3
30  DATA 32,149,217,96
40  FOR I = A TO A + L
50  READ B: POKE I,B: NEXT 
60 H = 256: POKE 12,A / H
70  POKE 11,A -  PEEK (12) * H
80  DEF  FN FA(N) =  USR (N < 2) + N *  FN FA(N - 1)
90  PRINT  FN FA(4)</lang>http://hoop-la.ca/apple2/2013/usr-if-recursive-fn/

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>

Babel

<lang babel>main:

   { argv 0 th $d
   fac 
   %d cr << }

fac!:

   { dup zero? 
       { dup one? 
           { cp 1 - fac * }
           { zap 1 }
       if }
       { zap 1 }
   if }

one?! : { 1 = } zero?!: { 0 = }</lang>

BASIC

Iterative

Works with: QBasic

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: QBasic

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>

BASIC256

Iterative

<lang BASIC256>print "enter a number, n = "; input n print string(n) + "! = " + string(factorial(n))

function factorial(n)

  factorial = 1
  if n > 0 then
     for p = 1 to n
     factorial *= p
     next p
  end if

end function</lang>

Recursive

<lang BASIC256>print "enter a number, n = "; input n print string(n) + "! = " + string(factorial(n))

function factorial(n)

  if n > 0 then
     factorial = n * factorial(n-1)
  else
     factorial = 1
  end if

end function</lang>

Batch File

<lang dos>@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</lang>

BBC BASIC

Works with: BBC BASIC for Windows

18! is the largest that doesn't overflow. <lang bbcbasic> *FLOAT64

     @% = &1010
     
     PRINT FNfactorial(18)
     END
     
     DEF FNfactorial(n)
     IF n <= 1 THEN = 1 ELSE = n * FNfactorial(n-1)</lang>

Output:

6402373705728000

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>

Bracmat

Compute 10! and checking that it is 3628800, the esoteric way <lang bracmat> (

     =   
       .   !arg:0&1
         |   !arg
           *   ( ( 
                 =   r
                   .   !arg:?r
                     &   
                       ' ( 
                         .   !arg:0&1
                           | !arg*(($r)$($r))$(!arg+-1)
                         )
                 )
               $ ( 
                 =   r
                   .   !arg:?r
                     &   
                       ' ( 
                         .   !arg:0&1
                           | !arg*(($r)$($r))$(!arg+-1)
                         )
                 )
               )
             $ (!arg+-1)
     )
   $ 10
 : 3628800

</lang>

This recursive lambda function is made in the following way (see http://en.wikipedia.org/wiki/Lambda_calculus):

Recursive lambda function for computing factorial.

   g := λr. λn.(1, if n = 0; else n × (r r (n-1)))
   f := g g

or, translated to Bracmat, and computing 10!

<lang bracmat> ( (=(r.!arg:?r&'(.!arg:0&1|!arg*(($r)$($r))$(!arg+-1)))):?g

   & (!g$!g):?f
   & !f$10
   )</lang>

The following is a straightforward recursive solution. Stack overflow occurs at some point, above 4243! in my case (Win XP).

  factorial=.!arg:~>1|!arg*factorial$(!arg+-1)

  factorial$4243
  (13552 digits, 2.62 seconds) 52254301882898638594700346296120213182765268536522926.....0000000

Lastly, here is an iterative solution

<lang bracmat>(factorial=

. !arg:?r

 &   whl
   ' (!arg:>1&(!arg+-1:?arg)*!r:?r)
 & !r

);</lang>

   factorial$5000
   (16326 digits) 422857792660554352220106420023358440539078667462664674884978240218135805270810820069089904787170638753708474665730068544587848606668381273 ... 000000

Brainf***

Prints sequential factorials in an infinite loop. <lang brainf***>>++++++++++>>>+>+[>>>+[-[<<<<<[+<<<<<]>>[[-]>[<<+>+>-]<[>+<-]<[>+<-[>+<-[> +<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>>>>+>+<<<<<<-[>+<-]]]]]]]]]]]>[<+>- ]+>>>>>]<<<<<[<<<<<]>>>>>>>[>>>>>]++[-<<<<<]>>>>>>-]+>>>>>]<[>++<-]<<<<[<[ >+<-]<<<<]>>[->[-]++++++[<++++++++>-]>>>>]<<<<<[<[>+>+<<-]>.<<<<<]>.>>>>]</lang>

Brat

<lang brat>factorial = { x |

 true? x == 0 1 { x * factorial(x - 1)}

}</lang>

Burlesque

Using the builtin Factorial function:

Burlesque does not have functions nor is it iterative. Burlesque's strength are its implicit loops.

Following examples display other ways to calculate the factorial function:

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

   return n == 0 ? 1 : n * factorial(n - 1);

}</lang>

Tail Recursive

Safe with some compilers (for example: GCC with -O2, LLVM's clang) <lang c>int fac_aux(int n, int acc) {

   return n < 1 ? acc : 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>

Template

<lang cpp>template <int N> struct Factorial {

   enum { value = N * Factorial<N - 1>::value };

};

template <> struct Factorial<0> {

   enum { value = 1 };

};

// Factorial<4>::value == 24 // Factorial<0>::value == 1 void foo() {

   int x = Factorial<4>::value; // == 24
   int y = Factorial<0>::value; // == 1

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

Cat

Taken direct from the Cat manual: <lang Cat>define rec_fac

     { dup 1 <= [pop 1] [dec rec_fac *] if }</lang>

Chapel

<lang chapel>proc fac(n) { var r = 1; for i in 1..n do r *= i;

return r; }</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>

Clay

Obviously there’s more than one way to skin a cat. Here’s a selection — recursive, iterative, and “functional” solutions. <lang Clay>factorialRec(n) {

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

}

factorialIter(n) {

   for (i in range(1, n))
       n *= i;
   return n;

}

factorialFold(n) {

   return reduce(multiply, 1, range(1, n + 1));

}</lang>

We could also do it at compile time, because — hey — why not?

<lang Clay>[n|n > 0] factorialStatic(static n) = n * factorialStatic(static n - 1); overload factorialStatic(static 0) = 1;</lang>

Because a literal 1 has type Int32, these functions receive and return numbers of that type. We must be a bit more careful if we wish to permit other numeric types (e.g. for larger integers).

<lang Clay>[N|Integer?(N)] factorial(n: N) {

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

}</lang>

And testing:

<lang Clay>main() {

   println(factorialRec(5));           // 120
   println(factorialIter(5));          // 120
   println(factorialFold(5));          // 120
   println(factorialStatic(static 5)); // 120
   println(factorial(Int64(20)));      // 2432902008176640000

}</lang>

CLIPS

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

Clojure

Folding

<lang lisp>(defn factorial [x]

 (apply * (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>

CMake

<lang cmake>function(factorial var n)

 set(product 1)
 foreach(i RANGE 2 ${n})
   math(EXPR product "${product} * ${i}")
 endforeach(i)
 set(${var} ${product} PARENT_SCOPE)

endfunction(factorial)

factorial(f 12) message("12! = ${f}")</lang>

COBOL

The following functions have no need to check if their parameters are negative because they are unsigned.

Intrinsic Function

COBOL includes an intrinsic function which returns the factorial of its argument. <lang cobol>MOVE FUNCTION FACTORIAL(num) TO result</lang>

Iterative

<lang cobol> IDENTIFICATION DIVISION.

      FUNCTION-ID. factorial.
      
      DATA DIVISION.
      LOCAL-STORAGE SECTION.
      01  i      PIC 9(10).
      
      LINKAGE SECTION.
      01  n      PIC 9(10).
      01  ret    PIC 9(10).
      
      PROCEDURE DIVISION USING BY VALUE n RETURNING ret.
          MOVE 1 TO ret
          
          PERFORM VARYING i FROM 2 BY 1 UNTIL n < i
              MULTIPLY i BY ret
          END-PERFORM
      
          GOBACK
          .</lang>

Recursive

Works with: Visual COBOL

<lang cobol> IDENTIFICATION DIVISION.

      FUNCTION-ID. factorial.
      
      DATA DIVISION.
      LOCAL-STORAGE SECTION.
      01  prev-n PIC 9(10).
      
      LINKAGE SECTION.
      01  n      PIC 9(10).
      01  ret    PIC 9(10).
      
      PROCEDURE DIVISION USING BY VALUE n RETURNING ret.
          IF n = 0
              MOVE 1 TO ret
          ELSE
              SUBTRACT 1 FROM n GIVING prev-n
              MULTIPLY n BY fac(prev-n) GIVING ret
          END-IF
      
          GOBACK
          .</lang>

CoffeeScript

Several solutions are possible in JavaScript:

Recursive

 if n <= 1
   1
 else
   n * fac n-1</lang>

Functional

Works with: JavaScript version 1.8

(See MDC)

 [1..n].reduce (x,y) -> x*y</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>

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

   (reduce #'* (loop for i from 1 to n collect i)))</lang>

D

<lang d>import std.stdio, std.algorithm, std.range;

/// Iterative. int factorial(in int n) {

   int result = 1;
   foreach (i; 1 .. n + 1)
       result *= i;
   return result;

}

/// Recursive. int recFactorial(in int n) {

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

}

/// Functional-style. int fact(in int n) {

   return iota(1, n + 1).reduce!q{a * b};

}

/// Tail recursive (at run-time, with DMD). int tfactorial(in 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, 15.factorial); pragma(msg, 15.recFactorial); pragma(msg, 15.fact); pragma(msg, 15.tfactorial);

void main() {

   // Computed and printed at run-time.
   15.factorial.writeln;
   15.recFactorial.writeln;
   15.fact.writeln;
   15.tfactorial.writeln;

}</lang>

Output:

1307674368000
1307674368000
1307674368000
1307674368000
1307674368000
1307674368000
1307674368000
1307674368000

Dart

Recursive

<lang dart>int fact(int n) {

 if(n<0) {
   throw new IllegalArgumentException('Argument less than 0');
 }
 return n==0 ? 1 : n*fact(n-1);

}

main() {

 print(fact(10));
 print(fact(-1));

}</lang>

Iterative

<lang dart>int fact(int n) {

 if(n<0) {
   throw new IllegalArgumentException('Argument less than 0');
 }
 int res=1;
 for(int i=1;i<=n;i++) {
   res*=i;
 }
 return res;

}

main() {

 print(fact(10));
 print(fact(-1));

}</lang>

dc

This factorial uses tail recursion to iterate from n down to 2. Some implementations, like OpenBSD dc, optimize the tail recursion so the call stack never overflows, though n might be large. <lang dc>[*

* (n) lfx -- (factorial of n)
*]sz

[

1 Sp           [product = 1]sz
[              [Loop while 1 < n:]sz
 d lp * sp      [product = n * product]sz
 1 -            [n = n - 1]sz
 d 1 <f
]Sf d 1 <f
Lfsz           [Drop loop.]sz
sz             [Drop n.]sz
Lp             [Push product.]sz

]sf

[*

* For example, print the factorial of 50.
*]sz

50 lfx psz</lang>

Delphi

Iterative

<lang Delphi>program Factorial1;

{$APPTYPE CONSOLE}

function FactorialIterative(aNumber: Integer): Int64; var

 i: Integer;

begin

 Result := 1;
 for i := 1 to aNumber do
   Result := i * Result;

end;

begin

 Writeln('5! = ', FactorialIterative(5));

end.</lang>

Recursive

<lang Delphi>program Factorial2;

{$APPTYPE CONSOLE}

function FactorialRecursive(aNumber: Integer): Int64; begin

 if aNumber < 1 then
   Result := 1
 else
   Result := aNumber * FactorialRecursive(aNumber - 1);

end;

begin

 Writeln('5! = ', FactorialRecursive(5));

end.</lang>

Tail Recursive

<lang Delphi>program Factorial3;

{$APPTYPE CONSOLE}

function FactorialTailRecursive(aNumber: Integer): Int64;

 function FactorialHelper(aNumber: Integer; aAccumulator: Int64): Int64;
 begin
   if aNumber = 0 then
     Result := aAccumulator
   else
     Result := FactorialHelper(aNumber - 1, aNumber * aAccumulator);
   end;

begin

 if aNumber < 1 then
   Result := 1
 else
   Result := FactorialHelper(aNumber, 1);

end;

begin

 Writeln('5! = ', FactorialTailRecursive(5));

end.</lang>

Déjà Vu

Iterative

<lang dejavu>factorial:

   1
   while over:
       * over
       swap -- swap
   drop swap</lang>

Recursive

<lang dejavu>factorial:

   if dup:
       * factorial -- dup
   else:
       1 drop</lang>

DWScript

Note that Factorial is part of the standard DWScript maths functions.

Iterative

<lang delphi>function IterativeFactorial(n : Integer) : Integer; var

  i : Integer;

begin

  Result := 1;
  for i := 2 to n do
     Result *= i;

end;</lang>

Recursive

<lang delphi>function RecursiveFactorial(n : Integer) : Integer; begin

  if n>1 then
     Result := RecursiveFactorial(n-1)*n
  else Result := 1;

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

Eiffel

<lang Eiffel> note description: "recursive and iterative factorial example of a positive integer."

class FACTORIAL_EXAMPLE

create make

feature -- Initialization

make local n: NATURAL do n := 5 print ("%NFactorial of " + n.out + " = ") print (recursive_factorial (n)) end

feature -- Access

recursive_factorial (n: NATURAL): NATURAL -- factorial of 'n' do if n = 0 then Result := 1 else Result := n * recursive_factorial (n - 1) end end

iterative_factorial (n: NATURAL): NATURAL -- factorial of 'n' local v: like n do from Result := 1 v := n until v <= 1 loop Result := Result * v v := v - 1 end end

end </lang>

Ela

Tail recursive version:

<lang Ela>fact = fact' 1L

      where fact' acc 0 = acc                  
            fact' acc n = fact' (n * acc) (n - 1)</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>

The calc package (which comes with Emacs) has a builtin fact(). It automatically uses the bignums implemented by calc.

<lang lisp>(require 'calc) (calc-eval "fact(30)") => "265252859812191058636308480000000"</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>

Euphoria

Straight forward methods

Iterative

<lang Euphoria>function factorial(integer n)

 atom f = 1
 while n > 1 do
   f *= n
   n -= 1
 end while

 return f

end function</lang>

Recursive

<lang Euphoria>function factorial(integer n)

 if n > 1 then
   return factorial(n-1) * n
 else
   return 1
 end if

end function</lang>

Tail Recursive

Works with: Euphoria version 4.0.0

<lang Euphoria>function factorial(integer n, integer acc = 1)

 if n <= 0 then
   return acc
 else
   return factorial(n-1, n*acc)
 end if

end function</lang>

'Paper tape' / Virtual Machine version

Works with: Euphoria version 4.0.0

Another 'Paper tape' / Virtual Machine version, with as much as possible happening in the tape itself. Some command line handling as well.

<lang Euphoria>include std/mathcons.e

enum MUL_LLL, TESTEQ_LIL, TESTLT_LIL, TRUEGO_LL, MOVE_LL, INCR_L, TESTGT_LLL, GOTO_L, OUT_LI, OUT_II, STOP

global sequence tape = { 1, 1, 0, 0, 0, {TESTLT_LIL, 5, 0, 4}, {TRUEGO_LL, 4, 22}, {TESTEQ_LIL, 5, 0, 4}, {TRUEGO_LL, 4, 20}, {MUL_LLL, 1, 2, 3}, {TESTEQ_LIL, 3, PINF, 4}, {TRUEGO_LL, 4, 18}, {MOVE_LL, 3, 1}, {INCR_L, 2}, {TESTGT_LLL, 2, 5, 4 }, {TRUEGO_LL, 4, 18}, {GOTO_L, 10}, {OUT_LI, 3, "%.0f\n"}, {STOP}, {OUT_II, 1, "%.0f\n"}, {STOP}, {OUT_II, "Negative argument", "%s\n"}, {STOP} }

global integer ip = 1

procedure eval( sequence cmd ) atom i = 1 while i <= length( cmd ) do switch cmd[ i ] do case MUL_LLL then -- multiply location location giving location tape[ cmd[ i + 3 ] ] = tape[ cmd[ i + 1 ] ] * tape[ cmd[ i + 2 ] ] i += 3 case TESTEQ_LIL then -- test if location eq value giving location tape[ cmd[ i + 3 ]] = ( tape[ cmd[ i + 1 ] ] = cmd[ i + 2 ] ) i += 3 case TESTLT_LIL then -- test if location eq value giving location tape[ cmd[ i + 3 ]] = ( tape[ cmd[ i + 1 ] ] < cmd[ i + 2 ] ) i += 3 case TRUEGO_LL then -- if true in location, goto location if tape[ cmd[ i + 1 ] ] then ip = cmd[ i + 2 ] - 1 end if i += 2 case MOVE_LL then -- move value at location to location tape[ cmd[ i + 2 ] ] = tape[ cmd[ i + 1 ] ] i += 2 case INCR_L then -- increment value at location tape[ cmd[ i + 1 ] ] += 1 i += 1 case TESTGT_LLL then -- test if location gt location giving location tape[ cmd[ i + 3 ]] = ( tape[ cmd[ i + 1 ] ] > tape[ cmd[ i + 2 ] ] ) i += 3 case GOTO_L then -- goto location ip = cmd[ i + 1 ] - 1 i += 1 case OUT_LI then -- output location using format printf( 1, cmd[ i + 2], tape[ cmd[ i + 1 ] ] ) i += 2 case OUT_II then -- output immediate using format if sequence( cmd[ i + 1 ] ) then printf( 1, cmd[ i + 2], { cmd[ i + 1 ] } ) else printf( 1, cmd[ i + 2], cmd[ i + 1 ] ) end if i += 2 case STOP then -- stop abort(0) end switch i += 1 end while end procedure

include std/convert.e

sequence cmd = command_line() if length( cmd ) > 2 then puts( 1, cmd[ 3 ] & "! = " ) tape[ 5 ] = to_number(cmd[3]) else puts( 1, "eui fact.ex <number>\n" ) abort(1) end if

while 1 do if sequence( tape[ ip ] ) then eval( tape[ ip ] ) end if ip += 1 end while</lang>

EGL

Iterative

<lang EGL> function fact(n int in) returns (bigint)

   if (n < 0)
       writestdout("No negative numbers");
       return (0);
   end
   ans bigint = 1;
   for (i int from 1 to n)
       ans *= i;
   end
   return (ans);

end </lang>

Recursive

<lang EGL> function fact(n int in) returns (bigint)

   if (n < 0)
       SysLib.writeStdout("No negative numbers");
       return (0);
   end
   if (n < 2)
   	return (1);
   else 
   	return (n * fact(n - 1));
   end

end </lang>

Ezhil

Recursive <lang src="Python"> நிரல்பாகம் fact ( n )

 @( n == 0 ) ஆனால்
           பின்கொடு  1
    இல்லை
           பின்கொடு    n*fact( n - 1 )
   முடி

முடி

பதிப்பி fact ( 10 ) </lang>

F#

<lang fsharp>//val inline factorial : // ^a -> ^a // when ^a : (static member get_One : -> ^a) and // ^a : (static member ( + ) : ^a * ^a -> ^a) and // ^a : (static member ( * ) : ^a * ^a -> ^a) let inline factorial n = Seq.reduce (*) [ LanguagePrimitives.GenericOne .. n ]</lang>

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

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>

Fantom

The following uses 'Ints' to hold the computed factorials, which limits results to a 64-bit signed integer. <lang fantom>class Main {

 static Int factorialRecursive (Int n)
 {
   if (n <= 1)
     return 1
   else
     return n * (factorialRecursive (n - 1))
 }

 static Int factorialIterative (Int n)
 {
   Int product := 1
   for (Int i := 2; i <=n ; ++i)
   {
     product *= i
   }
   return product
 }

 static Int factorialFunctional (Int n)
 {
   (1..n).toList.reduce(1) |a,v| 
   { 
     v->mult(a) // use a dynamic invoke
     // alternatively, cast a:  v * (Int)a
   }
 }

 public static Void main ()
 {
   echo (factorialRecursive(20))
   echo (factorialIterative(20))
   echo (factorialFunctional(20))
 }

}</lang>

Forth

Fortran

Fortran 90

A simple one-liner is sufficient <lang fortran>nfactorial = PRODUCT((/(i, i=1,n)/))</lang>

FORTRAN 77

<lang fortran> FUNCTION FACT(N)

    INTEGER N,I,FACT
    FACT=1
    DO 10 I=1,N
 10 FACT=FACT*I
    END</lang>

FPr

FP-Way <lang fpr>fact==((1&),iota)\(1*2)& </lang> Recursive <lang fpr>fact==(id<=1&)->(1&);id*fact°id-1& </lang>

Frink

Frink has a built-in factorial operator that creates arbitrarily-large numbers and caches results. <lang frink> factorial[x] := x! </lang> If you want to roll your own, you could do: <lang frink> factorial2[x] := product[1 to x] </lang>

GAP

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

An implementation

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

Genyris

<lang genyris>def factorial (n)

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

GML

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

   j *= i

return j</lang>

gnuplot

Gnuplot has a builtin ! factorial operator for use on integers. <lang gnuplot>set xrange [0:4.95] set key left plot int(x)!</lang>

If you wanted to write your own it can be done recursively.

<lang gnuplot># Using int(n) allows non-integer "n" inputs with the factorial

calculated on int(n) in that case.
Arranging the condition as "n>=2" avoids infinite recursion if
n==NaN, since any comparison involving NaN is false. Could change
"1" to an expression like "n*0+1" to propagate a NaN input to the
output too, if desired.

factorial(n) = (n >= 2 ? int(n)*factorial(n-1) : 1) set xrange [0:4.95] set key left plot factorial(x)</lang>

Golfscript

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

Go

Iterative, sequential, but at least handling big numbers: <lang go>package main

import (

   "fmt"
   "math/big"

)

func main() {

   fmt.Println(factorial(800))

}

func factorial(n int64) *big.Int {

   if n < 0 {
       return nil
   }
   r := big.NewInt(1)
   var f big.Int
   for i := int64(2); i <= n; i++ {
       r.Mul(r, f.SetInt64(i))
   }
   return r

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

import (

   "math/big"
   "fmt"

)

func factorial(n int64) *big.Int {

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

}

func main() {

   fmt.Println(factorial(800))

}</lang> For a bigger step up, an algorithm fast enough to compute factorials of numbers up to a million or so, see Factorial/Go.

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> See also: The Evolution of a Haskell Programmer

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>

Tail-recursive, checking the negative case: <lang haskell>fac n

   | n >= 0    = go 1 n
   | otherwise = error "Negative factorial!"
       where go acc 0 = acc
             go acc n = go (acc * n) (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>

Icon and 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>

IDL

<lang idl>function fact,n

  return, product(lindgen(n)+1)

end</lang>

Inform 6

<lang inform6>[ factorial n;

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

];</lang>

Io

Facorials are built-in to Io: <lang io>3 factorial</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(final 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(final 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 range(n) {

 for (let i = 1; i <= n; i++)
   yield i;

}

function factorial(n) {

 return [i for (i in range(n))].reduce(function(a, b) a*b, 1);

}</lang>

Joy

<lang Joy>DEFINE factorial == [0 =] [pop 1] [dup 1 - factorial *] ifte. </lang>

Julia

The factorial is provided by the standard library. <lang julia>julia> help(factorial) Loading help data... Base.factorial(n)

  Factorial of n

Base.factorial(n, k)

  Compute "factorial(n)/factorial(k)"</lang>

Here is its definition from the combinatorics.jl module of the Julia standard library <lang julia> function factorial(n::Integer)

   if n < 0
       return zero(n)
   end
   f = one(n)
   for i = 2:n
       f *= i
   end
   return f

end</lang>

Output:

julia> for i = 10:20
	println(factorial(big(i)))
end
3628800
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
121645100408832000
2432902008176640000

Another way of writing the factorial function, with arithmetic performed in the precision of the argument.

K

Iterative

<lang K> facti:*/1+!:

 facti 5

120</lang>

Recursive

<lang K> factr:{:[x>1;x*_f x-1;1]}

 factr 6

720</lang>

KonsolScript

<lang KonsolScript>function factorial(Number n):Number {

 Var:Number ret;
 if (n >= 0) {
   ret = 1;
   Var:Number i = 1;
   for (i = 1; i <= n; i++) {
     ret = ret * i;
   }
 } else {
   ret = 0;
 }
 return ret;

}</lang>

Lang5

Folding

<lang lang5> : fact iota 1 + '* reduce ;

 5 fact

120 </lang>

Recursive

 : fact dup 2 < if else dup 1 - fact * then ;
 5 fact

120 </lang>

Lasso

Iterative

<lang lasso>define factorial(n) => {

 local(x = 1)
 with i in generateSeries(2, #n)
 do {
   #x *= #i
 }
 return #x

}</lang>

Recursive

<lang lasso>define factorial(n) => #n < 2 ? 1 | #n * factorial(#n - 1)</lang>

LFE

<lang lisp>(defun fac (n)

 (cond
   ((== n 0) 1)
   ((> n 0) (* n (fac (- n 1))))))

</lang>

Liberty BASIC

<lang lb> for i =0 to 40

       print " FactorialI( "; using( "####", i); ") = "; factorialI( i)
       print " FactorialR( "; using( "####", i); ") = "; factorialR( i)
   next i

   wait

   function factorialI( n)
       if n >1 then
           f =1
           For i = 2 To n
               f = f * i
           Next i
       else
           f =1
       end if
   factorialI =f
   end function

   function factorialR( n)
       if n <2 then
           f =1
       else
           f =n *factorialR( n -1)
       end if
   factorialR =f
   end function

   end</lang>

Lisaac

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

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

);</lang>

Logo

Recursive

<lang logo>to factorial :n

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

end</lang>

Iterative

NOTE: Slight code modifications may needed in order to run this as each Logo implementation differs in various ways.

<lang logo>to factorial :n make "fact 1 make "i 1 repeat :n [make "fact :fact * :i make "i :i + 1] print :fact 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:

Maple

Builtin <lang Maple> > 5!;

</lang> Recursive <lang Maple>RecFact := proc( n :: nonnegint )

       if n = 0 or n = 1 then
               1
       else
               n * thisproc( n -  1 )
       end if

end proc: </lang> <lang Maple> > seq( RecFact( i ) = i!, i = 0 .. 10 ); 1 = 1, 1 = 1, 2 = 2, 6 = 6, 24 = 24, 120 = 120, 720 = 720, 5040 = 5040,

   40320 = 40320, 362880 = 362880, 3628800 = 3628800

</lang> Iterative <lang Maple> IterFact := proc( n :: nonnegint )

       local   i;
       mul( i, i = 2 .. n )

end proc: </lang> <lang Maple> > seq( IterFact( i ) = i!, i = 0 .. 10 ); 1 = 1, 1 = 1, 2 = 2, 6 = 6, 24 = 24, 120 = 120, 720 = 720, 5040 = 5040,

   40320 = 40320, 362880 = 362880, 3628800 = 3628800

</lang>

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)

<lang mathematica>factorial[n_Integer] := Block[{i}, Times @@ Table[i, {i, n}]]</lang>

MATLAB

Built-in

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>

Recursive

<lang matlab>function f=fac(n)

   if n==0
       f=1;
       return
   else
       f=n*fac(n-1);
   end</lang>

Iterative

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

Maude

<lang Maude> fmod FACTORIAL is

protecting INT .

op undefined : -> Int . op _! : Int -> Int .

var n : Int .

eq 0 ! = 1 . eq n ! = if n < 0 then undefined else n * (sd(n, 1) !) fi .

endfm

red 11 ! . </lang>

Maxima

Built-in

Recursive

Iterative

<lang maxima>fact2(n) := block([r: 1], for i thru n do r: r * i, r)$</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>

Mirah

<lang mirah>def factorial_iterative(n:int)

   2.upto(n-1) do |i|
       n *= i 
   end
   n

end

puts factorial_iterative 10</lang>

МК-61/52

ВП	П0	1	ИП0	*	L0	03	С/П

ML/I

Iterative

<lang ML/I>MCSKIP "WITH" NL "" Factorial - iterative MCSKIP MT,<> MCINS %. MCDEF FACTORIAL WITHS () AS <MCSET T1=%A1. MCSET T2=1 MCSET T3=1 %L1.MCGO L2 IF T3 GR T1 MCSET T2=T2*T3 MCSET T3=T3+1 MCGO L1 %L2.%T2.> fact(1) is FACTORIAL(1) fact(2) is FACTORIAL(2) fact(3) is FACTORIAL(3) fact(4) is FACTORIAL(4)</lang>

Recursive

<lang ML/I>MCSKIP "WITH" NL "" Factorial - recursive MCSKIP MT,<> MCINS %. MCDEF FACTORIAL WITHS () AS <MCSET T1=%A1. MCGO L1 UNLESS T1 EN 0 1<>MCGO L0 %L1.%%T1.*FACTORIAL(%T1.-1).> fact(1) is FACTORIAL(1) fact(2) is FACTORIAL(2) fact(3) is FACTORIAL(3) fact(4) is FACTORIAL(4)</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>

Nemerle

Here's two functional programming ways to do this and an iterative example translated from the C# above. Using long, we can only use number <= 20, I just don't like the scientific notation output from using a double. Note that in the iterative example, variables whose values change are explicitly defined as mutable; the default in Nemerle is immutable values, encouraging a more functional approach. <lang Nemerle>using System; using System.Console;

module Program {

 Main() : void
 {
     WriteLine("Factorial of which number?");
     def number = long.Parse(ReadLine());
     WriteLine("Using Fold : Factorial of {0} is {1}", number, FactorialFold(number));
     WriteLine("Using Match: Factorial of {0} is {1}", number, FactorialMatch(number));
     WriteLine("Iterative  : Factorial of {0} is {1}", number, FactorialIter(number));
 }
 
 FactorialFold(number : long) : long
 {
     $[1L..number].FoldLeft(1L, _ * _ )
 }
 
 FactorialMatch(number : long) : long
 {
     |0L => 1L
     |n  => n * FactorialMatch(n - 1L)
 }
 
 FactorialIter(number : long) : long
 {
     mutable accumulator = 1L;
     for (mutable factor = 1L; factor <= number; factor++)
     {
         accumulator *= factor;
     }
     accumulator  //implicit return
 }

}</lang>

NetRexx

<lang NetRexx>/* NetRexx */

options replace format comments java crossref savelog symbols nobinary

numeric digits 64 -- switch to exponential format when numbers become larger than 64 digits

say 'Input a number: \-' say do

 n_ = long ask -- Gets the number, must be an integer

 say n_'! =' factorial(n_) '(using iteration)'
 say n_'! =' factorial(n_, 'r') '(using recursion)'

 catch ex = Exception
   ex.printStackTrace

end

return

method factorial(n_ = long, fmethod = 'I') public static returns Rexx signals IllegalArgumentException

 if n_ < 0 then -
   signal IllegalArgumentException('Sorry, but' n_ 'is not a positive integer')

 select
   when fmethod.upper = 'R' then -
     fact = factorialRecursive(n_)
   otherwise -
     fact = factorialIterative(n_)
   end

 return fact

method factorialIterative(n_ = long) private static returns Rexx

 fact = 1
 loop i_ = 1 to n_
   fact = fact * i_
   end i_

 return fact

method factorialRecursive(n_ = long) private static returns Rexx

 if n_ > 1 then -
   fact = n_ * factorialRecursive(n_ - 1)
 else -
  fact = 1

 return fact</lang>

Output

Input a number: 
49
49! = 608281864034267560872252163321295376887552831379210240000000000 (using iteration)
49! = 608281864034267560872252163321295376887552831379210240000000000 (using recursion)

newLISP

<lang newLISP>> (define (factorial n) (exp (gammaln (+ n 1)))) (lambda (n) (exp (gammaln (+ n 1)))) > (factorial 4) 24</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)

Suggested correction: Neither of the three (two) results above is exact. The exact result (computed with Haskell) should be:

30414093201713378043612608166064768844377641568960512000000000000

In fact, all results given by Octave are precise up to their 16th digit, the rest seems to be "random" in all cases. Apparently, this is a consequence of Octave not being capable of arbitrary precision operation.

Order

Simple recursion: <lang c>#include <order/interpreter.h>

define ORDER_PP_DEF_8fac \

ORDER_PP_FN(8fn(8N, \

               8if(8less_eq(8N, 0),          \
                   1,                        \
                   8mul(8N, 8fac(8dec(8N))))))

ORDER_PP(8to_lit(8fac(8))) // 40320</lang> Tail recursion: <lang c>#include <order/interpreter.h>

define ORDER_PP_DEF_8fac \

ORDER_PP_FN(8fn(8N, \

               8let((8F, 8fn(8I, 8A, 8G,                                                         \
                             8if(8greater(8I, 8N),                                               \
                                 8A,                                                             \
                                 8apply(8G, 8seq_to_tuple(8seq(8inc(8I), 8mul(8A, 8I), 8G)))))), \
                     8apply(8F, 8seq_to_tuple(8seq(1, 1, 8F))))))

ORDER_PP(8to_lit(8fac(8))) // 40320</lang>

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

All of these versions include bignum support. The recursive version is limited by the operating system's stack size; it may not be able to compute factorials larger than twenty thousand digits. The gamma function method is reliant on precision; to use it for large numbers increase default(realprecision) as needed.

Recursive

Iterative

This is an improvement on the naive recursion above, being faster and not limited by stack space. <lang parigp>fact(n)=my(p=1);for(k=2,n,p*=k);p</lang>

Binary splitting

PARI's prod automatically uses binary splitting, preventing subproducts from growing overly large. This function is dramatically faster than the above. <lang parigp>fact(n)=prod(k=2,n,k)</lang>

Recursive 1

Even faster <lang parigp>f( a, b )={ my(c); if( b == a, return(a)); if( b-a > 1, c=(b + a) >> 1; return(f(a, c) * f(c+1, b)) ); return( a * b ); }

fact(n) = f(1, n)</lang>

Built-in

Uses binary splitting. According to the source, this was found to be faster than prime decomposition methods. This is, of course, faster than the above. <lang parigp>fact(n)=n!</lang>

Gamma

Note also the presence of factorial and lngamma. <lang parigp>fact(n)=round(gamma(n+1))</lang>

Moessner's algorithm

Not practical, just amusing. Note the lack of * or ^. A variant of an algorithm presented in

Alfred Moessner, "Eine Bemerkung über die Potenzen der natürlichen Zahlen." S.-B. Math.-Nat. Kl. Bayer. Akad. Wiss. 29:3 (1952).

This is very slow but should be able to compute factorials until it runs out of memory (usage is about $n^{2}\log n$ bits to compute n!); a machine with 1 GB of RAM and unlimited time could, in theory, find 100,000-digit factorials. <lang parigp>fact(n)={

 my(v=vector(n+1,i,i==1));
 for(i=2,n+1,
   forstep(j=i,2,-1,
     for(k=2,j,v[k]+=v[k-1])
   )
 );
 v[n+1]

};</lang>

Pascal

Iterative

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

var
 i, result: integer;
begin
 result := 1;
 for i := 2 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

via User-defined Postfix Operator

[*] is a reduction operator that multiplies all the following values together. Note that we don't need to start at 1, since the degenerate case of [*]() correctly returns 1, and multiplying by 1 to start off with is silly in any case. <lang perl6>sub postfix:<!>($n) { [*] 2..$n } say 5!;</lang>

Output:

via Memoized Constant Sequence

This approach is much more efficient for repeated use, since it automatically caches. [\*] is a reduction operator that returns its intermediate results as a list. Note that Perl 6 allows you to define constants lazily, which is rather helpful when your constant is of infinite size... <lang perl6>constant fact = 1, [\*] 1..*; say fact[5]</lang>

Output:

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

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 pseudocode>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 pli>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>

PostScript

Recursive

<lang postscript>/fact {

 dup 0 eq     % check for the argument being 0
 {
   pop 1      % if so, the result is 1
 }
 {
   dup
   1 sub
   fact       % call recursively with n - 1
   mul        % multiply the result with n
 } ifelse

} def</lang>

Iterative

<lang postscript>/fact {

 1            % initial value for the product
 1 1          % for's start value and increment
 4 -1 roll    % bring the argument to the top as for's end value
 { mul } for

} def</lang>

Combinator

Library: initlib

<lang postscript>/myfact {{dup 0 eq} {pop 1} {dup pred} {mul} linrec}.</lang>

PowerBASIC

<lang powerbasic>function fact1#(n%) local i%,r# r#=1 for i%=1 to n% r#=r#*i% next fact1#=r# end function

function fact2#(n%) if n%<=2 then fact2#=n% else fact2#=fact2#(n%-1)*n% end function

for i%=1 to 20 print i%,fact1#(i%),fact2#(i%) next</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>

Prolog

Works with: SWI Prolog

Recursive

Tail recursive

<lang prolog>fact(N, NF) :- fact(1, N, 1, NF).

fact(X, X, F, F) :- !. fact(X, N, FX, F) :- FX1 is FX * X, X1 is X + 1, fact(X1, N, FX1, F).</lang>

Fold

We can simulate foldl. <lang prolog>% foldl(Pred, Init, List, R). % foldl(_Pred, Val, [], Val). foldl(Pred, Val, [H | T], Res) :- call(Pred, Val, H, Val1), foldl(Pred, Val1, T, Res).

% factorial p(X, Y, Z) :- Z is X * Y).

fact(X, F) :- numlist(2, X, L), foldl(p, 1, L, F).</lang>

Fold with anonymous function

Using the module lambda written by Ulrich Neumerkel found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl, we can use anonymous functions and write : <lang prolog>:- use_module(lambda).

% foldl(Pred, Init, List, R). % foldl(_Pred, Val, [], Val). foldl(Pred, Val, [H | T], Res) :- call(Pred, Val, H, Val1), foldl(Pred, Val1, T, Res).

fact(N, F) :- numlist(2, N, L), foldl(\X^Y^Z^(Z is X * Y), 1, L, F).</lang>

Continuation passing style

Works with SWI-Prolog and module lambda written by Ulrich Neumerkel found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl. <lang prolog>:- use_module(lambda).

fact(N, FN) :- cont_fact(N, FN, \X^Y^(Y = X)).

cont_fact(N, F, Pred) :- ( N = 0 -> call(Pred, 1, F) ; N1 is N - 1,

P = \Z^T^(T is Z * N), cont_fact(N1, FT, P), call(Pred, FT, F) ).</lang>

Protium

Protium has an opcode for factorial so there's not much point coding one. <lang html><@ SAYFCTLIT>5</@></lang> However, just to prove that it can be done, here's one possible implementation: <lang html><@ DEFUDOLITLIT>FAT|__Transformer|<@ LETSCPLIT>result|1</@><@ ITEFORPARLIT>1|<@ ACTMULSCPPOSFOR>result|...</@></@><@ LETRESSCP>...|result</@></@> <@ SAYFATLIT>123</@></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):

   result = 1
   for i in range(1, n+1):
       result *= i
   return result</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>

Racket

Recursive

The standard recursive style: <lang Racket>(define (factorial n)

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

However, it is inefficient. It's more efficient to use an accumulator.

<lang Racket>(define (factorial n)

 (define (fact n acc)
   (if (= 0 n) 
       acc
       (fact (- n 1) (* n acc))))
 (fact n 1))</lang>

Rapira

Iterative

<lang rapira>Фун Факт(n)

 f := 1
 для i от 1 до n
       f := f * i
 кц
 Возврат f

Кон Фун</lang>

Recursive

<lang rapira>Фун Факт(n)

 Если n = 1
   Возврат 1
 Иначе
   Возврат n * Факт(n - 1)
 Всё

Кон Фун

Проц Старт()

 n := ВводЦел('Введите число (n <= 12) :')
 печать 'n! = '
 печать Факт(n)

Кон проц </lang>

Rascal

Iterative

The standard implementation: <lang rascal>public int factorial_iter(int n){ result = 1; for(i <- [1..n]) result *= i; return result; }</lang> However, Rascal supports an even neater solution. By using a reducer we can write this code on one short line: <lang rascal>public int factorial_iter2(int n) = (1 | it*e | int e <- [1..n]);</lang> Example outputs: <lang rascal>rascal>factorial_iter(10) int: 3628800

rascal>factorial_iter2(10) int: 3628800</lang>

Recursive

<lang rascal>public int factorial_rec(int n){ if(n>1) return n*factorial_rec(n-1); else return 1; }</lang> Example output: <lang rascal>rascal>factorial_rec(10) int: 3628800</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

See also more on memoization...

Retro

A recursive implementation from the benchmarking code. <lang Retro>: <factorial> dup 1 = if; dup 1- <factorial> * ;

factorial dup 0 = [ 1+ ] [ <factorial> ] if ;</lang>

REXX

simple version

This version of the REXX program calculates the factorial of numbers up to 25,000.

25,000! is exactly 99,094 digits.

Most REXX interpreters can handle eight million digits. <lang rexx>/*REXX program computes the factorial of a non-negative integer. */ numeric digits 100000 /*100k digs: handles N up to 25k.*/ parse arg n /*get argument from command line. */ if n= then call er 'no argument specified' if arg()>1 | words(n)>1 then call er 'too many arguments specified.' if \datatype(n,'N') then call er "argument isn't numeric: " n if \datatype(n,'W') then call er "argument isn't a whole number: " n if n<0 then call er "argument can't be negative: " n !=1 /*define factorial product so far.*/

/*══════════════════════════════════════where da rubber meets da road──┐*/

    do j=2 to n;    !=!*j            /*compute  the ! the hard way◄───┘*/
    end   /*j*/

/*══════════════════════════════════════════════════════════════════════*/

say n'! is ['length(!) "digits]:" /*display # of digits in factorial*/ say /*add some whitespace to output. */ say !/1 /*normalize the factorial product.*/ exit /*stick a fork in it, we're done. */ /*─────────────────────────────────ER subroutine────────────────────────*/ er: say; say '***error!***'; say; say arg(1); say; say; exit 13</lang> output when the input is: 100

100!  is  [158 digits]:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

precision autocorrection

This version of the REXX program allows the use of (pratically) unlimited digits. <lang rexx>/*REXX program computes the factorial of a non-negative integer, and */ /* automatically adjusts the number of digits to accommodate the answer.*/ /* ┌────────────────────────────────────────────────────────────────┐

  │               ───── Some factorial lengths ─────               │
  │                                                                │
  │                   10 !  =           7  digits                  │
  │                   20 !  =          19  digits                  │
  │                   52 !  =          68  digits                  │
  │                  104 !  =         167  digits                  │
  │                  208 !  =         394  digits                  │
  │                  416 !  =         394  digits   (8 deck shoe)  │
  │                                                                │
  │                   1k !  =       2,568  digits                  │
  │                  10k !  =      35,660  digits                  │
  │                 100k !  =     456,574  digits                  │
  │                                                                │
  │                   1m !  =   5,565,709  digits                  │
  │                  10m !  =  65,657,060  digits                  │
  │                 100m !  = 756,570,556  digits                  │
  │                                                                │
  │  Only one result is shown below for pratical reasons.          │
  │                                                                │
  │  This version of the REXX interpreter is essentially limited   │
  │  to around  8  million digits,  but with some programming      │
  │  tricks,  it could yield a result up to  ≈ 16  million digits. │
  │                                                                │
  │  Also, the Regina REXX interpreter is limited to an exponent   │
  │   9  digits,    i.e.:       9.999...999e+999999999             │
  └────────────────────────────────────────────────────────────────┘   */

numeric digits 99 /*99 digs initially, then expanded*/ numeric form /*exponentiated #s =scientric form*/ parse arg n /*get argument from command line. */ if n= then call er 'no argument specified' if arg()>1 | words(n)>1 then call er 'too many arguments specified.' if \datatype(n,'N') then call er "argument isn't numeric: " n if \datatype(n,'W') then call er "argument isn't a whole number: " n if n<0 then call er "argument can't be negative: " n !=1 /*define factorial product so far.*/

/*══════════════════════════════════════where da rubber meets da road──┐*/

    do j=2 to n;    !=!*j            /*compute  the ! the hard way◄───┘*/
    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   /*j*/

/*══════════════════════════════════════════════════════════════════════*/

say n'! is ['length(!) "digits]:" /*display # of digits in factorial*/ say /*add some whitespace to output. */ say !/1 /*normalize the factorial product.*/ exit /*stick a fork in it, we're done. */ /*─────────────────────────────────ER subroutine────────────────────────*/ er: say; say '***error!***'; say; say arg(1); say; say; exit 13</lang> output when the input is: 1000

1000! is  [2568 digits]:

4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048004799886101971960586316668729948085589013238296699445909974245040870737599188236277271887325197795059509952761208749754624970436014182780946464962910563938874378864873371191810458257836478499770124766328898359557354325131853239584630755574091142624174743493475534286465766116677973966688202912073791438537195882498081268678383745597317461360853795345242215865932019280908782973084313928444032812315586110369768013573042161687476096758713483120254785893207671691324484262361314125087802080002616831510273418279777047846358681701643650241536
9139828126481021309276124489635992870511496497541990934222156683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535340819890138544248798495995331910172335555660213945039973628075013783761530712776192684903435262520001588853514733161170210396817592151090778801939317811419454525722386554146106289218796022383897147608850627686296714667469756291123408243920816015378088989396451826324367161676217916890977991190375403127462228998800519544441428201218736174599264295658174662830295557029902432415318161721046583203678690611726015878352075151628422554026517048330422614397428693306169089796848259012
5458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290
1534830776445690990731524332782882698646027898643211390835062170950025973898635542771967428222487575867657523442202075736305694988250879689281627538488633969099598262809561214509948717012445164612603790293091208890869420285106401821543994571568059418727489980942547421735824010636774045957417851608292301353580818400969963725242305608559037006242712434169090041536901059339838357779394109700277534720000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000

rehydration (trailing zero replacement)

This version of the REXX program takes advantage of the fact that the decimal version of factorials (>4) have trailing zeroes, so
it simply strips them (reducing the magnitude of the factorial).
When the factorial is finished computing, the trailing zeroes are simply concatenated to the (dehydrated) factorial product.
This technique will allow other programs to extend their range, especially those that use decimal or floating point decimal,
but can work with binary numbers as well (albeit you'd most likely have to convert the number to decimal when a multiplier is
a multiple of five [or some other method]), strip the trailing zeroes, and then convert it back to binary). <lang rexx>/*REXX program computes the factorial of a non-negative integer, and */ /* automatically adjusts the number of digits to accommodate the answer.*/

/*This version allows for faster multiplying of #s (no trailing zeros).*/ numeric digits 100 /*start with 100 digits. */ numeric form /*indicates we want scientric form*/ parse arg n .; if n== then n=0 /*get argument from command line. */

/*════════════════════════════════════where the rubber meets the road. */ !=1 /*define factorial product so far.*/

    do j=2 to n                      /*compute factorial the hard way. */
    o!=!                             /*save old ! in case of overflow. */
    !=!*j                            /*multiple the factorial with  J, */
                                     /* and strip all trailing zeroes. */
    if pos('E',!)\==0 then do        /*is  !  in exponential notation? */
                           d=digits()               /*D is current digs*/
                           numeric digits d+d%10    /*add ten percent. */
                           !=o!*j    /*recalculate for the lost digit. */
                           end
    !=strip(!,'tail-end',0)          /*kill some electrons, strip 0's. */
    end                              /*(above) only 1st letter is used.*/
                                     /*let's perform some housekeeping.*/

if pos('E',!)\==0 then !=strip(!/1,"T",0) /*! in exponential notation?*/ v=5; tz=0

                   do while v<=n     /*calculate # of trailing zeroes. */
                   tz=tz+n%v
                   v=v*5
                   end  /*while v≤n*/

!=! || copies(0,tz) /*add some water to rehydrate !. */ /*══════════════════════════════════════════════════════════════════════*/

say n'! is ['length(!) "digits]:" /*display # of digits in factorial*/ say /*add some whitespace to output, */ say ! /* ... and display the ! product.*/</lang> output when the input is: 100

100! is  [158 digits]:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Ruby

Beware of recursion! Iterative solutions are better for large n.

With large n, the recursion can overflow the call stack and raise a SystemStackError. So factorial_recursive(10000) might fail.
MRI does not optimize tail recursion. So factorial_tail_recursive(10000) might also fail.

<lang ruby># Recursive def factorial_recursive(n)

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

end

Tail-recursive

def factorial_tail_recursive(n, prod = 1)

 n.zero? ? prod : factorial_tail_recursive(n - 1, prod * n)

end

Iterative with Range#each

def factorial_iterative(n)

 (2 .. n - 1).each {|i| n *= i}
 n

end

Iterative with Range#inject

def factorial_inject(n)

 (1..n).inject {|prod, i| prod * i}

end

Iterative with Range#reduce, requires Ruby 1.8.7

def factorial_reduce(n)

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

end

require 'benchmark'

n = 400 m = 10000

Benchmark.bm(16) do |b|

 b.report('recursive:')       {m.times {factorial_recursive(n)}}
 b.report('tail recursive:')  {m.times {factorial_tail_recursive(n)}}
 b.report('iterative:')       {m.times {factorial_iterative(n)}}
 b.report('inject:')          {m.times {factorial_inject(n)}}
 b.report('reduce:')          {m.times {factorial_reduce(n)}}

end</lang> The benchmark depends on the Ruby implementation. With MRI, #factorial_reduce seems slightly faster than others. This might happen because (1..n).reduce(:*) loops through fast C code, and avoids interpreted Ruby code.

Output

                       user     system      total        real
recursive:         2.350000   0.260000   2.610000 (  2.610410)
tail recursive:    2.710000   0.270000   2.980000 (  2.996830)
iterative:         2.250000   0.250000   2.500000 (  2.510037)
inject:            2.500000   0.130000   2.630000 (  2.641898)
reduce:            2.110000   0.230000   2.340000 (  2.338166)

Run BASIC

<lang runbasic>for i = 0 to 100

  print " fctrI(";right$("00";str$(i),2); ") = "; fctrI(i)
  print " fctrR(";right$("00";str$(i),2); ") = "; fctrR(i)

next i end

function fctrI(n) fctrI = 1

if n >1 then
 for i = 2 To n
   fctrI = fctrI * i
 next i
end if

end function

function fctrR(n) fctrR = 1 if n > 1 then fctrR = n * fctrR(n -1) end function</lang>

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

Library: Scala

Straightforward

This seems in an imperative style but it's converted to functional by a compiler feature called "for comprehension". <lang scala>def factorial(n: Int)={

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

}</lang>

Recursive

<lang scala>def factorial(n: 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 pattern

<lang scala>// Note use of big integer support in this version

implicit def IntToFac(i : Int) = new {

 def ! = (2 to i).foldLeft(BigInt(1))(_*_)

}</lang>

Example used in the REPL:

<lang scala>scala> implicit def IntToFac(i : Int) = new {

    |   def ! = (2 to i).foldLeft(BigInt(1))(_*_)
    | }

IntToFac: (i: Int)java.lang.Object{def !: scala.math.BigInt}

scala> 20! res0: scala.math.BigInt = 2432902008176640000

scala> 100! res1: scala.math.BigInt = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000</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>

Seed7

Seed7 defines the prefix operator ! , which computes a factorial of an integer. The maximum representable number for 32-bit signed integers is 2147483647. For 64-bit signed integers the maximum is 9223372036854775807. This limits the maximum factorial for 32-bit integers to factorial(12)=479001600 and for 64-bit integers to factorial(20)=2432902008176640000. Because of this limitations factorial is a very bad example to show the performance advantage of an iterative solution. To avoid this limitations the functions below use bigInteger:

Iterative

<lang seed7>const func bigInteger: factorial (in bigInteger: n) is func

 result
   var bigInteger: result is 1_;
 local
   var bigInteger: i is 0_;
 begin
   for i range 1_ to n do
     result *:= i;
   end for;
 end func;</lang>

Recursive

<lang seed7>const func bigInteger: factorial (in bigInteger: n) is func

 result
   var bigInteger: result is 1_;
 begin
   if n > 1_ then
     result := n * factorial(pred(n));
   end if;
 end func;</lang>

Scilab

Built-in

The factorial function is built-in to Scilab. The built-in function is only accurate for N <= 21 due to the precision limitations of floating point numbers. <lang Scilab>answer = factorial(N)</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>

Recursive (functional)

<lang smalltalk> |fac|

 fac := [:n |
   n < 0 ifTrue: [ self error: 'fac is defined for natural numbers' ].
   n <= 1 
       ifTrue: [ 1 ]
       ifFalse: [ n * (fac value:(n - 1)) ]
 ].
 fac value:1000.

].</lang>

Works with: Pharo version 1.3-13315

<lang smalltalk>| fac | fac := [ :n | (1 to: n) inject: 1 into: [ :prod :next | prod * next ] ]. fac value: 10. "3628800"</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

Using the Γ Function

Note that this only works correctly for factorials that produce correct representations in double precision floating-point numbers.

Library: Tcllib (Package: math::special)

<lang tcl>package require math::special

proc gfact n {

   expr {round([::math::special::Gamma [expr {$n+1}]])}

}</lang>

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

TorqueScript

Iterative

<lang Torque>function Factorial(%num) {

   if(%num < 2)
       return 1;
   for(%a = %num-1; %a > 1; %a--)
       %num *= %a;
   return %num;

}</lang>

Recursive

<lang Torque>function Factorial(%num) {

   if(%num < 2)
       return 1;
   return %num * Factorial(%num-1);

}</lang>

TUSCRIPT

<lang tuscript>$$ MODE TUSCRIPT LOOP num=-1,12

IF (num==0,1) THEN
 f=1
ELSEIF (num<0) THEN
 PRINT num," is negative number"
 CYCLE
ELSE
 f=VALUE(num)
 LOOP n=#num,2,-1
  f=f*(n-1)
 ENDLOOP
ENDIF

formatnum=CENTER(num,+2," ") PRINT "factorial of ",formatnum," = ",f ENDLOOP</lang> Output:

-1 is negative number
factorial of  0 = 1
factorial of  1 = 1
factorial of  2 = 2
factorial of  3 = 6
factorial of  4 = 24
factorial of  5 = 120
factorial of  6 = 720
factorial of  7 = 5040
factorial of  8 = 40320
factorial of  9 = 362880
factorial of 10 = 3628800
factorial of 11 = 39916800
factorial of 12 = 479001600

TXR

Built-in

Via nPk function:

Functional

<lang sh>$ txr -p '[reduce-left * (range 1 10) 1]' 3628800</lang>

UNIX Shell

Iterative

Works with: Bourne Shell

<lang bash>factorial() {

 set -- "$1" 1
 until test "$1" -lt 2; do
   set -- "`expr "$1" - 1`" "`expr "$2" \* "$1"`"
 done
 echo "$2"

}</lang>

If expr uses 32-bit signed integers, then this function overflows after factorial 12.

Or in Korn style:

Works with: bash

Works with: ksh93

Works with: zsh

<lang bash>function factorial {

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

}</lang>

bash and zsh use 64-bit signed integers, overflows after factorial 20.
ksh93 uses floating-point numbers, prints factorial 19 as an integer, prints factorial 20 in floating-point exponential format.

Recursive

These solutions fork many processes, because each level of recursion spawns a subshell to capture the output.

Works with: Almquist Shell

<lang bash>factorial () {

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

}</lang>

Or in Korn style:

Works with: bash

Works with: ksh93

Works with: pdksh

Works with: zsh

<lang bash>function factorial {

 typeset n=$1
 (( n < 2 )) && echo 1 && return
 echo $(( n * $(factorial $((n-1))) ))

}</lang>

C Shell

This is an iterative solution. csh uses 32-bit signed integers, so this alias overflows after factorial 12. <lang csh>alias factorial eval \set factorial_args=( \!*:q ) \\ @ factorial_n = $factorial_args[2] \\ @ factorial_i = 1 \\ while ( $factorial_n >= 2 ) \\ @ factorial_i *= $factorial_n \\ @ factorial_n -= 1 \\ end \\ @ $factorial_args[1] = $factorial_i \\ '\'

factorial f 12 echo $f

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

VHDL

<lang VHDL>use std.textio.all;

entity rc is end entity rc;

architecture beh of rc is function fact(n:integer) return integer is

   variable f: integer := 1;
   variable i: integer;

begin

   for i in 2 to n loop
       f := f*i;
   end loop;
   return f;

end;

begin process

   variable i: integer;
   variable l: line;

begin

   for i in 0 to 5 loop
       write(l, i);
       write(l, string'(" "));
       write(l, fact(i));
       writeline(output, l);
   end loop;
   wait;

end process; end;</lang>

Output:

Wart

Recursive, all at once

<lang python>def (fact n)

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

Recursive, using cases and pattern matching

<lang python>def (fact n)

 (n * (fact n-1))

def (fact 0)

 1</lang>

Iterative, with an explicit loop

<lang python>def (fact n)

 ret result 1
   for i 1 (i <= n) ++i
     result <- result*i</lang>

Iterative, with a pseudo-generator

<lang python># a useful helper to generate all the natural numbers until n def (nums n)

 collect+for i 1 (i <= n) ++i
   yield i

def (fact n)

 (reduce (*) nums.n 1)</lang>

Wortel

Operator: <lang wortel>@fac 10</lang> Number expression: <lang wortel>!#~F 10</lang> Folding: <lang wortel>!/^* @to 10

or

@prod @to 10</lang> Iterative: <lang wortel>~!10 &n [

 @var r 1
 @for x to n
   :!*r x
 r

]</lang> Recursive: <lang wortel>@let {

 fac &{fac n}?{
   <n 2 n
   *n !fac -n 1
 }

 ; memoized
 facM @mem &n?{
   <n 2 n
   *n !facM -n 1
 }

 !fac 10 !facM 10

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

XL

XPL0

<lang XPL0>func FactIter(N); \Factorial of N using iterative method int N; \range: 0..12 int F, I; [F:= 1; for I:= 2 to N do F:= F*I; return F; ];

func FactRecur(N); \Factorial of N using recursive method int N; \range: 0..12 return if N<2 then 1 else N*FactRecur(N-1);</lang>

ZX Spectrum Basic

Iterative

<lang zxbasic>10 LET x=5: GO SUB 1000: PRINT "5! = ";r 999 STOP 1000 REM ************* 1001 REM * FACTORIAL * 1002 REM ************* 1010 LET r=1 1020 IF x<2 THEN RETURN 1030 FOR i=2 TO x: LET r=r*i: NEXT i 1040 RETURN </lang> Output:

5! = 120

Recursive

Using VAL for delayed evaluation and AND's ability to return given string or empty, we can now control the program flow within an expression in a manner akin to LISP's cond: <lang zxbasic>DEF FN f(n) = VAL (("1" AND n<=0) + ("n*FN f(n-1)" AND n>0)) </lang> But, truth be told, the parameter n does not withstand recursive calling. Changing the order of the product gives naught: <lang zxbasic>DEF FN f(n) = VAL (("1" AND n<=0) + ("FN f(n-1)*n" AND n>0))</lang>