Factorial
From Rosetta Code
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.
[edit] 0815
This is an iterative solution which outputs the factorial of each number supplied on standard input.
}:r: Start reader loop.
|~ Read n,
#:end: if n is 0 terminates
>= enqueue it as the initial product, reposition.
}:f: Start factorial loop.
x<:1:x- Decrement n.
{=*> Dequeue product, position n, multiply, update product.
^:f:
{+% Dequeue incidental 0, add to get Y into Z, output fac(n).
<:a:~$ Output a newline.
^:r:
- Output:
seq 6 | 0815 fac.0 1 2 6 18 78 2d0
[edit] ABAP
[edit] 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.
[edit] 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.
[edit] ActionScript
[edit] 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;
}
[edit] Recursive
public static function factorial(n:int):int
{
if (n < 0)
return 0;
if (n == 0)
return 1;
return n * factorial(n - 1);
}
[edit] Ada
[edit] 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;
[edit] 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;
[edit] 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)
[edit] Aime
[edit] Iterative
integer
factorial(integer n)
{
integer i, result;
result = 1;
i = 1;
while (i < n) {
i += 1;
result *= i;
}
return result;
}
[edit] ALGOL 68
[edit] Iterative
PROC factorial = (INT upb n)LONG LONG INT:(
LONG LONG INT z := 1;
FOR n TO upb n DO z *:= n OD;
z
); ~
[edit] Numerical Approximation
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
[edit] 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
; ~
[edit] 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
[edit] AppleScript
[edit] 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
[edit] Recursive
on factorial(x)
if x < 0 then return 0
if x > 1 then return x * (my factorial(x - 1))
return 1
end factorial
[edit] AutoHotkey
[edit] Iterative
MsgBox % factorial(4)
factorial(n)
{
result := 1
Loop, % n
result *= A_Index
Return result
}
[edit] Recursive
MsgBox % factorial(4)
factorial(n)
{
return n > 1 ? n-- * factorial(n) : 1
}
[edit] AutoIt
[edit] 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
[edit] 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
[edit] 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
}
[edit] Babel
main:
{ argv 0 th $d
fac
%d cr << }
fac!:
{ dup zero?
{ dup one?
{ cp 1 - fac * }
{ zap 1 }
if }
{ zap 1 }
if }
one?! : { 1 = }
zero?!: { 0 = }
[edit] BASIC
[edit] Iterative
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
[edit] Recursive
FUNCTION factorial (n AS Integer) AS Integer
IF n < 2 THEN
factorial = 1
ELSE
factorial = n * factorial(n-1)
END IF
END FUNCTION
[edit] BASIC256
function factorial(n)
factorial = 1
if n>0 then
for p=1 to n
factorial *= p
next p
end if
end function
[edit] 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
[edit] BBC BASIC
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
[edit] bc
#! /usr/bin/bc -q
define f(x) {
if (x <= 1) return (1); return (f(x-1) * x)
}
f(1000)
quit
[edit] Befunge
&1\> :v v *<
^-1:_$>\:|
@.$<
[edit] 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
[edit] Brainf***
Prints sequential factorials in an infinite loop.
>++++++++++>>>+>+[>>>+[-[<<<<<[+<<<<<]>>[[-]>[<<+>+>-]<[>+<-]<[>+<-[>+<-[>
+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>>>>+>+<<<<<<-[>+<-]]]]]]]]]]]>[<+>-
]+>>>>>]<<<<<[<<<<<]>>>>>>>[>>>>>]++[-<<<<<]>>>>>>-]+>>>>>]<[>++<-]<<<<[<[
>+<-]<<<<]>>[->[-]++++++[<++++++++>-]>>>>]<<<<<[<[>+>+<<-]>.<<<<<]>.>>>>]
[edit] Brat
factorial = { x |
true? x == 0 1 { x * factorial(x - 1)}
}
[edit] Burlesque
Using the builtin Factorial function:
blsq ) 6?!
720
Burlesque does not have functions nor is it iterative. Burlesque's strength are its implicit loops.
Following examples display other ways to calculate the factorial function:
blsq ) 1 6r@pd
720
blsq ) 1 6r@{?*}r[
720
blsq ) 2 6r@(.*)\/[[1+]e!.*
720
blsq ) 1 6r@p^{.*}5E!
720
blsq ) 6ropd
720
blsq ) 7ro)(.*){0 1 11}die!
720
[edit] C
[edit] Iterative
int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; ++i)
result *= i;
return result;
}
[edit] Recursive
int factorial(int n) {
return n == 0 ? 1 : n * factorial(n - 1);
}
[edit] 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);
}
[edit] 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>());
}
[edit] 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;
}
[edit] 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
}
[edit] C#
[edit] 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));
}
}
[edit] 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));
}
}
[edit] 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));
}
}
[edit] 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));
}
}
[edit] Cat
Taken direct from the Cat manual:
define rec_fac
{ dup 1 <= [pop 1] [dec rec_fac *] if }
[edit] 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.
[edit] 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
}
[edit] 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))))))
[edit] Clojure
[edit] Folding
(defn factorial [x]
(apply * (range 2 (inc x))))
[edit] Recursive
(defn factorial [x]
(if (< x 2)
1
(* x (factorial (dec x)))))
[edit] Tail recursive
(defn factorial [x]
(loop [x x
acc 1]
(if (< x 2)
acc
(recur (dec x) (* acc x)))))
[edit] 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}")
[edit] 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)))
[edit] CoffeeScript
Several solutions are possible in JavaScript:
[edit] Recursive
fac = (n) ->
if n <= 1
1
else
n * fac n-1
[edit] Functional
(See MDC)fac = (n) ->
[1..n].reduce (x,y) -> x*y
[edit] D
import std.stdio, std.algorithm, std.metastrings, std.range;
// iterative
long factorial(long n) {
long result = 1;
foreach (i; 1 .. n + 1)
result *= i;
return result;
}
// recursive
long recFactorial(long n) {
if (n == 0)
return 1;
else
return n * recFactorial(n - 1);
}
// functional-style
long fact(long n) {
return iota(1, n + 1).reduce!q{a * b}();
}
// tail recursive (at run-time, with DMD)
long tfactorial(long n) {
static long facAux(long n, long 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));
}
Compile-time output
1307674368000 1307674368000 1307674368000 1307674368000
Run-time output
1307674368000 1307674368000 1307674368000 1307674368000
[edit] Dart
[edit] 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));
}
[edit] 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));
}
[edit] 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
[edit] Delphi
[edit] 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.
[edit] 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.
[edit] 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.
[edit] DWScript
Note that Factorial is part of the standard DWScript maths functions.
[edit] Iterative
function IterativeFactorial(n : Integer) : Integer;
var
i : Integer;
begin
Result := 1;
for i := 2 to n do
Result *= i;
end;
[edit] Recursive
function RecursiveFactorial(n : Integer) : Integer;
begin
if n>1 then
Result := RecursiveFactorial(n-1)*n
else Result := 1;
end;
[edit] Dylan
define method factorial(n)
reduce1(\*, range(from: 1, to: n));
end
[edit] E
pragma.enable("accumulator")
def factorial(n) {
return accum 1 for i in 2..n { _ * i }
}
[edit] Eiffel
note
description: "recursive and iterative factorial example of a positive integer."
class
FACTORIAL_EXAMPLE
create
make
feature -- Initialization
make
local
n: NATURAL
do
n := 5
print ("%NFactorial of " + n.out + " = ")
print (recursive_factorial (n))
end
feature -- Access
recursive_factorial (n: NATURAL): NATURAL
-- factorial of 'n'
do
if n = 0 then
Result := 1
else
Result := n * recursive_factorial (n - 1)
end
end
iterative_factorial (n: NATURAL): NATURAL
-- factorial of 'n'
local
v: like n
do
from
Result := 1
v := n
until
v <= 1
loop
Result := Result * v
v := v - 1
end
end
end
[edit] Ela
Tail recursive version:
fact = fact' 1L
where fact' acc 0 = acc
fact' acc n = fact' (n * acc) (n - 1)
[edit] 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))))))
The calc package (which comes with Emacs) has a builtin fact(). It automatically uses the bignums implemented by calc.
(require 'calc)
(calc-eval "fact(30)")
=>
"265252859812191058636308480000000"
[edit] 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).
[edit] Euphoria
Straight forward methods
[edit] Iterative
function factorial(integer n)
atom f = 1
while n > 1 do
f *= n
n -= 1
end while
return f
end function
[edit] Recursive
function factorial(integer n)
if n > 1 then
return factorial(n-1) * n
else
return 1
end if
end function
[edit] Tail Recursive
function factorial(integer n, integer acc = 1)
if n <= 0 then
return acc
else
return factorial(n-1, n*acc)
end if
end function
[edit] 'Paper tape' / Virtual Machine version
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
[edit] EGL
[edit] Iterative
function fact(n int in) returns (bigint)
if (n < 0)
writestdout("No negative numbers");
return (0);
end
ans bigint = 1;
for (i int from 1 to n)
ans *= i;
end
return (ans);
end
[edit] Recursive
function fact(n int in) returns (bigint)
if (n < 0)
SysLib.writeStdout("No negative numbers");
return (0);
end
if (n < 2)
return (1);
else
return (n * fact(n - 1));
end
end
[edit] 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
[edit] Factor
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.
[edit] FALSE
[1\[$][$@*\1-]#%]f:
^'0- f;!.
Recursive:
[$1=~[$1-f;!*]?]f:
[edit] 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
}
[edit] 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))
}
}
[edit] Forth
: fac ( n -- n! ) 1 swap 1+ 1 ?do i * loop ;
[edit] Fortran
[edit] Fortran 90
A simple one-liner is sufficient
nfactorial = PRODUCT((/(i, i=1,n)/))
[edit] FORTRAN 77
FUNCTION FACT(N)
INTEGER N,I,FACT
FACT=1
DO 10 I=1,N
10 FACT=FACT*I
END
[edit] FPr
FP-Way
fact==((1&),iota)\(1*2)&
Recursive
fact==(id<=1&)->(1&);id*fact°id-1&
[edit] GAP
# Built-in
Factorial(5);
# An implementation
fact := n -> Product([1 .. n]);
[edit] Genyris
def factorial (n)
if (< n 2) 1
* n
factorial (- n 1)
[edit] GML
n = argument0
j = 1
for(i = 1; i <= n; i += 1)
j *= i
return j
[edit] gnuplot
Gnuplot has a builtin ! factorial operator for use on integers.
set xrange [0:4.95]
set key left
plot int(x)!
If you wanted to write your own it can be done recursively.
# Using int(n) allows non-integer "n" inputs with the factorial
# calculated on int(n) in that case.
# Arranging the condition as "n>=2" avoids infinite recursion if
# n==NaN, since any comparison involving NaN is false. Could change
# "1" to an expression like "n*0+1" to propagate a NaN input to the
# output too, if desired.
#
factorial(n) = (n >= 2 ? int(n)*factorial(n-1) : 1)
set xrange [0:4.95]
set key left
plot factorial(x)
[edit] Golfscript
Iterative (uses folding)
{.!{1}{,{)}%{*}*}if}:fact;
5fact puts # test
or
{),(;{*}*}:fact;
Recursive
{.1<{;1}{.(fact*}if}:fact;
[edit] 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.
[edit] Groovy
[edit] 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
[edit] 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
[edit] 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)
Tail-recursive, checking the negative case:
fac n
| n >= 0 = go 1 n
| otherwise = error "Negative factorial!"
where go acc 0 = acc
go acc n = go (acc * n) (n - 1)
[edit] HicEst
WRITE(Clipboard) factorial(6) ! pasted: 720
FUNCTION factorial(n)
factorial = 1
DO i = 2, n
factorial = factorial * i
ENDDO
END
[edit] Icon and Unicon
[edit] 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
[edit] Iterative
The 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
[edit] IDL
function fact,n
return, product(lindgen(n)+1)
end
[edit] Inform 6
[ factorial n;
if(n == 0)
return 1;
else
return n * factorial(n - 1);
];
[edit] Io
Facorials are built-in to Io:
3 factorial
[edit] J
[edit] Operator
! 8 NB. Built in factorial operator
40320
[edit] Iterative / Functional
*/1+i.8
40320
[edit] Recursive
(*$:@:<:)^:(1&<) 8
40320
[edit] 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...
[edit] Java
[edit] 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;
}
[edit] 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);
}
[edit] JavaScript
Several solutions are possible in JavaScript:
[edit] Iterative
function factorial(n) {
var x = 1;
for (var i = 2; i <= n; i++) {
x *= i;
}
return x;
}
[edit] Recursive
function factorial(n) {
return n < 2 ? 1 : n * factorial(n - 1);
}
[edit] Functional
(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);
}
[edit] Joy
DEFINE factorial == [0 =] [pop 1] [dup 1 - factorial *] ifte.
[edit] Julia
This is just a copy from the combinatorics.jl module of the Julia standard library
function factorial(n::Integer)
if n < 0
return zero(n)
end
f = one(n)
for i = 2:n
f *= i
end
return f
end
- Output:
julia> for i = 10:20 println(factorial(BigInt(i))) end 3628800 39916800 479001600 6227020800 87178291200 1307674368000 20922789888000 355687428096000 6402373705728000 121645100408832000 2432902008176640000
[edit] K
[edit] Iterative
facti:*/1+!:
facti 5
120
[edit] Recursive
factr:{:[x>1;x*_f x-1;1]}
factr 6
720
[edit] 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;
}
[edit] Lang5
[edit] Folding
: fact iota 1 + '* reduce ;
5 fact
120
[edit] Recursive
: fact dup 2 < if else dup 1 - fact * then ;
5 fact
120
[edit] LFE
(defun fac (n)
(cond
((== n 0) 1)
((> n 0) (* n (fac (- n 1))))))
[edit] 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
[edit] Lisaac
- factorial x : INTEGER : INTEGER <- (
+ result : INTEGER;
(x <= 1).if {
result := 1;
} else {
result := x * factorial(x - 1);
};
result
);
[edit] Logo
[edit] Recursive
to factorial :n
if :n < 2 [output 1]
output :n * factorial :n-1
end
[edit] 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
[edit] Lua
[edit] Recursive
function fact(n)
return n > 0 and n * fact(n-1) or 1
end
[edit] Tail Recursive
function fact(n, acc)
acc = acc or 1
if n == 0 then
return acc
end
return fact(n-1, n*acc)
end
[edit] M4
define(`factorial',`ifelse(`$1',0,1,`eval($1*factorial(decr($1)))')')dnl
dnl
factorial(5)
Output:
120
[edit] Maple
Builtin
> 5!;
120
Recursive
RecFact := proc( n :: nonnegint )
if n = 0 or n = 1 then
1
else
n * thisproc( n - 1 )
end if
end proc:
> seq( RecFact( i ) = i!, i = 0 .. 10 );
1 = 1, 1 = 1, 2 = 2, 6 = 6, 24 = 24, 120 = 120, 720 = 720, 5040 = 5040,
40320 = 40320, 362880 = 362880, 3628800 = 3628800
Iterative
IterFact := proc( n :: nonnegint )
local i;
mul( i, i = 2 .. n )
end proc:
> seq( IterFact( i ) = i!, i = 0 .. 10 );
1 = 1, 1 = 1, 2 = 2, 6 = 6, 24 = 24, 120 = 120, 720 = 720, 5040 = 5040,
40320 = 40320, 362880 = 362880, 3628800 = 3628800
[edit] 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.
[edit] Recursive
factorial[n_Integer] := n*factorial[n-1]
factorial[0] = 1
[edit] Iterative (direct loop)
factorial[n_Integer] :=
Block[{i, result = 1}, For[i = 1, i <= n, ++i, result *= i]; result]
[edit] Iterative (list)
factorial[n_Integer] := Block[{i}, Times @@ Table[i, {i, n}]]
[edit] MATLAB
[edit] 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)
[edit] Recursive
function f=fac(n)
if n==0
f=1;
return
else
f=n*fac(n-1);
end
[edit] Iterative
A possible iterative solution:
function b=factorial(a)
b=1;
for i=1:a
b=b*i;
end
[edit] Maxima
[edit] Built-in
n!
[edit] Recursive
fact(n) := if n < 2 then 1 else n * fact(n - 1)$
[edit] Iterative
fact2(n) := block([r: 1], for i thru n do r: r * i, r)$
[edit] MAXScript
[edit] Iterative
fn factorial n =
(
if n == 0 then return 1
local fac = 1
for i in 1 to n do
(
fac *= i
)
fac
)
[edit] Recursive
fn factorial_rec n =
(
local fac = 1
if n > 1 then
(
fac = n * factorial_rec (n - 1)
)
fac
)
[edit] Mirah
def factorial_iterative(n:int)
2.upto(n-1) do |i|
n *= i
end
n
end
puts factorial_iterative 10
[edit] МК-61/52
ВП П0 1 ИП0 * L0 03 С/П
[edit] ML/I
[edit] 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)
[edit] 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)
[edit] Modula-3
[edit] 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;
[edit] Recursive
PROCEDURE FactRec(n: CARDINAL): CARDINAL =
VAR result := 1;
BEGIN
IF n > 1 THEN
result := n * FactRec(n - 1);
END;
RETURN result;
END FactRec;
[edit] MUMPS
[edit] 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
[edit] 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
[edit] 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
}
}
[edit] 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)
[edit] newLISP
> (define (factorial n) (exp (gammaln (+ n 1))))
(lambda (n) (exp (gammaln (+ n 1))))
> (factorial 4)
24
[edit] Nial
(from Nial help file)
fact is recur [ 0 =, 1 first, pass, product, -1 +]
Using it
|fact 4
=24
[edit] Niue
[edit] Recursive
[ dup 1 > [ dup 1 - factorial * ] when ] 'factorial ;
( test )
4 factorial . ( => 24 )
10 factorial . ( => 3628800 )
[edit] Objeck
[edit] Iterative
bundle Default {
class Fact {
function : Main(args : String[]) ~ Nil {
5->Factorial()->PrintLine();
}
}
}
[edit] OCaml
[edit] 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
[edit] 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
[edit] 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.
[edit] 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
[edit] Oz
[edit] Folding
fun {Fac1 N}
{FoldL {List.number 1 N 1} Number.'*' 1}
end
[edit] 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
[edit] Iterative
fun {Fac3 N}
Result = {NewCell 1}
in
for I in 1..N do
Result := @Result * I
end
@Result
end
[edit] 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 n2logn bits to compute n!); a machine with 1 GB of RAM and unlimited time could, in theory, find 100,000-digit factorials.
[edit] Recursive
fact(n)=if(n<2,1,n*fact(n-1))
[edit] 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
[edit] 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)
[edit] 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)
[edit] 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!
[edit] Gamma
Note also the presence of factorial and lngamma.
fact(n)=round(gamma(n+1))
[edit] 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]
};
[edit] Pascal
[edit] 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;
[edit] Recursive
function factorial(n: integer): integer;
begin
if n = 0
then
factorial := 1
else
factorial := n*factorial(n-1)
end;
[edit] Perl
[edit] 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;
}
[edit] Recursive
sub factorial
{
my $n = shift;
($n == 0)? 1 : $n*factorial($n-1);
}
[edit] Functional
use List::Util qw(reduce);
sub factorial
{
my $n = shift;
reduce { $a * $b } 1, 1 .. $n
}
[edit] Perl 6
sub postfix:<!> { [*] 1..$^n }
say 5!; #prints 120
[edit] PHP
[edit] Iterative
<?php
function factorial($n) {
if ($n < 0) {
return 0;
}
$factorial = 1;
for ($i = $n; $i >= 1; $i--) {
$factorial = $factorial * $i;
}
return $factorial;
}
?>
[edit] Recursive
<?php
function factorial($n) {
if ($n < 0) {
return 0;
}
if ($n == 0) {
return 1;
}
else {
return $n * factorial($n-1);
}
}
?>
[edit] One-Liner
<?php
function factorial($n) { return $n == 0 ? 1 : array_product(range(1, $n)); }
?>
[edit] Library
Requires the GMP library to be compiled in:
gmp_fact($n)
[edit] PicoLisp
(de fact (N)
(if (=0 N)
1
(* N (fact (dec N))) ) )
or:
(de fact (N)
(apply * (range 1 N) )
[edit] 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
[edit] 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;
[edit] PostScript
[edit] 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
[edit] 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
[edit] Combinator
/myfact {{dup 0 eq} {pop 1} {dup pred} {mul} linrec}.
[edit] 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
[edit] PowerShell
[edit] Recursive
function Get-Factorial ($x) {
if ($x -eq 0) {
return 1
}
return $x * (Get-Factorial ($x - 1))
}
[edit] Iterative
function Get-Factorial ($x) {
if ($x -eq 0) {
return 1
} else {
$product = 1
1..$x | ForEach-Object { $product *= $_ }
return $product
}
}
[edit] Evaluative
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 '*'))
}
[edit] Prolog
[edit] Recursive
fact(X, 1) :- X<2.
fact(X, F) :- Y is X-1, fact(Y,Z), F is Z*X.
[edit] 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).
[edit] 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).
[edit] 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).
[edit] 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)
).
[edit] Protium
Protium has an opcode for factorial so there's not much point coding one.
<@ SAYFCTLIT>5</@>
However, just to prove that it can be done, here's one possible implementation:
<@ DEFUDOLITLIT>FAT|__Transformer|<@ LETSCPLIT>result|1</@><@ ITEFORPARLIT>1|<@ ACTMULSCPPOSFOR>result|...</@></@><@ LETRESSCP>...|result</@></@>
<@ SAYFATLIT>123</@>
[edit] Pure
[edit] Recursive
fact n = n*fact (n-1) if n>0;
= 1 otherwise;
let facts = map fact (1..10); facts;
[edit] Tail Recursive
fact n = loop 1 n with
loop p n = if n>0 then loop (p*n) (n-1) else p;
end;
[edit] PureBasic
[edit] Iterative
Procedure factorial(n)
Protected i, f = 1
For i = 2 To n
f = f * i
Next
ProcedureReturn f
EndProcedure
[edit] Recursive
Procedure Factorial(n)
If n < 2
ProcedureReturn 1
Else
ProcedureReturn n * Factorial(n - 1)
EndIf
EndProcedure
[edit] Python
[edit] Library
import math
math.factorial(n)
[edit] Iterative
def factorial(n):
result = 1
for i in range(1, n+1):
result *= i
return result
[edit] 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
>>>
[edit] 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)
[edit] Recursive
def factorial(n):
z=1
if n>1:
z=n*factorial(n-1)
return z
[edit] Q
[edit] Iterative
[edit] Point-free
f:(*/)1+til@
or
f:(*)over 1+til@
or
f:prd 1+til@
[edit] As a function
f:{(*/)1+til x}
[edit] Recursive
f:{$[x=1;1;x*.z.s x-1]}
[edit] R
[edit] Recursive
fact <- function(n) {
if ( n <= 1 ) 1
else n * fact(n-1)
}
[edit] Iterative
factIter <- function(n) {
f = 1
for (i in 2:n) f <- f * i
f
}
[edit] 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
[edit] Racket
[edit] Recursive
The standard recursive style:
(define (factorial n)
(if (= 0 n)
1
(* n (factorial (- n 1)))))
However, it is inefficient. It's more efficient to use an accumulator.
(define (factorial n)
(define (fact n acc)
(if (= 0 n)
acc
(fact (- n 1) (* n acc))))
(fact n 1))
[edit] Rascal
[edit] Iterative
The standard implementation:
public int factorial_iter(int n){
result = 1;
for(i <- [1..n])
result *= i;
return result;
}
However, Rascal supports an even neater solution. By using a reducer we can write this code on one short line:
public int factorial_iter2(int n) = (1 | it*e | int e <- [1..n]);
Example outputs:
rascal>factorial_iter(10)
int: 3628800
rascal>factorial_iter2(10)
int: 3628800
[edit] Recursive
public int factorial_rec(int n){
if(n>1) return n*factorial_rec(n-1);
else return 1;
}
Example output:
rascal>factorial_rec(10)
int: 3628800
[edit] 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...
[edit] Retro
A recursive implementation from the benchmarking code.
: <factorial> dup 1 = if; dup 1- <factorial> * ;
: factorial dup 0 = [ 1+ ] [ <factorial> ] if ;
[edit] REXX
[edit] simple version
This version of the REXX program calculates the factorial of numbers up to 25,000.
25,000! is exactly 99,094 digits.
Most REXX interpreters can handle eight million digits.
/*REXX program computes the factorial of a non-negative integer. */
numeric digits 100000 /*100k digs: handles N up to 25k.*/
parse arg n /*get argument from command line. */
if n='' then call er 'no argument specified'
if arg()>1 | words(n)>1 then call er 'too many arguments specified.'
if \datatype(n,'N') then call er "argument isn't numeric: " n
if \datatype(n,'W') then call er "argument isn't a whole number: " n
if n<0 then call er "argument can't be negative: " n
!=1 /*define factorial product so far.*/
/*══════════════════════════════════════where da rubber meets da road──┐*/
do j=2 to n; !=!*j /*compute the ! the hard way◄───┘*/
end /*j*/
/*══════════════════════════════════════════════════════════════════════*/
say n'! is ['length(!) "digits]:" /*display # of digits in factorial*/
say /*add some whitespace to output. */
say !/1 /*normalize the factorial product.*/
exit /*stick a fork in it, we're done. */
/*─────────────────────────────────ER subroutine────────────────────────*/
er: say; say '***error!***'; say; say arg(1); say; say; exit 13
output when the input is: 100
100! is [158 digits]: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
[edit] precision autocorrection
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 factorial lengths ───── │
│ │
│ 10 ! = 7 digits │
│ 20 ! = 19 digits │
│ 52 ! = 68 digits │
│ 104 ! = 167 digits │
│ 208 ! = 394 digits │
│ 416 ! = 394 digits (8 deck shoe) │
│ │
│ 1k ! = 2,568 digits │
│ 10k ! = 35,660 digits │
│ 100k ! = 456,574 digits │
│ │
│ 1m ! = 5,565,709 digits │
│ 10m ! = 65,657,060 digits │
│ 100m ! = 756,570,556 digits │
│ │
│ Only one result is shown below for pratical reasons. │
│ │
│ This version of the REXX interpreter is essentially limited │
│ to around 8 million digits, but with some programming │
│ tricks, it could yield a result up to ≈ 16 million digits. │
│ │
│ Also, the Regina REXX interpreter is limited to an exponent │
│ 9 digits, i.e.: 9.999...999e+999999999 │
└────────────────────────────────────────────────────────────────┘ */
numeric digits 99 /*99 digs initially, then expanded*/
numeric form /*exponentiated #s =scientric form*/
parse arg n /*get argument from command line. */
if n='' then call er 'no argument specified'
if arg()>1 | words(n)>1 then call er 'too many arguments specified.'
if \datatype(n,'N') then call er "argument isn't numeric: " n
if \datatype(n,'W') then call er "argument isn't a whole number: " n
if n<0 then call er "argument can't be negative: " n
!=1 /*define factorial product so far.*/
/*══════════════════════════════════════where da rubber meets da road──┐*/
do j=2 to n; !=!*j /*compute the ! the hard way◄───┘*/
if pos('E',!)==0 then iterate /*is ! in exponential notation? */
parse var ! 'E' digs /*pick off the factorial exponent.*/
numeric digits digs+digs%10 /* and incease it by ten percent.*/
end /*j*/
/*══════════════════════════════════════════════════════════════════════*/
say n'! is ['length(!) "digits]:" /*display # of digits in factorial*/
say /*add some whitespace to output. */
say !/1 /*normalize the factorial product.*/
exit /*stick a fork in it, we're done. */
/*─────────────────────────────────ER subroutine────────────────────────*/
er: say; say '***error!***'; say; say arg(1); say; say; exit 13
output when the input is: 1000
1000! is [2568 digits]: 4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048004799886101971960586316668729948085589013238296699445909974245040870737599188236277271887325197795059509952761208749754624970436014182780946464962910563938874378864873371191810458257836478499770124766328898359557354325131853239584630755574091142624174743493475534286465766116677973966688202912073791438537195882498081268678383745597317461360853795345242215865932019280908782973084313928444032812315586110369768013573042161687476096758713483120254785893207671691324484262361314125087802080002616831510273418279777047846358681701643650241536 9139828126481021309276124489635992870511496497541990934222156683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535340819890138544248798495995331910172335555660213945039973628075013783761530712776192684903435262520001588853514733161170210396817592151090778801939317811419454525722386554146106289218796022383897147608850627686296714667469756291123408243920816015378088989396451826324367161676217916890977991190375403127462228998800519544441428201218736174599264295658174662830295557029902432415318161721046583203678690611726015878352075151628422554026517048330422614397428693306169089796848259012 5458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290 1534830776445690990731524332782882698646027898643211390835062170950025973898635542771967428222487575867657523442202075736305694988250879689281627538488633969099598262809561214509948717012445164612603790293091208890869420285106401821543994571568059418727489980942547421735824010636774045957417851608292301353580818400969963725242305608559037006242712434169090041536901059339838357779394109700277534720000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000
[edit] rehydration (trailing zero replacement)
This version of the REXX program takes advantage of the fact that the decimal version of factorials (>4) have trailing zeroes, so
it simply strips them (reducing the magnitude of the factorial).
When the factorial is finished computing, the trailing zeroes are simply concatenated to the (dehydrated) factorial product.
This technique will allow other programs to extend their range, especially those that use decimal or floating point decimal,
but can work with binary numbers as well (albeit you'd most likely have to convert the number to decimal when a multiplier is
a multiple of five [or some other method]), strip the trailing zeroes, and then convert it back to binary).
/*REXX program computes the factorial of a non-negative integer, and */
/* automatically adjusts the number of digits to accommodate the answer.*/
/*This version allows for faster multiplying of #s (no trailing zeros).*/
numeric digits 100 /*start with 100 digits. */
numeric form /*indicates we want scientric form*/
parse arg n .; if n=='' then n=0 /*get argument from command line. */
/*════════════════════════════════════where the rubber meets the road. */
!=1 /*define factorial product so far.*/
do j=2 to n /*compute factorial the hard way. */
o!=! /*save old ! in case of overflow. */
!=!*j /*multiple the factorial with J, */
/* and strip all trailing zeroes. */
if pos('E',!)\==0 then do /*is ! in exponential notation? */
d=digits() /*D is current digs*/
numeric digits d+d%10 /*add ten percent. */
!=o!*j /*recalculate for the lost digit. */
end
!=strip(!,'tail-end',0) /*kill some electrons, strip 0's. */
end /*(above) only 1st letter is used.*/
/*let's perform some housekeeping.*/
if pos('E',!)\==0 then !=strip(!/1,"T",0) /*! in exponential notation?*/
v=5; tz=0
do while v<=n /*calculate # of trailing zeroes. */
tz=tz+n%v
v=v*5
end /*while v≤n*/
!=! || copies(0,tz) /*add some water to rehydrate !. */
/*══════════════════════════════════════════════════════════════════════*/
say n'! is ['length(!) "digits]:" /*display # of digits in factorial*/
say /*add some whitespace to output, */
say ! /* ... and display the ! product.*/
output when the input is: 100
100! is [158 digits]: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
[edit] 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)
[edit] Run BASIC
for i = 0 to 100
print " fctrI(";right$("00";str$(i),2); ") = "; fctrI(i)
print " fctrR(";right$("00";str$(i),2); ") = "; fctrR(i)
next i
end
function fctrI(n)
fctrI = 1
if n >1 then
for i = 2 To n
fctrI = fctrI * i
next i
end if
end function
function fctrR(n)
fctrR = 1
if n > 1 then fctrR = n * fctrR(n -1)
end function
[edit] 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;
[edit] Scala
[edit] Imperative
def factorial(n: Int)={
var res = 1
for(i <- 1 to n)
res *=i
res
}
[edit] Recursive
def factorial(n: Int) = if(n == 0) 1 else n * factorial(n-1)
[edit] Folding
def factorial(n: Int) = (2 to n).foldLeft(1)(_*_)
[edit] 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
[edit] Scheme
[edit] 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)))))
[edit] Iterative
(define (factorial n)
(do ((i 1 (+ i 1))
(accum 1 (* accum i)))
((> i n) accum)))
[edit] 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
[edit] 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:
[edit] 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;
[edit] 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;
[edit] 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
[edit] 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
[edit] Smalltalk
Smalltalk Number class already has a factorial method; however, let's see how we can implement it by ourselves.
[edit] Iterative with fold
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.
[edit] 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)
]
].
[edit] 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.
].
| fac |
fac := [ :n | (1 to: n) inject: 1 into: [ :prod :next | prod * next ] ].
fac value: 10.
"3628800"
[edit] SNOBOL4
Note: Snobol4+ overflows after 7! because of signed short int limitation.
[edit] Recursive
define('rfact(n)') :(rfact_end)
rfact rfact = le(n,0) 1 :s(return)
rfact = n * rfact(n - 1) :(return)
rfact_end
[edit] 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
[edit] 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
[edit] Standard ML
[edit] 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
[edit] Tcl
Use Tcl 8.5 for its built-in arbitrary precision integer support.
[edit] Iterative
proc ifact n {
for {set i $n; set sum 1} {$i >= 2} {incr i -1} {
set sum [expr {$sum * $i}]
}
return $sum
}
[edit] 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)}}
[edit] 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
}
[edit] 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
[edit] Using the Γ Function
Note that this only works correctly for factorials that produce correct representations in double precision floating-point numbers.
package require math::special
proc gfact n {
expr {round([::math::special::Gamma [expr {$n+1}]])}
}
[edit] 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: 
[edit] TorqueScript
[edit] Iterative
function Factorial(%num)
{
if(%num < 2)
return 1;
for(%a = %num-1; %a > 1; %a--)
%num *= %a;
return %num;
}
[edit] Recursive
function Factorial(%num)
{
if(%num < 2)
return 1;
return %num * Factorial(%num-1);
}
[edit] 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
[edit] UNIX Shell
[edit] Iterative
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:
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 19as an integer, printsfactorial 20in floating-point exponential format.
[edit] Recursive
These solutions fork many processes, because each level of recursion spawns a subshell to capture the output.
factorial ()
{
if [ $1 -eq 0 ]
then echo 1
else echo $(($1 * $(factorial $(($1-1)) ) ))
fi
}
Or in Korn style:
function factorial {
typeset n=$1
(( n < 2 )) && echo 1 && return
echo $(( n * $(factorial $((n-1))) ))
}
[edit] 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
[edit] 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>
[edit] 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
[edit] Wrapl
[edit] Product
DEF fac(n) n <= 1 | PROD 1:to(n);
[edit] Recursive
DEF fac(n) n <= 0 => 1 // n * fac(n - 1);
[edit] Folding
DEF fac(n) n <= 1 | :"*":foldl(ALL 1:to(n));
[edit] x86 Assembly
[edit] 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
[edit] 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
[edit] 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
[edit] XL
0! -> 1
N! -> N * (N-1)!
[edit] XPL0
func FactIter(N); \Factorial of N using iterative method
int N; \range: 0..12
int F, I;
[F:= 1;
for I:= 2 to N do F:= F*I;
return F;
];
func FactRecur(N); \Factorial of N using recursive method
int N; \range: 0..12
return if N<2 then 1 else N*FactRecur(N-1);
[edit] ZX Spectrum Basic
[edit] Iterative
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
[edit] Recursive
Using VAL for delayed evaluation and AND's ability to return given string or empty, we can now control the program flow within an expression in a manner akin to LISP's cond:
DEF FN f(n) = VAL (("1" AND n<=0) + ("n*FN f(n-1)" AND n>0))
But, truth be told, the parameter n does not withstand recursive calling. Changing the order of the product gives naught:
DEF FN f(n) = VAL (("1" AND n<=0) + ("FN f(n-1)*n" AND n>0))
Categories:
- Programming Tasks
- Arithmetic operations
- Recursion
- Memoization
- Classic CS problems and programs
- Arithmetic
- 0815
- ABAP
- ActionScript
- Ada
- Aime
- ALGOL 68
- AmigaE
- AppleScript
- AutoHotkey
- AutoIt
- AWK
- Babel
- BASIC
- BASIC256
- Batch File
- BBC BASIC
- Bc
- Befunge
- Bracmat
- Brainf***
- Brat
- Burlesque
- C
- C++
- C sharp
- Cat
- Chef
- Clay
- CLIPS
- Clojure
- CMake
- Common Lisp
- CoffeeScript
- D
- Dart
- Dc
- Delphi
- DWScript
- Dylan
- E
- Eiffel
- Ela
- Emacs Lisp
- Erlang
- Euphoria
- EGL
- F Sharp
- Factor
- FALSE
- Fancy
- Fantom
- Forth
- Fortran
- FPr
- GAP
- Genyris
- GML
- Gnuplot
- Golfscript
- Go
- Groovy
- Haskell
- HicEst
- Icon
- Unicon
- Icon Programming Library
- IDL
- Inform 6
- Io
- J
- Java
- JavaScript
- Joy
- Julia
- K
- KonsolScript
- Lang5
- LFE
- Liberty BASIC
- Lisaac
- Logo
- Lua
- M4
- Maple
- Mathematica
- MATLAB
- Maxima
- MAXScript
- Mirah
- МК-61/52
- ML/I
- Modula-3
- MUMPS
- Nemerle
- NetRexx
- NewLISP
- Nial
- Niue
- Objeck
- OCaml
- Octave
- Order
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- Piet
- PL/I
- PostScript
- Initlib
- PowerBASIC
- PowerShell
- Prolog
- Protium
- Pure
- PureBasic
- Python
- Q
- R
- Racket
- Rascal
- REBOL
- Retro
- REXX
- Ruby
- Run BASIC
- Sather
- Scala
- Scheme
- Seed7
- Sisal
- Slate
- Smalltalk
- SNOBOL4
- Standard ML
- Tcl
- Tcllib
- TI-89 BASIC
- TorqueScript
- TUSCRIPT
- UNIX Shell
- C Shell
- Ursala
- VBScript
- Wrapl
- X86 Assembly
- XL
- XPL0
- ZX Spectrum Basic
