Factorial: Difference between revisions
Line 844: | Line 844: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Library=== |
|||
{{works with|Python|2.6+, 3.x}} |
|||
<lang python>import math |
|||
math.factorial(n)</lang> |
|||
===Iterative=== |
===Iterative=== |
||
<lang python>def factorial(n): |
<lang python>def factorial(n): |
Revision as of 18:18, 15 October 2009
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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 ;
AmigaE
Recursive solution: <lang amigae>PROC fact(x) IS IF x>=2 THEN x*fact(x-1) ELSE 1
PROC main()
WriteF('5! = \d\n', fact(5))
ENDPROC</lang>
Iterative: <lang amigae>PROC fact(x)
DEF r, y IF x < 2 THEN RETURN 1 r := 1; y := x; FOR x := 2 TO y DO r := r * x
ENDPROC r</lang>
AutoHotkey
Iterative
<lang AutoHotkey> MsgBox % factorial(4)
factorial(n) {
result := 1 Loop, % n result *= A_Index Return result
} </lang>
AWK
Recursive <lang awk>function fact_r(n) {
if ( n <= 1 ) return 1; return n*fact_r(n-1);
}</lang>
Iterative <lang awk>function fact(n) {
if ( n < 1 ) return 1; r = 1 for(m = 2; m <= n; m++) { r *= m; } return r
}</lang>
BASIC
Iterative
<lang freebasic> FUNCTION factorial (n AS Integer) AS Integer
DIM f AS Integer, i AS Integer f = 1 FOR i = 2 TO n f = f*i NEXT i factorial = f
END FUNCTION </lang>
Recursive
<lang freebasic> FUNCTION factorial (n AS Integer) AS Integer
IF n < 2 THEN factorial = 1 ELSE factorial = n * factorial(n-1) END IF
END FUNCTION </lang>
bc
#! /usr/bin/bc -q define f(x) { if (x <= 1) return (1); return (f(x-1) * x); } f(1000) quit
Befunge
&1\> :v v *< ^-1:_$>\:| @.$<
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>
C#
Recursive
<lang csharp>using System;
class Program {
static long fact(int n) { if (n == 0) return 1; return n * fact(n - 1); }
static void Main(string[] args) { Console.WriteLine(fact(5)); //Example }
}</lang>
Clojure
<lang clojure> (defn factorial [x]
(apply * (range 2 (inc x)))
) </lang>
Common Lisp
Recursive: <lang lisp>(defun fact (n)
(if (< n 2) 1 (* n (fact(- n 1))) )
)</lang>
Iterative: <lang lisp>(defun factorial (n)
"Calculates N!" (loop for result = 1 then (* result i) for i from 2 to n finally (return result)))</lang>
D
D solution would be similar to C version, but the most known example for factorial is the one using templates calculated during compilation. pragma() compiler directive is used to print calculated value.
<lang D> template itoa(ulong i) {
static if (i < 10) const char[] itoa = "" ~ cast(char)(i + '0'); else const char[] itoa = itoa!(i / 10) ~ itoa!(i % 10);
}
template factorial(uint n) {
static assert(n < 21, "too much for me"); static if (n == 1) const ulong factorial = 1; else const ulong factorial = n * factorial!(n-1);
}
pragma (msg, itoa!(factorial!(20)));
void main() {} </lang>
E
<lang e>pragma.enable("accumulator") def factorial(n) {
return accum 1 for i in 2..n { _ * i }
}</lang>
Erlang
With a fold: <lang erlang> lists:foldl(fun(X,Y) -> X*Y end, 1, lists:seq(1,N)). </lang>
With a recursive function: <lang erlang> fac(1) -> 1; fac(N) -> N * fac(N-1).</lang>
With a tail-recursive function: <lang erlang> fac(N) -> fac(N-1,N). fac(1,N) -> N; fac(I,N) -> fac(I-1,N*I).</lang>
FALSE
[1\[$][$@*\1-]#%]f: ^'0- f;!.
Recursive:
[$1=~[$1-f;!*]?]f:
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>
F#
This is a fast tail-recursive implementation. <lang fsharp>let factorial n : bigint =
let rec f a n = match n with | 0I -> a | n -> (f (a * n) (n - 1I)) f 1I n</lang>
> factorial 8I;; val it : bigint = 40320I > factorial 800I;; val it : bigint = 771053011335386004144639397775028360595556401816010239163410994033970851827093069367090769795539033092647861224230677444659785152639745401480184653174909762504470638274259120173309701702610875092918816846985842150593623718603861642063078834117234098513725265045402523056575658860621238870412640219629971024686826624713383660963127048195572279707711688352620259869140994901287895747290410722496106151954257267396322405556727354786893725785838732404646243357335918597747405776328924775897564519583591354080898117023132762250714057271344110948164029940588827847780442314473200479525138318208302427727803133219305210952507605948994314345449325259594876385922128494560437296428386002940601874072732488897504223793518377180605441783116649708269946061380230531018291930510748665577803014523251797790388615033756544830374909440162270182952303329091720438210637097105616258387051884030288933650309756289188364568672104084185529365727646234588306683493594765274559497543759651733699820639731702116912963247441294200297800087061725868223880865243583365623482704395893652711840735418799773763054887588219943984673401051362280384187818611005035187862707840912942753454646054674870155072495767509778534059298038364204076299048072934501046255175378323008217670731649519955699084482330798811049166276249251326544312580289357812924825898217462848297648349400838815410152872456707653654424335818651136964880049831580548028614922852377435001511377656015730959254647171290930517340367287657007606177675483830521499707873449016844402390203746633086969747680671468541687265823637922007413849118593487710272883164905548707198762911703545119701275432473548172544699118836274377270607420652133092686282081777383674487881628800801928103015832821021286322120460874941697199487758769730544922012389694504960000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000I
Genyris
Recursive
<lang python>def factorial (n)
if (< n 2) 1 * n factorial (- n 1)</lang>
Groovy
Recursive
A recursive closure must be pre-declared. <lang groovy>def rFact rFact = { (it > 1) ? it * rFact(it - 1) : 1 } </lang>
Test program: <lang groovy>(0..6).each { println "${it}: ${rFact(it)}" }</lang>
Output:
0: 1 1: 1 2: 2 3: 6 4: 24 5: 120 6: 720
Iterative
<lang groovy>def iFact = { (it > 1) ? (2..it).inject(1) { i, j -> i*j } : 1 }</lang>
Test program: <lang groovy>(0..6).each { println "${it}: ${iFact(it)}" }</lang>
Output:
0: 1 1: 1 2: 2 3: 6 4: 24 5: 120 6: 720
Haskell
The simplest description: factorial is the product of the numbers from 1 to n:
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>
Lisaac
<lang Lisaac> - factorial x : INTEGER : INTEGER <- (
+ result : INTEGER; (x <= 1).if { result := 1; } else { result := x * factorial(x - 1); }; result
); </lang>
Logo
to factorial :n if :n < 2 [output 1] output :n * factorial :n-1 end
M4
<lang M4> define(`factorial',`ifelse(`$1',0,1,`eval($1*factorial(decr($1)))')')dnl dnl factorial(5) </lang>
Output:
120
Mathematica
Note that Mathematica already comes with a factorial function, which can be used as e.g. 5! (gives 120). So the following implementations are only of pedagogical value.
Recursive
<lang mathematica> factorial[n_Integer] := n*factorial[n-1] factorial[0] = 1 </lang>
Iterative (direct loop)
<lang mathematica> factorial[n_Integer] :=
Block[{i, result = 1}, For[i = 1, i <= n, ++i, result *= i]; result]
</lang>
Iterative (list)
factorial[n_Integer] := Block[{i}, Times @@ Table[i, {i, n}]]
MAXScript
Iterative
fn factorial n = ( if n == 0 then return 1 local fac = 1 for i in 1 to n do ( fac *= i ) fac )
Recursive
fn factorial_rec n = ( local fac = 1 if n > 1 then ( fac = n * factorial_rec (n - 1) ) fac )
Modula-3
Iterative
<lang modula3>PROCEDURE FactIter(n: CARDINAL): CARDINAL =
VAR result := n; counter := n - 1; BEGIN FOR i := counter TO 1 BY -1 DO result := result * i; END; RETURN result; END FactIter;</lang>
Recursive
<lang modula3>PROCEDURE FactRec(n: CARDINAL): CARDINAL =
VAR result := 1;
BEGIN IF n > 1 THEN result := n * FactRec(n - 1); END; RETURN result; END FactRec;</lang>
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>
Octave
<lang octave>% built in factorial printf("%d\n", factorial(50));
% let's define our recursive... function fact = my_fact(n)
if ( n <= 1 ) fact = 1; else fact = n * my_fact(n-1); endif
endfunction
printf("%d\n", my_fact(50));
% let's define our iterative function fact = iter_fact(n)
fact = 1; for i = 2:n fact = fact * i; endfor
endfunction
printf("%d\n", iter_fact(50));</lang>
Output:
30414093201713018969967457666435945132957882063457991132016803840 30414093201713375576366966406747986832057064836514787179557289984 30414093201713375576366966406747986832057064836514787179557289984
(Built-in is fast but use an approximation for big numbers)
Pascal
Iterative
<lang pascal> function factorial(n: integer): integer;
var i, result: integer; begin result := 1; for i := 1 to n do result := result * i; factorial := result end;
</lang>
Recursive
<lang pascal> function factorial(n: integer): integer;
begin if n = 0 then factorial := 1 else factorial := n*factorial(n-1) end;
</lang>
Perl
Iterative
<lang perl>sub factorial {
my $n = shift; my $result = 1; for (my $i = 1; $i <= $n; ++$i) { $result *= $i; }; $result;
}
- using a .. range
sub factorial {
my $r = 1; $r *= $_ for 1..shift; $r;
}</lang>
Recursive
<lang perl>sub factorial {
my $n = shift; ($n == 0)? 1 : $n*factorial($n-1);
}</lang>
Functional
<lang perl>use List::Util qw(reduce); sub factorial {
my $n = shift; reduce { $a * $b } 1, 1 .. $n
}</lang>
Perl 6
Reduction Operator
<lang perl>sub postfix:<!> { [*] 1..$^n }
say 5!; #prints 120 </lang>
PHP
Iterative
<lang php> <?php function factorial($n) {
if ($n < 0) { return 0; }
$factorial = 1; for ($i = $n; $i >= 1; $i--) { $factorial = $factorial * $i; }
return $factorial;
} ?> </lang>
Recursive
<lang php> <?php function factorial($n) {
if ($n < 0) { return 0; }
if ($n == 0) { return 1; }
else { return $n * factorial($n-1); }
} ?> </lang>
Prolog
<lang prolog>fact(X, 1) :- X<2. fact(X, F) :- Y is X-1, fact(Y,Z), F is Z*X.</lang>
PowerShell
Recursive
<lang powershell>function Get-Factorial ($x) {
if ($x -eq 0) { return 1 } return $x * (Get-Factorial ($x - 1))
}</lang>
Iterative
<lang powershell>function Get-Factorial ($x) {
if ($x -eq 0) { return 1 } else { $product = 1 1..$x | ForEach-Object { $product *= $_ } return $product }
}</lang>
Evaluative
This one first builds a string, containing 1*2*3...
and then lets PowerShell evaluate it. A bit of mis-use but works.
<lang powershell>function Get-Factorial ($x) {
if ($x -eq 0) { return 1 } return (Invoke-Expression (1..$x -join '*'))
}</lang>
Python
Library
<lang python>import math math.factorial(n)</lang>
Iterative
<lang python>def factorial(n):
if n == 0: return 1 z=n while n>1: n=n-1 z=z*n return z
</lang>
Functional
<lang python>from operator import mul
def factorial(n):
return reduce(mul, xrange(1,n+1), 1)
</lang>
Sample output:
<lang python>
>>> for i in range(6): print i, factorial(i) 0 1 1 1 2 2 3 6 4 24 5 120 >>>
</lang>
Numerical Approximation
The following sample uses Lanczos approximation from wp:Lanczos_approximation <lang python> from cmath import *
- Coefficients used by the GNU Scientific Library
g = 7 p = [0.99999999999980993, 676.5203681218851, -1259.1392167224028,
771.32342877765313, -176.61502916214059, 12.507343278686905, -0.13857109526572012, 9.9843695780195716e-6, 1.5056327351493116e-7]
def gamma(z):
z = complex(z) # Reflection formula if z.real < 0.5: return pi / (sin(pi*z)*gamma(1-z)) else: z -= 1 x = p[0] for i in range(1, g+2): x += p[i]/(z+i) t = z + g + 0.5 return sqrt(2*pi) * t**(z+0.5) * exp(-t) * x
def factorial(n):
return gamma(n+1)
print "factorial(-0.5)**2=",factorial(-0.5)**2 for i in range(10):
print "factorial(%d)=%s"%(i,factorial(i))
</lang> Output:
factorial(-0.5)**2= (3.14159265359+0j) factorial(0)=(1+0j) factorial(1)=(1+0j) factorial(2)=(2+0j) factorial(3)=(6+0j) factorial(4)=(24+0j) factorial(5)=(120+0j) factorial(6)=(720+0j) factorial(7)=(5040+0j) factorial(8)=(40320+0j) factorial(9)=(362880+0j)
Recursive
<lang python>def factorial(n):
z=1 if n>1: z=n*factorial(n-1) return z
</lang>
R
Recursive
<lang R>fact <- function(n) {
if ( n <= 1 ) 1 else n * fact(n-1)
} </lang>
Iterative
<lang R> factIter <- function(n) {
f = 1 for (i in 2:n) f <- f * i f
}</lang>
Numerical Approximation
R has a native gamma function and a wrapper for that function that can produce factorials. E.g. <lang R>print(factorial(50)) # 3.041409e+64</lang>
Ruby
Recursive
<lang ruby>def factorial_recursive(n)
n.zero? ? 1 : n * factorial_recursive(n - 1)
end</lang>
Iterative
<lang ruby>def factorial_iterative(n)
n.downto(2).inject(1) {|factorial, i| factorial *= i}
end</lang>
Functional
<lang ruby>def factorial_functional(n)
(1..n).reduce(1, :*)
end</lang>
Performance
<lang ruby>require 'benchmark'
n = 400 m = 10000
Benchmark.bm(12) do |b|
b.report('recursive:') {m.times {factorial_recursive(n)}} b.report('iterative:') {m.times {factorial_iterative(n)}} b.report('functional:') {m.times {factorial_functional(n)}}
end</lang>
Output
user system total real recursive: 14.875000 0.000000 14.875000 ( 14.914000) iterative: 14.203000 0.000000 14.203000 ( 14.451000) functional: 9.125000 0.000000 9.125000 ( 9.354000)
Scheme
Recursive
<lang scheme>(define (factorial n)
(if (<= n 0) 1 (* n (factorial (- n 1)))))</lang>
The following is tail-recursive, so it is effectively iterative: <lang scheme>(define (factorial n)
(let loop ((i 1) (accum 1)) (if (> i n) accum (loop (+ i 1) (* accum i)))))</lang>
Iterative
<lang scheme>(define (factorial n)
(do ((i 1 (+ i 1)) (accum 1 (* accum i))) ((> i n) accum)))</lang>
Slate
This is already implemented in the core language as:
<lang slate> n@(Integer traits) factorial "The standard recursive definition." [
n isNegative ifTrue: [error: 'Negative inputs to factorial are invalid.']. n <= 1 ifTrue: [1] ifFalse: [n * ((n - 1) factorial)]
]. </lang>
Here is another way to implement it:
<lang slate> n@(Integer traits) factorial2 [
n isNegative ifTrue: [error: 'Negative inputs to factorial are invalid.']. (1 upTo: n by: 1) reduce: [|:a :b| a * b]
]. </lang>
The output:
<lang slate> slate[5]> 100 factorial. 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 </lang>
Smalltalk
Smalltalk Number class already has a factorial method; however, let's see how we can implement it by ourselves.
Iterative with fold
<lang smalltalk>Number extend [
my_factorial [ (self < 2) ifTrue: [ ^1 ] ifFalse: [ |c| c := OrderedCollection new. 2 to: self do: [ :i | c add: i ].
^ (c fold: [ :a :b | a * b ] )
] ]
].
7 factorial printNl. 7 my_factorial printNl.</lang>
Recursive
<lang smalltalk>Number extend [
my_factorial [ self < 0 ifTrue: [ self error: 'my_factorial is defined for natural numbers' ]. self isZero ifTrue: [ ^1 ]. ^self * ((self - 1) my_factorial) ]
].</lang>
Standard ML
Recursive
<lang sml>fun factorial n =
if n <= 0 then 1 else n * factorial (n-1)</lang>
The following is tail-recursive, so it is effectively iterative: <lang sml>fun factorial n = let
fun loop (i, accum) = if i > n then accum else loop (i + 1, accum * i)
in
loop (1, 1)
end</lang>
Tcl
Use Tcl 8.5 for its built-in arbitrary precision integer support.
Iterative
<lang tcl>proc ifact n {
for {set i $n; set sum 1} {$i >= 2} {incr i -1} { set sum [expr {$sum * $i}] } return $sum
}</lang>
Recursive
<lang tcl>proc rfact n {
expr {$n < 2 ? 1 : $n * [rfact [incr n -1]]}
}</lang>
The recursive version is limited by the default stack size to roughly 850!
When put into the tcl::mathfunc namespace, the recursive call stays inside the expr language, and thus looks clearer:
<lang Tcl>proc tcl::mathfunc::fact n {expr {$n < 2? 1: $n*fact($n-1)}}</lang>
Iterative with caching
<lang tcl>proc ifact_caching n {
global fact_cache if { ! [info exists fact_cache]} { set fact_cache {1 1} } if {$n < [llength $fact_cache]} { return [lindex $fact_cache $n] } set i [expr {[llength $fact_cache] - 1}] set sum [lindex $fact_cache $i] while {$i < $n} { incr i set sum [expr {$sum * $i}] lappend fact_cache $sum } return $sum
}</lang>
Performance Analysis
<lang tcl>puts [ifact 30] puts [rfact 30] puts [ifact_caching 30]
set n 400 set iterations 10000 puts "calculate $n factorial $iterations times" puts "ifact: [time {ifact $n} $iterations]" puts "rfact: [time {rfact $n} $iterations]"
- for the caching proc, reset the cache between each iteration so as not to skew the results
puts "ifact_caching: [time {ifact_caching $n; unset -nocomplain fact_cache} $iterations]"</lang> Output:
265252859812191058636308480000000 265252859812191058636308480000000 265252859812191058636308480000000 calculate 400 factorial 10000 times ifact: 661.4324 microseconds per iteration rfact: 654.7593 microseconds per iteration ifact_caching: 613.1989 microseconds per iteration
TI-89 BASIC
TI-89 BASIC also has the factorial function built in: x! is the factorial of x.
factorial(x) Func Return Π(y,y,1,x) EndFunc
Π is the standard product operator:
UNIX Shell
fact () { if [ $1 -eq 0 ]; then echo 1; else echo $(($1 * $(fact $(($1-1)) ) )); fi; }
Ursala
There is already a library function for factorials, but they can be defined anyway like this. The good method treats natural numbers as an abstract type, and the better method factors out powers of 2 by bit twiddling. <lang Ursala>
- import nat
good_factorial = ~&?\1! product:-1^lrtPC/~& iota better_factorial = ~&?\1! ^T(~&lSL,@rS product:-1)+ ~&Z-~^*lrtPC/~& iota</lang> test program: <lang Ursala>#cast %nL
test = better_factorial* <0,1,2,3,4,5,6,7,8></lang> output:
<1,1,2,6,24,120,720,5040,40320>
- Programming Tasks
- Arithmetic operations
- Recursion
- Classic CS problems and programs
- ActionScript
- Ada
- ALGOL 68
- AmigaE
- AutoHotkey
- AWK
- BASIC
- Bc
- Befunge
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- E
- Erlang
- FALSE
- Forth
- Fortran
- F Sharp
- Genyris
- Groovy
- Haskell
- J
- Java
- JavaScript
- Lisaac
- Logo
- M4
- Mathematica
- MAXScript
- Modula-3
- Nial
- OCaml
- Octave
- Pascal
- Perl
- Perl 6
- PHP
- Prolog
- PowerShell
- Python
- R
- Ruby
- Scheme
- Slate
- Smalltalk
- Standard ML
- Tcl
- TI-89 BASIC
- UNIX Shell
- Ursala