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.
You are encouraged to solve this task according to the task description, using any language you may know.
Write a function to return the factorial of a number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion). Support for trapping negative n errors is optional.
ActionScript
Iterative
<lang actionscript>public static function factorial(n:int):int {
if (n < 0) return 0;
var fact:int = 1; for (var i:int = 1; i <= n; i++) fact *= i;
return fact;
}</lang>
Recursive
<lang actionscript>public static function factorial(n:int):int {
if (n < 0) return 0;
if (n == 0) return 1; return n * factorial(n - 1);
}</lang>
Ada
Iterative
<lang ada>function Factorial (N : Positive) return Positive is
Result : Positive := N; Counter : Natural := N - 1;
begin
for I in reverse 1..Counter loop Result := Result * I; end loop; return Result;
end Factorial;</lang>
Recursive
<lang ada>function Factorial(N : Positive) return Positive is
Result : Positive := 1;
begin
if N > 1 then Result := N * Factorial(N - 1); end if; return Result;
end Factorial;</lang>
Numerical Approximation
<lang ada>with Ada.Numerics.Generic_Complex_Types; with Ada.Numerics.Generic_Complex_Elementary_Functions; with Ada.Numerics.Generic_Elementary_Functions; with Ada.Text_IO.Complex_Io; with Ada.Text_Io; use Ada.Text_Io;
procedure Factorial_Numeric_Approximation is
type Real is digits 15; package Complex_Pck is new Ada.Numerics.Generic_Complex_Types(Real); use Complex_Pck; package Complex_Io is new Ada.Text_Io.Complex_Io(Complex_Pck); use Complex_IO; package Cmplx_Elem_Funcs is new Ada.Numerics.Generic_Complex_Elementary_Functions(Complex_Pck); use Cmplx_Elem_Funcs; function Gamma(X : Complex) return Complex is package Elem_Funcs is new Ada.Numerics.Generic_Elementary_Functions(Real); use Elem_Funcs; use Ada.Numerics; -- Coefficients used by the GNU Scientific Library G : Natural := 7; P : constant array (Natural range 0..G + 1) of Real := ( 0.99999999999980993, 676.5203681218851, -1259.1392167224028, 771.32342877765313, -176.61502916214059, 12.507343278686905, -0.13857109526572012, 9.9843695780195716e-6, 1.5056327351493116e-7); Z : Complex := X; Cx : Complex; Ct : Complex; begin if Re(Z) < 0.5 then return Pi / (Sin(Pi * Z) * Gamma(1.0 - Z)); else Z := Z - 1.0; Set_Re(Cx, P(0)); Set_Im(Cx, 0.0); for I in 1..P'Last loop Cx := Cx + (P(I) / (Z + Real(I))); end loop; Ct := Z + Real(G) + 0.5; return Sqrt(2.0 * Pi) * Ct**(Z + 0.5) * Exp(-Ct) * Cx; end if; end Gamma; function Factorial(N : Complex) return Complex is begin return Gamma(N + 1.0); end Factorial; Arg : Complex;
begin
Put("factorial(-0.5)**2.0 = "); Set_Re(Arg, -0.5); Set_Im(Arg, 0.0); Put(Item => Factorial(Arg) **2.0, Fore => 1, Aft => 8, Exp => 0); New_Line; for I in 0..9 loop Set_Re(Arg, Real(I)); Set_Im(Arg, 0.0); Put("factorial(" & Integer'Image(I) & ") = "); Put(Item => Factorial(Arg), Fore => 6, Aft => 8, Exp => 0); New_Line; end loop;
end Factorial_Numeric_Approximation;</lang> Output:
factorial(-0.5)**2.0 = (3.14159265,0.00000000) factorial( 0) = ( 1.00000000, 0.00000000) factorial( 1) = ( 1.00000000, 0.00000000) factorial( 2) = ( 2.00000000, 0.00000000) factorial( 3) = ( 6.00000000, 0.00000000) factorial( 4) = ( 24.00000000, 0.00000000) factorial( 5) = ( 120.00000000, 0.00000000) factorial( 6) = ( 720.00000000, 0.00000000) factorial( 7) = ( 5040.00000000, 0.00000000) factorial( 8) = ( 40320.00000000, 0.00000000) factorial( 9) = (362880.00000000, 0.00000000)
ALGOL 68
Iterative
<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
<lang algol68># Coefficients used by the GNU Scientific Library # INT g = 7; []REAL p = []REAL(0.99999999999980993, 676.5203681218851, -1259.1392167224028,
771.32342877765313, -176.61502916214059, 12.507343278686905, -0.13857109526572012, 9.9843695780195716e-6, 1.5056327351493116e-7)[@0];
PROC complex gamma = (COMPL in z)COMPL: (
# Reflection formula # COMPL z := in z; IF re OF z < 0.5 THEN pi / (complex sin(pi*z)*complex gamma(1-z)) ELSE z -:= 1; COMPL x := p[0]; FOR i TO g+1 DO x +:= p[i]/(z+i) OD; COMPL t := z + g + 0.5; complex sqrt(2*pi) * t**(z+0.5) * complex exp(-t) * x FI
);
OP ** = (COMPL z, p)COMPL: ( z=0|0|complex exp(complex ln(z)*p) ); PROC factorial = (COMPL n)COMPL: complex gamma(n+1);
FORMAT compl fmt = $g(-16, 8)"⊥"g(-10, 8)$; printf(($q"factorial(-0.5)**2="f(compl fmt)l$, factorial(-0.5)**2)); FOR i TO 9 DO
printf(($q"factorial("d")="f(compl fmt)l$, i, factorial(i)))
OD</lang> Output: <lang algol68>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</lang>
Recursive
<lang algol68>PROC factorial = (INT n)LONG LONG INT:
CASE n+1 IN 1,1,2,6,24,120,720 # a brief lookup # OUT n*factorial(n-1) ESAC
- </lang>
AmigaE
Recursive solution: <lang amigae>PROC fact(x) IS IF x>=2 THEN x*fact(x-1) ELSE 1
PROC main()
WriteF('5! = \d\n', fact(5))
ENDPROC</lang>
Iterative: <lang amigae>PROC fact(x)
DEF r, y IF x < 2 THEN RETURN 1 r := 1; y := x; FOR x := 2 TO y DO r := r * x
ENDPROC r</lang>
AppleScript
Iterative
<lang AppleScript>on factorial(x) if x < 0 then return 0 set R to 1 repeat while x > 1 set {R, x} to {R * x, x - 1} end repeat return R end factorial</lang>
Recursive
<lang AppleScript>on factorial(x) if x < 0 then return 0 if x > 1 then return x * (my factorial(x - 1)) return 1 end factorial</lang>
AutoHotkey
Iterative
<lang AutoHotkey>MsgBox % factorial(4)
factorial(n) {
result := 1 Loop, % n result *= A_Index Return result
}</lang>
Recursive
<lang AutoHotkey>MsgBox % factorial(4)
factorial(n) {
return n > 1 ? n-- * factorial(n) : 1
}</lang>
AWK
Recursive <lang awk>function fact_r(n) {
if ( n <= 1 ) return 1; return n*fact_r(n-1);
}</lang>
Iterative <lang awk>function fact(n) {
if ( n < 1 ) return 1; r = 1 for(m = 2; m <= n; m++) { r *= m; } return r
}</lang>
BASIC
Iterative
<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
<lang freebasic> FUNCTION factorial (n AS Integer) AS Integer
IF n < 2 THEN factorial = 1 ELSE factorial = n * factorial(n-1) END IF
END FUNCTION </lang>
bc
<lang bc>#! /usr/bin/bc -q
define f(x) { if (x <= 1) return (1); return (f(x-1) * x); } f(1000) quit</lang>
Befunge
<lang befunge>&1\> :v v *<
^-1:_$>\:| @.$<</lang>
C
Iterative
<lang c>int factorial(int n) {
int result = 1; for (int i = 1; i <= n; ++i) result *= i; return result;
}</lang>
Recursive
<lang c>int factorial(int n) {
if (n == 0) return 1; else return n*factorial(n-1);
}</lang>
Tail Recursive
Safe with some compilers (e.g. GCC with -O2, LLVM's clang)
<lang c>int fac_aux(int n, int acc) {
if (n < 1) return acc; else return fac_aux(n-1, acc*n);
}
int factorial(int n) {
return fac_aux(n, 1);
}</lang>
C++
The C versions work unchanged with C++, however, here is another possibility using the STL and boost: <lang cpp>#include <boost/iterator/counting_iterator.hpp>
- include <algorithm>
int factorial(int n) {
// last is one-past-end return std::accumulate(boost::counting_iterator<int>(1), boost::counting_iterator<int>(n+1), 1, std::multiplies<int>());
}</lang>
Iterative
This version of the program is iterative, with a do-while loop. <lang cpp> long long int Factorial(long long int m_nValue)
{ long long int result=m_nValue; long long int result_next; long long int pc = m_nValue; do { result_next = result*(pc-1); result = result_next; pc--; }while(pc>2); m_nValue = result; return m_nValue; }
</lang>
C#
Recursive
<lang csharp> class Program {
static long fact(int n) { if (n == 0) return 1; return n * fact(n - 1); }
static void Main(string[] args) { System.Console.WriteLine(fact(5)); //Example }
}</lang>
Iterative
<lang csharp> class Program {
static long fact(int n) { long f = 1; for( int i = 2; i<=n; i++) f=f*i; return f; }
static void Main(string[] args) { System.Console.WriteLine(fact(5)); //Example }
}</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>
Clojure
Folding
<lang lisp>(defn factorial [x]
(apply * (range 2 (inc x)))
)</lang>
Or, in more idiomatical functional style: <lang lisp>(defn factorial [x]
(reduce * (range 2 (inc x)))
)</lang>
Recursive
<lang lisp>(defn factorial [x]
(if (< x 2) 1 (* x (factorial (dec x)))))</lang>
Tail recursive
<lang lisp>(defn factorial [x]
(loop [x x acc 1] (if (< x 2) acc (recur (dec x) (* acc x)))))</lang>
Common Lisp
Recursive: <lang lisp>(defun fact (n)
(if (< n 2) 1 (* n (fact(- n 1)))))
</lang>
Iterative: <lang lisp>(defun factorial (n)
"Calculates N!" (loop for result = 1 then (* result i) for i from 2 to n finally (return result)))</lang>
D
D solution would be similar to C version, but the most known example for factorial is the one using templates calculated during compilation. pragma() compiler directive is used to print calculated value.
<lang D>template itoa(ulong i) {
static if (i < 10) const char[] itoa = "" ~ cast(char)(i + '0'); else const char[] itoa = itoa!(i / 10) ~ itoa!(i % 10);
}
template factorial(uint n) {
static assert(n < 21, "too much for me"); static if (n == 1) const ulong factorial = 1; else const ulong factorial = n * factorial!(n-1);
}
pragma (msg, itoa!(factorial!(20)));
void main() {}</lang>
Dylan
<lang dylan>define method factorial(n)
reduce1(\*, range(from: 1, to: n));
end</lang>
E
<lang e>pragma.enable("accumulator") def factorial(n) {
return accum 1 for i in 2..n { _ * i }
}</lang>
Emacs Lisp
<lang lisp> (defun fact (n)
"n is an integer, this function returns n!, that is n * (n - 1)
- (n - 2)....* 4 * 3 * 2 * 1"
(cond ((= n 1) 1) (t (* n (fact (1- n))))))
</lang>
Erlang
With a fold: <lang erlang>lists:foldl(fun(X,Y) -> X*Y end, 1, lists:seq(1,N)).</lang>
With a recursive function: <lang erlang>fac(1) -> 1; fac(N) -> N * fac(N-1).</lang>
With a tail-recursive function: <lang erlang>fac(N) -> fac(N-1,N). fac(1,N) -> N; fac(I,N) -> fac(I-1,N*I).</lang>
Factor
<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>
Forth
<lang forth>: fac ( n -- n! ) 1 swap 1+ 1 ?do i * loop ;</lang>
Fortran
A simple one-liner is sufficient
nfactorial = PRODUCT((/(i, i=1,n)/))
<lang fortran> INTEGER FUNCTION FACT(N)
INTEGER N, I FACT = 1 DO 10, I = 1, N FACT = FACT * I
10 CONTINUE
RETURN END</lang>
F#
This is a fast tail-recursive implementation. <lang fsharp>let factorial n : bigint =
let rec f a n = match n with | 0I -> a | n -> (f (a * n) (n - 1I)) f 1I n</lang>
> factorial 8I;; val it : bigint = 40320I > factorial 800I;; val it : bigint = 771053011335386004144639397775028360595556401816010239163410994033970851827093069367090769795539033092647861224230677444659785152639745401480184653174909762504470638274259120173309701702610875092918816846985842150593623718603861642063078834117234098513725265045402523056575658860621238870412640219629971024686826624713383660963127048195572279707711688352620259869140994901287895747290410722496106151954257267396322405556727354786893725785838732404646243357335918597747405776328924775897564519583591354080898117023132762250714057271344110948164029940588827847780442314473200479525138318208302427727803133219305210952507605948994314345449325259594876385922128494560437296428386002940601874072732488897504223793518377180605441783116649708269946061380230531018291930510748665577803014523251797790388615033756544830374909440162270182952303329091720438210637097105616258387051884030288933650309756289188364568672104084185529365727646234588306683493594765274559497543759651733699820639731702116912963247441294200297800087061725868223880865243583365623482704395893652711840735418799773763054887588219943984673401051362280384187818611005035187862707840912942753454646054674870155072495767509778534059298038364204076299048072934501046255175378323008217670731649519955699084482330798811049166276249251326544312580289357812924825898217462848297648349400838815410152872456707653654424335818651136964880049831580548028614922852377435001511377656015730959254647171290930517340367287657007606177675483830521499707873449016844402390203746633086969747680671468541687265823637922007413849118593487710272883164905548707198762911703545119701275432473548172544699118836274377270607420652133092686282081777383674487881628800801928103015832821021286322120460874941697199487758769730544922012389694504960000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000I
Genyris
Recursive
<lang genyris>def factorial (n)
if (< n 2) 1 * n factorial (- n 1)</lang>
Groovy
Recursive
A recursive closure must be pre-declared. <lang groovy>def rFact rFact = { (it > 1) ? it * rFact(it - 1) : 1 }</lang>
Test program: <lang groovy>(0..6).each { println "${it}: ${rFact(it)}" }</lang>
Output:
0: 1 1: 1 2: 2 3: 6 4: 24 5: 120 6: 720
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:
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: <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>
HicEst
<lang hicest>WRITE(Clipboard) factorial(6) ! pasted: 720
FUNCTION factorial(n)
factorial = 1 DO i = 2, n factorial = factorial * i ENDDO
END</lang>
IDL
<lang idl>function fact,n
return, product(lindgen(n)+1)
end</lang>
J
Operator
<lang j> ! 8 NB. Built in factorial operator 40320</lang>
Iterative / Functional
<lang j> */1+i.8 40320</lang>
Recursive
<lang j> (*$:@:<:)^:(1&<) 8 40320</lang>
Generalization
Factorial, like all J's primitives, is generalized:
<lang j> ! 8 0.8 _0.8 NB. Generalizes as the gamma function 40320 0.931384 4.59084
! 800x NB. Also arbitrarily large
7710530113353860041446393977750283605955564018160102391634109940339708518270930693670907697955390330926478612242306774446597851526397454014801846531749097625044706382742591201733097017026108750929188168469858421505936237186038616420630788341172340985137252...</lang>
Java
Iterative
<lang java5>public static long fact(int n){
if(n < 0){ System.err.println("No negative numbers"); return 0; } long ans = 1; for(int i = 1;i <= n;i++){ ans *= i; } return ans;
}</lang>
Recursive
<lang java5>public static long fact(int n){
if(n < 0){ System.err.println("No negative numbers"); return 0; } if(n == 0) return 1; return 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 *= n; } return x;
}</lang>
Recursive
<lang javascript>function factorial(n) {
return n<2 ? 1 : n * factorial(n-1);
}</lang>
Functional
(See MDC)
<lang javascript>function factorial(n) {
var nums = [1]; for (var i=2; i<=n; i++) { // No built-in function to generate array of numbers a to n :( nums.push(n); } return nums.reduce(function(a, b) {return a*b});
}</lang>
Lisaac
<lang Lisaac>- factorial x : INTEGER : INTEGER <- (
+ result : INTEGER; (x <= 1).if { result := 1; } else { result := x * factorial(x - 1); }; result
);</lang>
Logo
<lang logo>to factorial :n
if :n < 2 [output 1] output :n * factorial :n-1
end</lang>
Lua
Recursive
<lang lua> function fact(n)
return n > 0 and n * fact(n-1) or 1
end </lang>
Tail Recursive
<lang lua> function fact(n, acc)
acc = acc or 1 if n == 0 then return acc end return fact(n-1, n*acc)
end </lang>
M4
<lang M4>define(`factorial',`ifelse(`$1',0,1,`eval($1*factorial(decr($1)))')')dnl dnl factorial(5)</lang>
Output:
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
<lang mathematica>factorial[n_Integer] := n*factorial[n-1] factorial[0] = 1</lang>
Iterative (direct loop)
<lang mathematica>factorial[n_Integer] :=
Block[{i, result = 1}, For[i = 1, i <= n, ++i, result *= i]; result]</lang>
Iterative (list)
factorial[n_Integer] := Block[{i}, Times @@ Table[i, {i, n}]]
MATLAB
The factorial function is built-in to MATLAB. The built-in function is only accurate for N <= 21 due to the precision limitations of floating point numbers. <lang>answer = factorial(N)</lang>
MAXScript
Iterative
<lang maxscript>fn factorial n = (
if n == 0 then return 1 local fac = 1 for i in 1 to n do ( fac *= i ) fac
)</lang>
Recursive
<lang maxscript>fn factorial_rec n = (
local fac = 1 if n > 1 then ( fac = n * factorial_rec (n - 1) ) fac
)</lang>
Modula-3
Iterative
<lang modula3>PROCEDURE FactIter(n: CARDINAL): CARDINAL =
VAR result := n; counter := n - 1; BEGIN FOR i := counter TO 1 BY -1 DO result := result * i; END; RETURN result; END FactIter;</lang>
Recursive
<lang modula3>PROCEDURE FactRec(n: CARDINAL): CARDINAL =
VAR result := 1;
BEGIN IF n > 1 THEN result := n * FactRec(n - 1); END; RETURN result; END FactRec;</lang>
MUMPS
Iterative
<lang MUMPS> factorial(num) New ii,result If num<0 Quit "Negative number" If num["." Quit "Not an integer" Set result=1 For ii=1:1:num Set result=result*ii Quit result
Write $$factorial(0) ; 1 Write $$factorial(1) ; 1 Write $$factorial(2) ; 2 Write $$factorial(3) ; 6 Write $$factorial(10) ; 3628800 Write $$factorial(-6) ; Negative number Write $$factorial(3.7) ; Not an integer</lang>
Recursive
<lang MUMPS>factorial(num) ; If num<0 Quit "Negative number" If num["." Quit "Not an integer" If num<2 Quit 1 Quit num*$$factorial(num-1)
Write $$factorial(0) ; 1 Write $$factorial(1) ; 1 Write $$factorial(2) ; 2 Write $$factorial(3) ; 6 Write $$factorial(10) ; 3628800 Write $$factorial(-6) ; Negative number Write $$factorial(3.7) ; Not an integer</lang>
Nial
(from Nial help file) <lang nial>fact is recur [ 0 =, 1 first, pass, product, -1 +]</lang> Using it <lang nial>|fact 4 =24</lang>
Niue
Recursive
<lang Niue>[ dup 1 > [ dup 1 - factorial * ] when ] 'factorial ;
( test ) 4 factorial . ( => 24 ) 10 factorial . ( => 3628800 ) </lang>
OCaml
Recursive
<lang ocaml>let rec factorial n =
if n <= 0 then 1 else n * factorial (n-1)</lang>
The following is tail-recursive, so it is effectively iterative: <lang ocaml>let factorial n =
let rec loop i accum = if i > n then accum else loop (i + 1) (accum * i) in loop 1 1</lang>
Iterative
It can be done using explicit state, but this is usually discouraged in a functional language: <lang ocaml>let factorial n =
let result = ref 1 in for i = 1 to n do result := !result * i done; !result</lang>
Octave
<lang octave>% built in factorial printf("%d\n", factorial(50));
% let's define our recursive... function fact = my_fact(n)
if ( n <= 1 ) fact = 1; else fact = n * my_fact(n-1); endif
endfunction
printf("%d\n", my_fact(50));
% let's define our iterative function fact = iter_fact(n)
fact = 1; for i = 2:n fact = fact * i; endfor
endfunction
printf("%d\n", iter_fact(50));</lang>
Output:
30414093201713018969967457666435945132957882063457991132016803840 30414093201713375576366966406747986832057064836514787179557289984 30414093201713375576366966406747986832057064836514787179557289984
(Built-in is fast but use an approximation for big numbers)
Oz
Folding
<lang oz>fun {Fac1 N}
{FoldL {List.number 1 N 1} Number.'*' 1}
end</lang>
Tail recursive
<lang oz>fun {Fac2 N}
fun {Loop N Acc} if N < 1 then Acc else
{Loop N-1 N*Acc}
end end
in
{Loop N 1}
end</lang>
Iterative
<lang oz>fun {Fac3 N}
Result = {NewCell 1}
in
for I in 1..N do Result := @Result * I end @Result
end</lang>
Pascal
Iterative
<lang pascal>function factorial(n: integer): integer;
var i, result: integer; begin result := 1; for i := 1 to n do result := result * i; factorial := result end;</lang>
Recursive
<lang pascal>function factorial(n: integer): integer;
begin if n = 0 then factorial := 1 else factorial := n*factorial(n-1) end;</lang>
Perl
Iterative
<lang perl>sub factorial {
my $n = shift; my $result = 1; for (my $i = 1; $i <= $n; ++$i) { $result *= $i; }; $result;
}
- using a .. range
sub factorial {
my $r = 1; $r *= $_ for 1..shift; $r;
}</lang>
Recursive
<lang perl>sub factorial {
my $n = shift; ($n == 0)? 1 : $n*factorial($n-1);
}</lang>
Functional
<lang perl>use List::Util qw(reduce); sub factorial {
my $n = shift; reduce { $a * $b } 1, 1 .. $n
}</lang>
Perl 6
<lang perl6>sub postfix:<!> { [*] 1..$^n }
say 5!; #prints 120</lang>
PHP
Iterative
<lang php><?php function factorial($n) {
if ($n < 0) { return 0; }
$factorial = 1; for ($i = $n; $i >= 1; $i--) { $factorial = $factorial * $i; }
return $factorial;
} ?></lang>
Recursive
<lang php><?php function factorial($n) {
if ($n < 0) { return 0; }
if ($n == 0) { return 1; }
else { return $n * factorial($n-1); }
} ?></lang>
One-Liner
<lang php><?php function factorial($n) {
return $n == 0 ? 1 : array_product(range(1, $n));
} ?></lang>
Library
Requires the GMP library to be compiled in: <lang php>gmp_fact($n)</lang>
PicoLisp
<lang PicoLisp>(de fact (N)
(if (=0 N) 1 (* N (fact (dec N))) ) )</lang>
or: <lang PicoLisp>(de fact (N)
(apply * (range 1 N) )</lang>
PL/I
<lang PL/I> factorial: procedure (N) returns (fixed decimal (30));
declare N fixed binary nonassignable; declare i fixed decimal (10); declare F fixed decimal (30);
if N < 0 then signal error; F = 1; do i = 2 to N; F = F * i; end; return (F);
end factorial; </lang>
Prolog
<lang prolog>fact(X, 1) :- X<2. fact(X, F) :- Y is X-1, fact(Y,Z), F is Z*X.</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
This one first builds a string, containing 1*2*3...
and then lets PowerShell evaluate it. A bit of mis-use but works.
<lang powershell>function Get-Factorial ($x) {
if ($x -eq 0) { return 1 } return (Invoke-Expression (1..$x -join '*'))
}</lang>
Pure
Recursive
<lang pure>fact n = n*fact (n-1) if n>0;
= 1 otherwise;
let facts = map fact (1..10); facts;</lang>
Tail Recursive
<lang pure>fact n = loop 1 n with
loop p n = if n>0 then loop (p*n) (n-1) else p;
end;</lang>
PureBasic
Iterative
<lang PureBasic>Procedure factorial(n)
Protected i, f = 1 For i = 2 To n f = f * i Next ProcedureReturn f
EndProcedure</lang>
Recursive
<lang PureBasic>Procedure Factorial(n)
If n < 2 ProcedureReturn 1 Else ProcedureReturn n * Factorial(n - 1) EndIf
EndProcedure</lang>
Python
Library
<lang python>import math math.factorial(n)</lang>
Iterative
<lang python>def factorial(n):
if n == 0: return 1 z=n while n>1: n=n-1 z=z*n return z</lang>
Functional
<lang python>from operator import mul
def factorial(n):
return reduce(mul, xrange(1,n+1), 1)</lang>
Sample output:
<lang python>>>> for i in range(6):
print i, factorial(i)
0 1 1 1 2 2 3 6 4 24 5 120 >>></lang>
Numerical Approximation
The following sample uses Lanczos approximation from wp:Lanczos_approximation <lang python>from cmath import *
- Coefficients used by the GNU Scientific Library
g = 7 p = [0.99999999999980993, 676.5203681218851, -1259.1392167224028,
771.32342877765313, -176.61502916214059, 12.507343278686905, -0.13857109526572012, 9.9843695780195716e-6, 1.5056327351493116e-7]
def gamma(z):
z = complex(z) # Reflection formula if z.real < 0.5: return pi / (sin(pi*z)*gamma(1-z)) else: z -= 1 x = p[0] for i in range(1, g+2): x += p[i]/(z+i) t = z + g + 0.5 return sqrt(2*pi) * t**(z+0.5) * exp(-t) * x
def factorial(n):
return gamma(n+1)
print "factorial(-0.5)**2=",factorial(-0.5)**2 for i in range(10):
print "factorial(%d)=%s"%(i,factorial(i))</lang>
Output:
factorial(-0.5)**2= (3.14159265359+0j) factorial(0)=(1+0j) factorial(1)=(1+0j) factorial(2)=(2+0j) factorial(3)=(6+0j) factorial(4)=(24+0j) factorial(5)=(120+0j) factorial(6)=(720+0j) factorial(7)=(5040+0j) factorial(8)=(40320+0j) factorial(9)=(362880+0j)
Recursive
<lang python>def factorial(n):
z=1 if n>1: z=n*factorial(n-1) return z</lang>
Q
Iterative
Point-free
<lang Q>f:(*/)1+til@</lang> or <lang Q>f:(*)over 1+til@</lang> or <lang Q>f:prd 1+til@</lang>
As a function
<lang Q>f:{(*/)1+til x}</lang>
Recursive
<lang Q>f:{$[x=1;1;x*.z.s x-1]}</lang>
R
Recursive
<lang R>fact <- function(n) {
if ( n <= 1 ) 1 else n * fact(n-1)
}</lang>
Iterative
<lang R>factIter <- function(n) {
f = 1 for (i in 2:n) f <- f * i f
}</lang>
Numerical Approximation
R has a native gamma function and a wrapper for that function that can produce factorials. E.g. <lang R>print(factorial(50)) # 3.041409e+64</lang>
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
Ruby
Recursive
<lang ruby>def factorial_recursive(n)
n.zero? ? 1 : n * factorial_recursive(n - 1)
end</lang>
Iterative
<lang ruby>def factorial_iterative(n)
n.downto(2).inject(1) {|factorial, i| factorial *= i}
end</lang>
Functional
<lang ruby>def factorial_functional(n)
(1..n).reduce(1, :*)
end</lang>
Performance
<lang ruby>require 'benchmark'
n = 400 m = 10000
Benchmark.bm(12) do |b|
b.report('recursive:') {m.times {factorial_recursive(n)}} b.report('iterative:') {m.times {factorial_iterative(n)}} b.report('functional:') {m.times {factorial_functional(n)}}
end</lang>
Output
user system total real recursive: 14.875000 0.000000 14.875000 ( 14.914000) iterative: 14.203000 0.000000 14.203000 ( 14.451000) functional: 9.125000 0.000000 9.125000 ( 9.354000)
Sather
<lang sather>class MAIN is
-- recursive fact(a: INTI):INTI is if a < 1.inti then return 1.inti; end; return a * fact(a - 1.inti); end;
-- iterative fact_iter(a:INTI):INTI is s ::= 1.inti; loop s := s * a.downto!(1.inti); end; return s; end;
main is a :INTI := 10.inti; #OUT + fact(a) + " = " + fact_iter(a) + "\n"; end;
end;</lang>
Scala
Imperative
<lang scala>def factorial(n: Int)={
var res = 1 if(n > 0) for(i <- 1 to n) res *=i res
} </lang>
Recursive
<lang scala>def factorial(n: Int): Int ={
if(n == 0) 1 else n * factorial(n-1)
} </lang>
Folding
<lang scala>def factorial(n: Int) = (2 to n).foldLeft(1)(_*_) </lang>
Scheme
Recursive
<lang scheme>(define (factorial n)
(if (<= n 0) 1 (* n (factorial (- n 1)))))</lang>
The following is tail-recursive, so it is effectively iterative: <lang scheme>(define (factorial n)
(let loop ((i 1) (accum 1)) (if (> i n) accum (loop (+ i 1) (* accum i)))))</lang>
Iterative
<lang scheme>(define (factorial n)
(do ((i 1 (+ i 1)) (accum 1 (* accum i))) ((> i n) accum)))</lang>
Slate
This is already implemented in the core language as:
<lang slate>n@(Integer traits) factorial "The standard recursive definition." [
n isNegative ifTrue: [error: 'Negative inputs to factorial are invalid.']. n <= 1 ifTrue: [1] ifFalse: [n * ((n - 1) factorial)]
].</lang>
Here is another way to implement it:
<lang slate>n@(Integer traits) factorial2 [
n isNegative ifTrue: [error: 'Negative inputs to factorial are invalid.']. (1 upTo: n by: 1) reduce: [|:a :b| a * b]
].</lang>
The output:
<lang slate>slate[5]> 100 factorial. 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000</lang>
Smalltalk
Smalltalk Number class already has a factorial method; however, let's see how we can implement it by ourselves.
Iterative with fold
<lang smalltalk>Number extend [
my_factorial [ (self < 2) ifTrue: [ ^1 ] ifFalse: [ |c| c := OrderedCollection new. 2 to: self do: [ :i | c add: i ].
^ (c fold: [ :a :b | a * b ] )
] ]
].
7 factorial printNl. 7 my_factorial printNl.</lang>
Recursive
<lang smalltalk>Number extend [
my_factorial [ self < 0 ifTrue: [ self error: 'my_factorial is defined for natural numbers' ]. self isZero ifTrue: [ ^1 ]. ^self * ((self - 1) my_factorial) ]
].</lang>
Standard ML
Recursive
<lang sml>fun factorial n =
if n <= 0 then 1 else n * factorial (n-1)</lang>
The following is tail-recursive, so it is effectively iterative: <lang sml>fun factorial n = let
fun loop (i, accum) = if i > n then accum else loop (i + 1, accum * i)
in
loop (1, 1)
end</lang>
Tcl
Use Tcl 8.5 for its built-in arbitrary precision integer support.
Iterative
<lang tcl>proc ifact n {
for {set i $n; set sum 1} {$i >= 2} {incr i -1} { set sum [expr {$sum * $i}] } return $sum
}</lang>
Recursive
<lang tcl>proc rfact n {
expr {$n < 2 ? 1 : $n * [rfact [incr n -1]]}
}</lang>
The recursive version is limited by the default stack size to roughly 850!
When put into the tcl::mathfunc namespace, the recursive call stays inside the expr language, and thus looks clearer:
<lang Tcl>proc tcl::mathfunc::fact n {expr {$n < 2? 1: $n*fact($n-1)}}</lang>
Iterative with caching
<lang tcl>proc ifact_caching n {
global fact_cache if { ! [info exists fact_cache]} { set fact_cache {1 1} } if {$n < [llength $fact_cache]} { return [lindex $fact_cache $n] } set i [expr {[llength $fact_cache] - 1}] set sum [lindex $fact_cache $i] while {$i < $n} { incr i set sum [expr {$sum * $i}] lappend fact_cache $sum } return $sum
}</lang>
Performance Analysis
<lang tcl>puts [ifact 30] puts [rfact 30] puts [ifact_caching 30]
set n 400 set iterations 10000 puts "calculate $n factorial $iterations times" puts "ifact: [time {ifact $n} $iterations]" puts "rfact: [time {rfact $n} $iterations]"
- for the caching proc, reset the cache between each iteration so as not to skew the results
puts "ifact_caching: [time {ifact_caching $n; unset -nocomplain fact_cache} $iterations]"</lang> Output:
265252859812191058636308480000000 265252859812191058636308480000000 265252859812191058636308480000000 calculate 400 factorial 10000 times ifact: 661.4324 microseconds per iteration rfact: 654.7593 microseconds per iteration ifact_caching: 613.1989 microseconds per iteration
TI-89 BASIC
TI-89 BASIC also has the factorial function built in: x! is the factorial of x.
<lang ti89b>factorial(x) Func
Return Π(y,y,1,x)
EndFunc</lang>
Π is the standard product operator:
UNIX Shell
<lang bash>fact () {
if [ $1 -eq 0 ]; then echo 1; else echo $(($1 * $(fact $(($1-1)) ) )); fi;
}</lang>
Ursala
There is already a library function for factorials, but they can be defined anyway like this. The good method treats natural numbers as an abstract type, and the better method factors out powers of 2 by bit twiddling. <lang Ursala>#import nat
good_factorial = ~&?\1! product:-1^lrtPC/~& iota better_factorial = ~&?\1! ^T(~&lSL,@rS product:-1)+ ~&Z-~^*lrtPC/~& iota</lang> test program: <lang Ursala>#cast %nL
test = better_factorial* <0,1,2,3,4,5,6,7,8></lang> output:
<1,1,2,6,24,120,720,5040,40320>
VBScript
Optimized with memoization, works for numbers up to 170 (because of the limitations on Doubles), exits if -1 is input <lang VBScript>Dim lookupTable(170), returnTable(170), currentPosition, input currentPosition = 0
Do While True input = InputBox("Please type a number (-1 to quit):") MsgBox "The factorial of " & input & " is " & factorial(CDbl(input)) Loop
Function factorial (x) If x = -1 Then WScript.Quit 0 End If Dim temp temp = lookup(x) If x <= 1 Then factorial = 1 ElseIf temp <> 0 Then factorial = temp Else temp = factorial(x - 1) * x store x, temp factorial = temp End If End Function
Function lookup (x) Dim i For i = 0 To currentPosition - 1 If lookupTable(i) = x Then lookup = returnTable(i) Exit Function End If Next lookup = 0 End Function
Function store (x, y) lookupTable(currentPosition) = x returnTable(currentPosition) = y currentPosition = currentPosition + 1 End Function </lang>
x86 Assembly
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>