Factorial

Factorial
You are encouraged to solve this task according to the task description, using any language you may know.

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

Write a function to return the factorial of a number. Solutions can be iterative or recursive. Support for trapping negative n errors is optional.

ABAP

Iterative

form factorial using iv_val type i.
  data: lv_res type i value 1.
  do iv_val times.
    multiply lv_res by sy-index.
  enddo.
 
  iv_val = lv_res.
endform.

Recursive

form fac_rec using iv_val type i.
  data: lv_temp type i.
 
  if iv_val = 0.
    iv_val = 1.
  else.
    lv_temp = iv_val - 1.
    perform fac_rec using lv_temp.
    multiply iv_val by lv_temp.
  endif.
endform.

ActionScript

Iterative

public static function factorial(n:int):int
{
    if (n < 0)
        return 0;
 
    var fact:int = 1;
    for (var i:int = 1; i <= n; i++)
        fact *= i;
 
    return fact;
}

Recursive

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

Ada

Iterative

function Factorial (N : Positive) return Positive is
   Result : Positive := N;
   Counter : Natural := N - 1;
begin
   for I in reverse 1..Counter loop
      Result := Result * I;
   end loop;
   return Result;
end Factorial;

Recursive

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

Numerical Approximation

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

Output:

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

Aime

Iterative

integer
factorial(integer n)
{
    integer i, result;
 
    result = 1;
    i = 1;
    while (i < n) {
        i += 1;
        result *= i;
    }
 
    return result;
}

ALGOL 68

Iterative

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

Numerical Approximation

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

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

INT g = 7;
[]REAL p = []REAL(0.99999999999980993, 676.5203681218851,   -1259.1392167224028, 
                771.32342877765313,   -176.61502916214059,     12.507343278686905, 
                 -0.13857109526572012,   9.9843695780195716e-6, 1.5056327351493116e-7)[@0];
 
PROC complex gamma = (COMPL in z)COMPL: (
  # Reflection formula #
  COMPL z := in z;
  IF re OF z < 0.5 THEN
    pi / (complex sin(pi*z)*complex gamma(1-z))
  ELSE
    z -:= 1;
    COMPL x := p[0];
    FOR i TO g+1 DO x +:= p[i]/(z+i) OD;
    COMPL t := z + g + 0.5;
    complex sqrt(2*pi) * t**(z+0.5) * complex exp(-t) * x
  FI
);
 
OP ** = (COMPL z, p)COMPL: ( z=0|0|complex exp(complex ln(z)*p) );
PROC factorial = (COMPL n)COMPL: complex gamma(n+1);
 
FORMAT compl fmt = $g(-16, 8)"⊥"g(-10, 8)$;
 
test:(
  printf(($q"factorial(-0.5)**2="f(compl fmt)l$, factorial(-0.5)**2));
  FOR i TO 9 DO
    printf(($q"factorial("d")="f(compl fmt)l$, i, factorial(i)))
  OD
)
 

Output:

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

Recursive

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

AmigaE

Recursive solution:

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

Iterative:

PROC fact(x)
  DEF r, y
  IF x < 2 THEN RETURN 1
  r := 1; y := x;
  FOR x := 2 TO y DO r := r * x
ENDPROC r

AppleScript

Iterative

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

Recursive

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

AutoHotkey

Iterative

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

Recursive

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

AutoIt

Iterative

;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

Recursive

;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

AWK

Recursive

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

Iterative

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

BASIC

Iterative

Works with: QBasic

Works with: RapidQ

FUNCTION factorial (n AS Integer) AS Integer
    DIM f AS Integer, i AS Integer
    f = 1
    FOR  i = 2 TO n
        f = f*i
    NEXT i
    factorial = f
END FUNCTION

Recursive

Works with: QBasic

Works with: RapidQ

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

Batch File

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

BBC BASIC

Works with: BBC BASIC for Windows

18! is the largest that doesn't overflow.

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

Output:

6402373705728000

bc

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

Befunge

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

Bracmat

Compute 10! and checking that it is 3628800, the esoteric way

      ( 
      =   
        .   !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
 

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!

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

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

(factorial=
  r
.   !arg:?r
  &   whl
    ' (!arg:>1&(!arg+-1:?arg)*!r:?r)
  & !r
);

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

Brainf***

Prints sequential factorials in an infinite loop.

>++++++++++>>>+>+[>>>+[-[<<<<<[+<<<<<]>>[[-]>[<<+>+>-]<[>+<-]<[>+<-[>+<-[>
+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>>>>+>+<<<<<<-[>+<-]]]]]]]]]]]>[<+>-
]+>>>>>]<<<<<[<<<<<]>>>>>>>[>>>>>]++[-<<<<<]>>>>>>-]+>>>>>]<[>++<-]<<<<[<[
>+<-]<<<<]>>[->[-]++++++[<++++++++>-]>>>>]<<<<<[<[>+>+<<-]>.<<<<<]>.>>>>]

Brat

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

C

Iterative

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

Recursive

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

Tail Recursive

Safe with some compilers (for example: GCC with -O2, LLVM's clang)

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

C++

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

#include <boost/iterator/counting_iterator.hpp>
#include <algorithm>
 
int factorial(int n)
{
  // last is one-past-end
  return std::accumulate(boost::counting_iterator<int>(1), boost::counting_iterator<int>(n+1), 1, std::multiplies<int>());
}

Iterative

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

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

Template

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
}

C#

Iterative

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

Recursive

using System;
 
class Program
{
    static int Factorial(int number)
    {
        return number == 0 ? 1 : number * Factorial(number - 1);
    }
 
    static void Main()
    {
        Console.WriteLine(Factorial(10));
    }
}

Tail Recursive

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

Functional

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

Cat

Taken direct from the Cat manual:

define rec_fac
      { dup 1 <= [pop 1] [dec rec_fac *] if }

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.

Clay

Obviously there’s more than one way to skin a cat. Here’s a selection — recursive, iterative, and “functional” solutions.

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

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

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

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

[N|Integer?(N)] factorial(n: N) {
    if (n == 0) return N(1);
    return n * factorial(n - 1);
}

And testing:

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

CLIPS

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

Clojure

Folding

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

Recursive

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

Tail recursive

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

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

Common Lisp

Recursive:

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

Iterative:

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

Functional:

(defun factorial (n)
    (reduce #'* (loop for i from 1 to n collect i)))

CoffeeScript

Several solutions are possible in JavaScript:

Recursive

fac = (n) ->
  if n <= 1
    1
  else
    n * fac n-1

Functional

Works with: JavaScript version 1.8

(See MDC)

fac = (n) ->
  [1..n].reduce (x,y) -> x*y

D

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

Output:

2004310016
2004310016
2004310016
2004310016
2004310016
2004310016
2004310016
2004310016

Dart

Recursive

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

Iterative

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

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.

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

Delphi

Iterative

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.

Recursive

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.

Tail Recursive

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.

DWScript

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

Iterative

function IterativeFactorial(n : Integer) : Integer;
var 
   i : Integer;
begin
   Result := 1;
   for i := 2 to n do
      Result *= i;
end;

Recursive

function RecursiveFactorial(n : Integer) : Integer;
begin
   if n>1 then
      Result := RecursiveFactorial(n-1)*n
   else Result := 1;
end;

Dylan

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

E

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

Ela

Tail recursive version:

let fact = fact' 1L             
           where fact' acc 0 = acc                  
                 fact' acc n = fact' (n * acc) (n - 1)

Emacs Lisp

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

Erlang

With a fold:

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

With a recursive function:

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

With a tail-recursive function:

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

Euphoria

Straight forward methods

Iterative

function factorial(integer n)
  atom f = 1
  while n > 1 do
    f *= n
    n -= 1
  end while
 
  return f
end function

Recursive

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

Tail Recursive

Works with: Euphoria version 4.0.0

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

'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.

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

F#

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

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

Factor

Translation of: Haskell

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

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

FALSE

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

Recursive:

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

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
}

Fantom

The following uses 'Ints' to hold the computed factorials, which limits results to a 64-bit signed integer.

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

Forth

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

Fortran

Fortran 90

A simple one-liner is sufficient

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

FORTRAN 77

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

GAP

# Built-in
Factorial(5);
 
# An implementation
fact := n -> Product([1 .. n]);

Genyris

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

GML

n = argument0
j = 1
for(i = 1; i <= n; i += 1)
    j *= i
return j

Golfscript

Iterative (uses folding)

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

or

{),(;{*}*}:fact;

Recursive

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

Go

Iterative, sequential, but at least handling big numbers:

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
}

Built in function currently uses a simple divide and conquer technique. It's a step up from sequential multiplication.

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

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.

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

Test program:

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

Output:

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

Iterative

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

Test program:

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

Output:

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

Haskell

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

factorial n = product [1..n]

Or, written explicitly as a fold:

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

See also: The Evolution of a Haskell Programmer

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

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

Or, written without library functions:

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

HicEst

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

Icon and Unicon

Recursive

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

Iterative

The

Library: Icon Programming Library

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

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

IDL

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

Inform 6

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

Io

Facorials are built-in to Io:

3 factorial

J

Operator

  ! 8             NB.  Built in factorial operator
40320

Iterative / Functional

   */1+i.8
40320

Recursive

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

Generalization

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

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

Java

Iterative

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

Recursive

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

JavaScript

Several solutions are possible in JavaScript:

Iterative

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

Recursive

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

Functional

Works with: JavaScript version 1.8

(See MDC)

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

Joy

DEFINE factorial == [0 =] [pop 1] [dup 1 - factorial *] ifte. 

K

Iterative

  facti:*/1+!:
  facti 5
120

Recursive

  factr:{:[x>1;x*_f x-1;1]}
  factr 6
720

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

Liberty BASIC

    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

Lisaac

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

Logo

Recursive

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

Iterative

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

to factorial :n 
	make "fact 1 
	make "i 1 
	repeat :n [make "fact :fact * :i make "i :i + 1] 
	print :fact 
end

Lua

Recursive

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

Tail Recursive

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

M4

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

Output:

120

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

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

Iterative (direct loop)

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

Iterative (list)

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

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.

answer = factorial(N)

Recursive

function f=fac(n)
    if n==0
        f=1;
        return
    else
        f=n*fac(n-1);
    end

Iterative

A possible iterative solution:

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

Maxima

Built-in

n!

Recursive

fact(n) := if n < 2 then 1 else n*fact(n - 1)

Iterative

fact2(n) := block([r], r: 1, for i: 1 thru n do r: r*i, r);

MAXScript

Iterative

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

Recursive

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

Mirah

def factorial_iterative(n:int)
    2.upto(n-1) do |i|
        n *= i 
    end
    n
end
 
puts factorial_iterative 10

ML/I

Iterative

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)

Recursive

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)

Modula-3

Iterative

PROCEDURE FactIter(n: CARDINAL): CARDINAL =
  VAR
    result := n;
    counter := n - 1;
 
  BEGIN
    FOR i := counter TO 1 BY -1 DO
      result := result * i;
    END;
    RETURN result;
  END FactIter;

Recursive

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

MUMPS

Iterative

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

Recursive

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

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.

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

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

Output

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

newLISP

> (define (factorial n) (exp (gammaln (+ n 1))))
(lambda (n) (exp (gammaln (+ n 1))))
> (factorial 4)
24

Nial

(from Nial help file)

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

Using it

|fact 4
=24

Niue

Recursive

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

Objeck

Iterative

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

OCaml

Recursive

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

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

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

Iterative

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

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

Octave

% built in factorial
printf("%d\n", factorial(50));
 
% let's define our recursive...
function fact = my_fact(n)
  if ( n <= 1 )
    fact = 1;
  else
    fact = n * my_fact(n-1);
  endif
endfunction
 
printf("%d\n", my_fact(50));
 
% let's define our iterative
function fact = iter_fact(n)
  fact = 1;
  for i = 2:n
    fact = fact * i;
  endfor
endfunction
 
printf("%d\n", iter_fact(50));

Output:

30414093201713018969967457666435945132957882063457991132016803840
30414093201713375576366966406747986832057064836514787179557289984
30414093201713375576366966406747986832057064836514787179557289984

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

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:

#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

Tail recursion:

#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

Oz

Folding

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

Tail recursive

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

Iterative

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

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. Moessner's algorithm is very slow but should be able to compute factorials until it runs out of memory (usage is about n²logn bits to compute n!); a machine with 1 GB of RAM and unlimited time could, in theory, find 100,000-digit factorials.

Recursive

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

Iterative

This is an improvement on the naive recursion above, being faster and not limited by stack space.

fact(n)=my(p=1);for(k=2,n,p*=k);p

Binary splitting

PARI's prod automatically uses binary splitting, preventing subproducts from growing overly large. This function is dramatically faster than the above.

fact(n)=prod(k=2,n,k)

Recursive 1

Even faster

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)

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.

fact(n)=n!

Gamma

Note also the presence of factorial and lngamma.

fact(n)=round(gamma(n+1))

Moessner's algorithm

Not practical, just amusing. Note the lack of * or ^.

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

Pascal

Iterative

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

Recursive

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

Perl

Iterative

sub factorial
{
  my $n = shift;
  my $result = 1;
  for (my $i = 1; $i <= $n; ++$i)
  {
    $result *= $i;
  };
  $result;
}
 
# using a .. range
sub factorial {
    my $r = 1;
    $r *= $_ for 1..shift;
    $r;
}

Recursive

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

Functional

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

Perl 6

Works with: Rakudo version #22 "Thousand Oaks"

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

PHP

Iterative

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

Recursive

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

One-Liner

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

Library

Requires the GMP library to be compiled in:

gmp_fact($n)

PicoLisp

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

or:

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

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

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

PL/I

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

PostScript

Recursive

/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

Iterative

/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

Combinator

Library: initlib

/myfact {{dup 0 eq} {pop 1} {dup pred} {mul} linrec}.

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

PowerShell

Recursive

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

Iterative

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

Evaluative

Works with: PowerShell version 2

This one first builds a string, containing 1*2*3... and then lets PowerShell evaluate it. A bit of mis-use but works.

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

Prolog

Works with: SWI Prolog

Recursive

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

Tail recursive

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

Fold

We can simulate foldl.

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

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 :

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

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.

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

Pure

Recursive

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

Tail Recursive

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

PureBasic

Iterative

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

Recursive

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

Python

Library

Works with: Python version 2.6+, 3.x

import math
math.factorial(n)

Iterative

def factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

Functional

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

Sample output:

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

Numerical Approximation

The following sample uses Lanczos approximation from wp:Lanczos_approximation

from cmath import *
 
# Coefficients used by the GNU Scientific Library
g = 7
p = [0.99999999999980993, 676.5203681218851, -1259.1392167224028,
     771.32342877765313, -176.61502916214059, 12.507343278686905,
     -0.13857109526572012, 9.9843695780195716e-6, 1.5056327351493116e-7]
 
def gamma(z):
  z = complex(z)
  # Reflection formula
  if z.real < 0.5:
    return pi / (sin(pi*z)*gamma(1-z))
  else:
    z -= 1
    x = p[0]
    for i in range(1, g+2):
      x += p[i]/(z+i)
    t = z + g + 0.5
    return sqrt(2*pi) * t**(z+0.5) * exp(-t) * x
 
def factorial(n):
  return gamma(n+1)
 
print "factorial(-0.5)**2=",factorial(-0.5)**2
for i in range(10):
  print "factorial(%d)=%s"%(i,factorial(i))

Output:

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

Recursive

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

Q

Iterative

Point-free

f:(*/)1+til@

or

f:(*)over 1+til@

or

f:prd 1+til@

As a function

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

Recursive

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

R

Recursive

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

Iterative

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

Numerical Approximation

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

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

REBOL

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

Output:

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

• See also more on memoization...

Retro

A recursive implementation from the benchmarking code.

: <factorial> dup 1 = if; dup 1- <factorial> * ;
: factorial dup 0 = [ 1+ ] [ <factorial> ] if ;

REXX

version 1

This version of the REXX program allows the use of (pratically) unlimited digits.

/*REXX program computes the factorial of a non-negative integer,  and   */
/* automatically adjusts the number of digits to accommodate the answer.*/
 
/*   ┌──────────────────────────────────────────────────────────────┐
     │  Some gihugeic factorials calculated:                        │
     │                                                              │
     │                   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, this version of the REXX interpreter is limited to an │
     │  exponent of  9  digits,   i.e.:    9.999...999e+999999999   │
     └──────────────────────────────────────────────────────────────┘   */
 
numeric digits 100                    /*start with 100 digits.          */
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' n "must be numeric"
if \datatype(n,'W')     then call er 'argument' n "must be a whole number"
if n<0                  then call er 'argument' n "must not be negative"
 
/*════════════════════════════════════where the rubber meets the road.  */
!=1                                   /*define factorial produce so far.*/
if n\==0 then                         /*test to enable a fast version DO*/
     do j=2 for n-1                   /*compute factorial the hard way. */
     !=!*j                            /*multiple the factorial with  J. */
     if pos('E',!)==0 then iterate    /*is  !  in exponential notation? */
     parse var ! 'E' digs             /*pick off the factorial exponent.*/
     numeric digits digs+digs%10      /*  and incease it by ten percent.*/
     end
/*══════════════════════════════════════════════════════════════════════*/
 
say n'! is  ['length(!) "digits]:"    /*display # of digits in factorial*/
say                                   /*add some whitespace to output.  */
say !/1                               /*normalize the factorial product.*/
exit
 
/*────────────────────────────────────ER subroutine─────────────────────*/
er:  say;  say '***error!***';  say;  say arg(1);  say;  say;  exit 13

Output when the input is: 1000

1000! is  [2568 digits]:

40238726007709377354370243392300398571937486421071463254379991042993851239862902059204420848696940480047998861019719605863166687299480855890132382966994459099742450408707375991882362772718873251977950
59509952761208749754624970436014182780946464962910563938874378864873371191810458257836478499770124766328898359557354325131853239584630755574091142624174743493475534286465766116677973966688202912073791
43853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151
02734182797770478463586817016436502415369139828126481021309276124489635992870511496497541990934222156683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535
34081989013854424879849599533191017233555566021394503997362807501378376153071277619268490343526252000158885351473316117021039681759215109077880193931781141945452572238655414610628921879602238389714760
88506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786
90611726015878352075151628422554026517048330422614397428693306169089796848259012545832716822645806652676995865268227280707578139185817888965220816434834482599326604336766017699961283186078838615027946
59551311565520360939881806121385586003014356945272242063446317974605946825731037900840244324384656572450144028218852524709351906209290231364932734975655139587205596542287497740114133469627154228458623
77387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819
37238864261483965738229112312502418664935314397013742853192664987533721894069428143411852015801412334482801505139969429015348307764456909907315243327828826986460278986432113908350621709500259738986355
42771967428222487575867657523442202075736305694988250879689281627538488633969099598262809561214509948717012445164612603790293091208890869420285106401821543994571568059418727489980942547421735824010636
77404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

version 2

This version of the REXX program takes advantage of the fact that the decimal version of the factorial has 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 factorial.
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 have to convert the number to decimal, strip the trailing zeroes, and
then convert back to binary).

/*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.          */
parse arg n .; if n=='' then n=0      /*get argument from command line. */
 
/*════════════════════════════════════where the rubber meets the road.  */
!=1                                   /*define factorial produce so far.*/
if n\==0 then                         /*test to enable a fast version DO*/
     do j=2 for n-1                   /*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()
                            numeric digits d+d%10     /*digs=digs + 10%.*/
                            !=o!*j    /*now, recalcuate for the lost dig*/
                            end
                       else !=strip(!,'T',0)      /*kill some electrons.*/
     end
                                      /*let's perform some housekeeping.*/
if pos('E',!)\==0 then !=strip(!/1,'T',0) /*is ! in exponential notation*/
v=5; tz=0; do while v<=n; tz=tz+n%v; v=v*5; end /*calc # trailing zeroes*/
!=!||copies(0,tz)                     /*add some water to re-hydrate !. */
/*══════════════════════════════════════════════════════════════════════*/
 
say n'! is  ['length(!) "digits]:"    /*display # of digits in factorial*/
say                                   /*add some whitespace to output.  */
say !

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.

# 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

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)

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;

Scala

Imperative

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

Recursive

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

Folding

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

Using Pimp My Library pattern

// Note use of big integer support in this version
 
implicit def IntToFac(i : Int) = new {
  def ! = (2 to i).foldLeft(BigInt(1))(_*_)
}

Example use in the REPL:

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

Scheme

Recursive

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

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

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

Iterative

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

Folding

;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

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

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;

Recursive

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;

Sisal

Solution using a fold:

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

Simple example using a recursive function:

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

Slate

This is already implemented in the core language as:

n@(Integer traits) factorial
"The standard recursive definition."
[
  n isNegative ifTrue: [error: 'Negative inputs to factorial are invalid.'].
  n <= 1
    ifTrue: [1]
    ifFalse: [n * ((n - 1) factorial)]
].

Here is another way to implement it:

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

The output:

slate[5]> 100 factorial.
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

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

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.

Recursive

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

Recursive (functional)

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

Works with: Pharo version 1.3-13315

| fac |
fac := [ :n | (1 to: n) inject: 1 into: [ :prod :next | prod * next ] ]. 
fac value: 10. 
"3628800"

SNOBOL4

Works with: Macro Spitbol

Works with: CSnobol

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

Recursive

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

Tail-recursive

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

Iterative

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

Test and display factorials 0 .. 10

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

Output:

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

Standard ML

Recursive

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

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

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

Tcl

Works with: Tcl version 8.5

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

Iterative

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

Recursive

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

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

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

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

Iterative with caching

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

Performance Analysis

puts [ifact 30]
puts [rfact 30]
puts [ifact_caching 30]
 
set n 400
set iterations 10000
puts "calculate $n factorial $iterations times"
puts "ifact: [time {ifact $n} $iterations]"
puts "rfact: [time {rfact $n} $iterations]"
# for the caching proc, reset the cache between each iteration so as not to skew the results
puts "ifact_caching: [time {ifact_caching $n; unset -nocomplain fact_cache} $iterations]"

Output:

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

TI-89 BASIC

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

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

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

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

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 

UNIX Shell

Iterative

Works with: Bourne Shell

factorial() {
  set -- "$1" 1
  until test "$1" -lt 2; do
    set -- "`expr "$1" - 1`" "`expr "$2" \* "$1"`"
  done
  echo "$2"
}

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

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

• 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

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

Or in Korn style:

Works with: bash

Works with: ksh93

Works with: pdksh

Works with: zsh

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

C Shell

This is an iterative solution. csh uses 32-bit signed integers, so this alias overflows after factorial 12.

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

Ursala

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

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

test program:

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

output:

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

VBScript

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

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

Wrapl

Product

DEF fac(n) n <= 1 | PROD 1:to(n);

Recursive

DEF fac(n) n <= 0 => 1 // n * fac(n - 1);

Folding

DEF fac(n) n <= 1 | :"*":foldl(ALL 1:to(n));

x86 Assembly

Works with: nasm

Iterative

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

Recursive

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

Tail Recursive

global factorial
section .text
 
; Input in ECX register
; Output in EAX register
factorial:
  mov   eax, 1  ; default argument, store 1 in accumulator
 
.base_case:
  test  ecx, ecx
  jnz   .inductive_case  ; return accumulator if n == 0
  ret
 
.inductive_case:
  mul   ecx         ; accumulator *= n
  dec   ecx         ; n -= 1
  jmp   .base_case  ; tail call

XL

0! -> 1
N! -> N * (N-1)!

ZX Spectrum Basic

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 

Output:

5! = 120