Factorial: Difference between revisions
(added J) |
(lang tag switch, wp links, added CL) |
||
Line 1: | Line 1: | ||
{{task|Arithmetic operations}}[[Category:Recursion]][[Category:Classic CS problems and programs]]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 [ |
{{task|Arithmetic operations}}[[Category:Recursion]][[Category:Classic CS problems and programs]]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 [[wp:Factorial#Definition|defined]] as being 1. |
||
Write a function to return the factorial of a number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion). Support for trapping negative n errors is optional. |
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. |
||
Line 5: | Line 5: | ||
=={{header|ActionScript}}== |
=={{header|ActionScript}}== |
||
===Iterative=== |
===Iterative=== |
||
<actionscript> |
<lang actionscript> |
||
public static function factorial(n:int):int |
public static function factorial(n:int):int |
||
{ |
{ |
||
Line 17: | Line 17: | ||
return fact; |
return fact; |
||
} |
} |
||
</lang> |
|||
</actionscript> |
|||
===Recursive=== |
===Recursive=== |
||
<actionscript> |
<lang actionscript> |
||
public static function factorial(n:int):int |
public static function factorial(n:int):int |
||
{ |
{ |
||
Line 30: | Line 30: | ||
return n * factorial(n - 1); |
return n * factorial(n - 1); |
||
} |
} |
||
</lang> |
|||
</actionscript> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
===Iterative=== |
===Iterative=== |
||
<lang ada> |
|||
<Ada> |
|||
function Factorial (N : Positive) return Positive is |
function Factorial (N : Positive) return Positive is |
||
Result : Positive := N; |
Result : Positive := N; |
||
Line 44: | Line 44: | ||
return Result; |
return Result; |
||
end Factorial; |
end Factorial; |
||
</ |
</lang> |
||
===Recursive=== |
===Recursive=== |
||
<lang ada> |
|||
<Ada> |
|||
function Factorial(N : Positive) return Positive is |
function Factorial(N : Positive) return Positive is |
||
Result : Positive := 1; |
Result : Positive := 1; |
||
Line 55: | Line 55: | ||
return Result; |
return Result; |
||
end Factorial; |
end Factorial; |
||
</ |
</lang> |
||
===Numerical Approximation=== |
===Numerical Approximation=== |
||
<lang ada> |
|||
<Ada> |
|||
with Ada.Numerics.Generic_Complex_Types; |
with Ada.Numerics.Generic_Complex_Types; |
||
with Ada.Numerics.Generic_Complex_Elementary_Functions; |
with Ada.Numerics.Generic_Complex_Elementary_Functions; |
||
Line 120: | Line 120: | ||
end loop; |
end loop; |
||
end Factorial_Numeric_Approximation; |
end Factorial_Numeric_Approximation; |
||
</ |
</lang> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 198: | Line 198: | ||
{{works with|FreeBASIC}} |
{{works with|FreeBASIC}} |
||
{{works with|RapidQ}} |
{{works with|RapidQ}} |
||
<freebasic> |
<lang freebasic> |
||
FUNCTION factorial (n AS Integer) AS Integer |
FUNCTION factorial (n AS Integer) AS Integer |
||
DIM f AS Integer, i AS Integer |
DIM f AS Integer, i AS Integer |
||
Line 207: | Line 207: | ||
factorial = f |
factorial = f |
||
END FUNCTION |
END FUNCTION |
||
</ |
</lang> |
||
===Recursive=== |
===Recursive=== |
||
{{works with|FreeBASIC}} |
{{works with|FreeBASIC}} |
||
{{works with|RapidQ}} |
{{works with|RapidQ}} |
||
<freebasic> |
<lang freebasic> |
||
FUNCTION factorial (n AS Integer) AS Integer |
FUNCTION factorial (n AS Integer) AS Integer |
||
IF n < 2 THEN |
IF n < 2 THEN |
||
Line 220: | Line 220: | ||
END IF |
END IF |
||
END FUNCTION |
END FUNCTION |
||
</ |
</lang> |
||
=={{header|Befunge}}== |
=={{header|Befunge}}== |
||
Line 229: | Line 229: | ||
=={{header|C}}== |
=={{header|C}}== |
||
=== Iterative === |
=== Iterative === |
||
<c> |
<lang c> |
||
int factorial(int n) |
int factorial(int n) |
||
{ |
{ |
||
Line 237: | Line 237: | ||
return result; |
return result; |
||
} |
} |
||
</ |
</lang> |
||
=== Recursive === |
=== Recursive === |
||
<c> |
<lang c> |
||
int factorial(int n) |
int factorial(int n) |
||
{ |
{ |
||
Line 247: | Line 247: | ||
return n*factorial(n-1); |
return n*factorial(n-1); |
||
} |
} |
||
</ |
</lang> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
The C versions work unchanged with C++, however, here is another possibility using the STL and boost: |
The C versions work unchanged with C++, however, here is another possibility using the STL and boost: |
||
<cpp> |
<lang cpp> |
||
#include <boost/iterator/counting_iterator.hpp> |
#include <boost/iterator/counting_iterator.hpp> |
||
#include <algorithm> |
#include <algorithm> |
||
Line 260: | Line 260: | ||
return std::accumulate(boost::counting_iterator<int>(1), boost::counting_iterator<int>(n+1), 1, std::multiplies<int>()); |
return std::accumulate(boost::counting_iterator<int>(1), boost::counting_iterator<int>(n+1), 1, std::multiplies<int>()); |
||
} |
} |
||
</ |
</lang> |
||
=={{header|Common Lisp}}== |
|||
''Warning: Written without an interpreter available. May have mismatched parentheses.'' |
|||
<lang lisp> |
|||
(defun fact(n) |
|||
(cond (or (= n 1) (= n 0)) |
|||
(1) |
|||
(t |
|||
(* n (fact(- n 1)))) |
|||
) |
|||
) |
|||
</lang> |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
: fac ( n -- n! ) 1 swap 1+ 1 ?do i * loop ; |
: fac ( n -- n! ) 1 swap 1+ 1 ?do i * loop ; |
||
Line 271: | Line 281: | ||
{{works with|Fortran|77 and later}} |
{{works with|Fortran|77 and later}} |
||
<lang fortran> |
|||
<pre> |
|||
INTEGER FUNCTION FACT(N) |
INTEGER FUNCTION FACT(N) |
||
INTEGER N, I |
INTEGER N, I |
||
Line 280: | Line 290: | ||
RETURN |
RETURN |
||
END |
END |
||
</ |
</lang> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 306: | Line 316: | ||
! 8 0.8 _0.8 NB. Generalizes as the gamma function |
! 8 0.8 _0.8 NB. Generalizes as the gamma function |
||
40320 0.931384 4.59084 |
40320 0.931384 4.59084 |
||
! 800x NB. Also |
! 800x NB. Also arbitrarily large |
||
7710530113353860041446393977750283605955564018160102391634109940339708518270930693670907697955390330926478612242306774446597851526397454014801846531749097625044706382742591201733097017026108750929188168469858421505936237186038616420630788341172340985137252... |
7710530113353860041446393977750283605955564018160102391634109940339708518270930693670907697955390330926478612242306774446597851526397454014801846531749097625044706382742591201733097017026108750929188168469858421505936237186038616420630788341172340985137252... |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
===Iterative=== |
===Iterative=== |
||
< |
<lang java5>public static long fact(int n){ |
||
if(n < 0){ |
if(n < 0){ |
||
System.err.println("No negative numbers"); |
System.err.println("No negative numbers"); |
||
Line 321: | Line 331: | ||
} |
} |
||
return ans; |
return ans; |
||
}</ |
}</lang> |
||
===Recursive=== |
===Recursive=== |
||
< |
<lang java5>public static long fact(int n){ |
||
if(n < 0){ |
if(n < 0){ |
||
System.err.println("No negative numbers"); |
System.err.println("No negative numbers"); |
||
Line 330: | Line 340: | ||
if(n == 0) return 1; |
if(n == 0) return 1; |
||
return n * fact(n-1); |
return n * fact(n-1); |
||
}</ |
}</lang> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
<javascript>function factorial(n) { |
<lang javascript>function factorial(n) { |
||
return n<2 ? 1 : n * factorial(n-1); |
return n<2 ? 1 : n * factorial(n-1); |
||
}</ |
}</lang> |
||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
Line 346: | Line 356: | ||
Note that Mathematica already comes with a factorial function, which can be used as e.g. <code>5!</code> (gives 120). So the following implementations are only of pedagogical value. |
Note that Mathematica already comes with a factorial function, which can be used as e.g. <code>5!</code> (gives 120). So the following implementations are only of pedagogical value. |
||
=== Recursive === |
=== Recursive === |
||
<lang mathematica> |
|||
<pre> |
|||
factorial[n_Integer] := n*factorial[n-1] |
factorial[n_Integer] := n*factorial[n-1] |
||
factorial[0] = 1 |
factorial[0] = 1 |
||
</ |
</lang> |
||
=== Iterative (direct loop) === |
=== Iterative (direct loop) === |
||
<lang mathematica> |
|||
<pre> |
|||
factorial[n_Integer] := |
factorial[n_Integer] := |
||
Block[{i, result = 1}, For[i = 1, i <= n, ++i, result *= i]; result] |
Block[{i, result = 1}, For[i = 1, i <= n, ++i, result *= i]; result] |
||
</ |
</lang> |
||
=== Iterative (list) === |
=== Iterative (list) === |
||
<pre> |
<pre> |
||
Line 369: | Line 379: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
===Recursive=== |
===Recursive=== |
||
<ocaml>let rec factorial n = |
<lang ocaml>let rec factorial n = |
||
if n <= 0 then 1 |
if n <= 0 then 1 |
||
else n * factorial (n-1)</ |
else n * factorial (n-1)</lang> |
||
The following is tail-recursive, so it is effectively iterative: |
The following is tail-recursive, so it is effectively iterative: |
||
<ocaml>let factorial n = |
<lang ocaml>let factorial n = |
||
let rec loop i accum = |
let rec loop i accum = |
||
if i > n then accum |
if i > n then accum |
||
else loop (i + 1) (accum * i) |
else loop (i + 1) (accum * i) |
||
in loop 1 1</ |
in loop 1 1</lang> |
||
===Iterative=== |
===Iterative=== |
||
It can be done using explicit state, but this is usually discouraged in a functional language: |
It can be done using explicit state, but this is usually discouraged in a functional language: |
||
<ocaml>let factorial n = |
<lang ocaml>let factorial n = |
||
let result = ref 1 in |
let result = ref 1 in |
||
for i = 1 to n do |
for i = 1 to n do |
||
result := !result * i |
result := !result * i |
||
done; |
done; |
||
!result</ |
!result</lang> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
=== Iterative === |
=== Iterative === |
||
<pascal> |
<lang pascal> |
||
function factorial(n: integer): integer; |
function factorial(n: integer): integer; |
||
var |
var |
||
Line 401: | Line 411: | ||
factorial := result |
factorial := result |
||
end; |
end; |
||
</ |
</lang> |
||
=== Recursive === |
=== Recursive === |
||
<pascal> |
<lang pascal> |
||
function factorial(n: integer): integer; |
function factorial(n: integer): integer; |
||
begin |
begin |
||
Line 413: | Line 423: | ||
factorial := n*factorial(n-1) |
factorial := n*factorial(n-1) |
||
end; |
end; |
||
</ |
</lang> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
=== Iterative === |
=== Iterative === |
||
<perl>sub factorial |
<lang perl>sub factorial |
||
{ |
{ |
||
my $n = shift; |
my $n = shift; |
||
Line 426: | Line 436: | ||
}; |
}; |
||
$result; |
$result; |
||
}</ |
}</lang> |
||
=== Recursive === |
=== Recursive === |
||
<perl>sub factorial |
<lang perl>sub factorial |
||
{ |
{ |
||
my $n = shift; |
my $n = shift; |
||
($n == 0)? 1 : $n*factorial($n-1); |
($n == 0)? 1 : $n*factorial($n-1); |
||
}</ |
}</lang> |
||
=== Functional === |
=== Functional === |
||
<perl>use List::Util qw(reduce); |
<lang perl>use List::Util qw(reduce); |
||
sub factorial |
sub factorial |
||
{ |
{ |
||
my $n = shift; |
my $n = shift; |
||
reduce { $a * $b } 1, 1 .. $n |
reduce { $a * $b } 1, 1 .. $n |
||
}</ |
}</lang> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Iterative=== |
===Iterative=== |
||
<python>def factorial(n): |
<lang python>def factorial(n): |
||
if n == 0: |
if n == 0: |
||
return 1 |
return 1 |
||
Line 451: | Line 461: | ||
z=z*n |
z=z*n |
||
return z |
return z |
||
</ |
</lang> |
||
====Functional==== |
====Functional==== |
||
<python>from operator import mul |
<lang python>from operator import mul |
||
def factorial(n): |
def factorial(n): |
||
return reduce(mul, xrange(1,n+1), 1) |
return reduce(mul, xrange(1,n+1), 1) |
||
</ |
</lang> |
||
Sample output: |
Sample output: |
||
<python> |
<lang python> |
||
>>> for i in range(6): |
>>> for i in range(6): |
||
print i, factorial(i) |
print i, factorial(i) |
||
Line 472: | Line 482: | ||
5 120 |
5 120 |
||
>>> |
>>> |
||
</ |
</lang> |
||
===Numerical Approximation=== |
===Numerical Approximation=== |
||
The following sample uses Lanczos approximation from |
The following sample uses Lanczos approximation from [[wp:Lanczos_approximation]] |
||
<python> |
<lang python> |
||
from cmath import * |
from cmath import * |
||
Line 504: | Line 514: | ||
for i in range(10): |
for i in range(10): |
||
print "factorial(%d)=%s"%(i,factorial(i)) |
print "factorial(%d)=%s"%(i,factorial(i)) |
||
</ |
</lang> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 520: | Line 530: | ||
</pre> |
</pre> |
||
===Recursive=== |
===Recursive=== |
||
<python>def factorial(n): |
<lang python>def factorial(n): |
||
z=1 |
z=1 |
||
if n>1: |
if n>1: |
||
z=n*factorial(n-1) |
z=n*factorial(n-1) |
||
return z |
return z |
||
</ |
</lang> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
===Recursive=== |
===Recursive=== |
||
< |
<slang cheme>(define (factorial n) |
||
(if (<= n 0) |
(if (<= n 0) |
||
1 |
1 |
||
(* n factorial (- n 1))))</ |
(* n factorial (- n 1))))</lang> |
||
The following is tail-recursive, so it is effectively iterative: |
The following is tail-recursive, so it is effectively iterative: |
||
<scheme>(define (factorial n) |
<lang scheme>(define (factorial n) |
||
(let loop ((i 1) |
(let loop ((i 1) |
||
(accum 1)) |
(accum 1)) |
||
(if (> i n) |
(if (> i n) |
||
accum |
accum |
||
(loop (+ i 1) (* accum i)))))</ |
(loop (+ i 1) (* accum i)))))</lang> |
||
===Iterative=== |
===Iterative=== |
||
<scheme>(define (factorial n) |
<lang scheme>(define (factorial n) |
||
(do ((i 1 (+ i 1)) |
(do ((i 1 (+ i 1)) |
||
(accum 1 (* accum i))) |
(accum 1 (* accum i))) |
||
((> i n) accum)))</ |
((> i n) accum)))</lang> |
||
=={{header|UNIX Shell}}== |
=={{header|UNIX Shell}}== |
Revision as of 19:39, 30 January 2009
You are encouraged to solve this task according to the task description, using any language you may know.
The Factorial Function of a positive integer, n, is defined as the product of the sequence n, n-1, n-2, ...1 and the factorial of zero, 0, is defined as being 1.
Write a function to return the factorial of a number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion). Support for trapping negative n errors is optional.
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
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
# 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
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 ;
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>
Befunge
&1\> :v v *< ^-1:_$>\:| @.$<
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>
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>
Common Lisp
Warning: Written without an interpreter available. May have mismatched parentheses. <lang lisp> (defun fact(n) (cond (or (= n 1) (= n 0)) (1) (t (* n (fact(- n 1)))) ) ) </lang>
Forth
: fac ( n -- n! ) 1 swap 1+ 1 ?do i * loop ;
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>
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
J
Operator
! 8 NB. Built in factorial operator 40320
Iterative / Functional
*/1+i.8 40320
Recursive
(*$:@:<:)^:(1&<) 8 40320
Generalization
Factorial, like all J's primitives, is generalized:
! 8 0.8 _0.8 NB. Generalizes as the gamma function 40320 0.931384 4.59084 ! 800x NB. Also arbitrarily large 7710530113353860041446393977750283605955564018160102391634109940339708518270930693670907697955390330926478612242306774446597851526397454014801846531749097625044706382742591201733097017026108750929188168469858421505936237186038616420630788341172340985137252...
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
<lang javascript>function factorial(n) {
return n<2 ? 1 : n * factorial(n-1);
}</lang>
Logo
to factorial :n if :n < 2 [output 1] output :n * factorial :n-1 end
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}]]
Nial
(from Nial help file)
fact is recur [ 0 =, 1 first, pass, product, -1 +]
Using it
|fact 4 =24
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>
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;
}</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>
Python
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>
Scheme
Recursive
<slang cheme>(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>
UNIX Shell
fact () { if [ $1 -eq 0 ]; then echo 1; else echo $(($1 * $(fact $(($1-1)) ) )); fi; }