Factorial: Difference between revisions

{{task|Arithmetic operations}}

[[Category:Recursion]]

[[Category:Arithmetic]]

[[Category:Simple]]

 

;Definitions:

:* &nbsp; The &nbsp; '''Factorial Function''' &nbsp; of a positive integer, &nbsp; <big> ''n'', </big> &nbsp; is defined as the product of the sequence:

<big><big> ''n'', &nbsp; ''n''-1, &nbsp; ''n''-2, &nbsp; ... &nbsp; 1 </big></big>

 

 

 

Support for trapping negative &nbsp; <big> ''n'' </big> &nbsp; errors is optional.

<br><br>

 

This is an iterative solution which outputs the factorial of each number supplied on standard input.

 

|~ Read n,

#:end: if n is 0 terminates

{+% Dequeue incidental 0, add to get Y into Z, output fac(n).

<:a:~$ Output a newline.

 

{{out}}

78

2d0</pre>

 

=={{header|360 Assembly}}==

For maximum compatibility, this program uses only the basic instruction set.

USING FACTO,R13

SAVEAREA B STM-SAVEAREA(R15)

L R15,=A(FACT)

BALR R14,R15 call fact(n)

DUMP EQU *

MVC WTOBUF+5(2),S+30

MVC WTOBUF+9(32),S

WTO MF=(E,WTOMSG)

ENDLOOPN EQU *

RETURN EQU *

LOOP CP I,L if i>l

BH ENDLOOP then goto endloop

ENDLOOP EQU *

LA R1,R return r

LTORG

YREGS

{{out}}

<pre>FACT(29)= 8841761993739701954543616000000 </pre>

 

=={{header|ABAP}}==

===Iterative===

data: lv_res type i value 1.

do iv_val times.

 

iv_val = lv_res.

===Recursive===

data: lv_temp type i.

 

multiply iv_val by lv_temp.

endif.

 

=={{header|ActionScript}}==

===Iterative===

{

if (n < 0)

 

return fact;

===Recursive===

{

if (n < 0)

return n * factorial(n - 1);

 

=={{header|Ada}}==

===Iterative===

Result : Positive := N;

Counter : Natural := N - 1;

end loop;

return Result;

===Recursive===

Result : Positive := 1;

begin

end if;

return Result;

===Numerical Approximation===

with Ada.Numerics.Generic_Complex_Elementary_Functions;

with Ada.Numerics.Generic_Elementary_Functions;

New_Line;

end loop;

{{out}}

<pre>

factorial( 9) = (362880.00000000, 0.00000000)

</pre>

 

=={{header|Aime}}==

===Iterative===

factorial(integer n)

{

 

return result;

 

=={{header|ALGOL 68}}==

===Iterative===

LONG LONG INT z := 1;

FOR n TO upb n DO z *:= n OD;

z

 

===Numerical Approximation===

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to restricted support for ''compl''}}

[]REAL p = []REAL(0.99999999999980993, 676.5203681218851, -1259.1392167224028,

771.32342877765313, -176.61502916214059, 12.507343278686905,

OD

)

{{out}}

<pre>

 

===Recursive===

CASE n+1 IN

1,1,2,6,24,120,720 # a brief lookup #

n*factorial(n-1)

ESAC

 

=={{header|ALGOL W}}==

Iterative solution

% computes factorial n iteratively %

integer procedure factorial( integer value n ) ;

for t := 0 until 10 do write( "factorial: ", t, factorial( t ) );

 

 

=={{header|AmigaE}}==

Recursive solution:

 

PROC main()

WriteF('5! = \d\n', fact(5))

 

Iterative:

DEF r, y

IF x < 2 THEN RETURN 1

r := 1; y := x;

FOR x := 2 TO y DO r := r * x

 

=={{header|AntLang}}==

AntLang is a functional language, but it isn't made for recursion - it's made for list processing.

 

=={{header|Apex}}==

===Iterative===

if (n < 0) {

System.debug('No negative numbers');

}

return ans;

===Recursive===

if (n < 0){

System.debug('No negative numbers');

}

return (n < 2) ? 1 : n * fact(n - 1);

 

=={{header|APL}}==

But, if we want to reimplement it, we can start by noting that <i>n</i>! is found by multiplying together a vector of integers 1, 2... <i>n</i>. This definition ('multiply'—'together'—'integers from 1 to'—'<i>n</i>') can be expressed directly in APL notation:

And the resulting function can then be used instead of the (admittedly more convenient) builtin one:

 

=={{header|AppleScript}}==

===Iteration===

if x < 0 then return 0

set R to 1

end repeat

return R

 

===Recursion===

(Perhaps because the iterative code is making use of list splats)

 

on factorial(x)

if x > 1 then

x * (factorial(x - 1))

else

end if

 

===Fold===

 

 

-- factorial :: Int -> Int

on factorial(x)

end factorial

 

 

 

 

-- foldl :: (a -> b -> a) -> a -> [b] -> a

set lng to length of xs

repeat with i from 1 to lng

end repeat

return v

end tell

end foldl

 

 

else

script

end script

end if

 

 

 

=={{header|Arendelle}}==

}

</pre>

 

=={{header|ATS}}==

 

===Iterative===

fun

fact

val () = while (n > 0) (res := res * n; n := n - 1)

}

 

===Recursive===

fun

factorial

if n > 0 then n * factorial(n-1) else 1

// end of [factorial]

 

===Tail-recursive===

fun

factorial

loop(n, 1)

end // end of [factorial]

 

=={{header|AutoHotkey}}==

===Iterative===

 

factorial(n)

result *= A_Index

Return result

 

===Recursive===

 

factorial(n)

{

return n > 1 ? n-- * factorial(n) : 1

 

=={{header|AutoIt}}==

===Iterative===

MsgBox (0,"Factorial",factorial(6))

Func factorial($int)

Next

Return $fact

===Recursive===

MsgBox (0,"Factorial",factorial(6))

Func factorial($int)

EndIf

return $int * factorial($int - 1)

 

=={{header|AWK}}==

'''Recursive'''

{

if ( n <= 1 ) return 1;

return n*fact_r(n-1);

 

'''Iterative'''

{

if ( n < 1 ) return 1;

}

return r

 

=={{header|Axe}}==

'''Iterative'''

1→R

For(I,1,r₁)

End

R

 

'''Recursive'''

r₁??1,r₁*FACT(r₁-1)

 

=={{header|Babel}}==

 

===Iterative===

{(0 1 2 3 4 5 6 7 8 9 10)

{fact ! %d nl <<}

{dup 1 =}{ zap 1 }

{1 }{ <- 1 {iter 1 + *} -> 1 - times })

 

===Recursive===

{(0 1 2 3 4 5 6 7 8 9 10)

{fact ! %d nl <<}

{1 }{ dup 1 - fact ! *})

cond}))

 

When run, either code snippet generates the following

=={{header|bash}}==

===Recursive===

{

if [ $1 -le 1 ]

fi

}

 

=={{header|BASIC}}==

===Iterative===

{{works with|QBasic}}

{{works with|RapidQ}}

DIM f AS Integer, i AS Integer

f = 1

NEXT i

factorial = f

 

===Recursive===

{{works with|QBasic}}

{{works with|RapidQ}}

IF n < 2 THEN

factorial = 1

factorial = n * factorial(n-1)

END IF

 

input n

print string(n) + "! = " + string(factorial(n))

next p

end if

 

input n

print string(n) + "! = " + string(factorial(n))

factorial = 1

end if

 

{{works with|BBC BASIC for Windows}}

18! is the largest that doesn't overflow.

@% = &1010

DEF FNfactorial(n)

{{out}}

<pre>6402373705728000</pre>

 

=={{header|bc}}==

 

define f(x) {

}

f(1000)

 

 

=={{header|beeswax}}==

Infinite loop for entering <code>n</code> and getting the result <code>n!</code>:

 

_>1FT"pF>M"p~.~d

>Pd >~{Np

 

Calculate <code>n!</code> only once:

 

_1FT"pF>M"p~.~d

 

Limits for UInt64 numbers apply to both examples.

<code>i</code> indicates that the program expects the user to enter an integer.

 

i0

1

3628800

i22

 

Input of negative numbers forces the program to quit with an error message.

 

=={{header|Befunge}}==

^-1:_$>\:|

 

=={{header|Bracmat}}==

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

=

. !arg:0&1

$ 10

: 3628800

 

This recursive lambda function is made in the following way (see http://en.wikipedia.org/wiki/Lambda_calculus):

or, translated to Bracmat, and computing 10!

 

& (!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).

Lastly, here is an iterative solution

 

r

. !arg:?r

' (!arg:>1&(!arg+-1:?arg)*!r:?r)

& !r

 

factorial$5000

=={{header|Brainf***}}==

Prints sequential factorials in an infinite loop.

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

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

 

=={{header|Brat}}==

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

 

=={{header|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 ) 7ro)(.*){0 1 11}die!

720

 

=== Iterative ===

return result;

 

int result = 1;

for (int i = 1; i <= n; ++i)

result *= i;

return result;

=== Recursive ===

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

 

=== Tail Recursive ===

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

return n < 1 ? acc : fac_aux(n - 1, acc * n);

}

 

int factorial(int n) {

return fac_aux(n, 1);

 

=={{header|C sharp|C#}}==

===Iterative===

 

class Program

static int Factorial(int number)

{

{

accumulator *= factor;

Console.WriteLine(Factorial(10));

}

===Recursive===

 

class Program

static int Factorial(int number)

{

return number == 0 ? 1 : number * Factorial(number - 1);

}

Console.WriteLine(Factorial(10));

}

===Tail Recursive===

 

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

}

Console.WriteLine(Factorial(10));

}

===Functional===

using System.Linq;

 

Console.WriteLine(Factorial(10));

}

 

=={{header|C++}}==

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

#include <algorithm>

 

// last is one-past-end

return std::accumulate(boost::counting_iterator<int>(1), boost::counting_iterator<int>(n+1), 1, std::multiplies<int>());

 

===Iterative===

 

===Template===

struct Factorial

{

int x = Factorial<4>::value; // == 24

int y = Factorial<0>::value; // == 1

 

=={{header|Cat}}==

Taken direct from the Cat manual:

 

=={{header|Ceylon}}==

Integer? recursiveFactorial(Integer n) =>

}

}

 

=={{header|Chapel}}==

var r = 1;

for i in 1..n do

return r;

 

=={{header|Chef}}==

 

Only reads one value.

Pour contents of the 1st mixing bowl into the 1st baking dish.

 

 

=={{header|ChucK}}==

===Recursive===

0 => int total;

fun int factorial(int i)

return total;

}

===Iterative===

1 => int total;

fun int factorial(int i)

return total;

}

 

=={{header|Clay}}==

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

if (n == 0) return 1;

return n * factorialRec(n - 1);

factorialFold(n) {

return reduce(multiply, 1, range(1, n + 1));

 

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

 

 

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

 

if (n == 0) return N(1);

return n * factorial(n - 1);

 

And testing:

 

println(factorialRec(5)); // 120

println(factorialIter(5)); // 120

println(factorialStatic(static 5)); // 120

println(factorial(Int64(20))); // 2432902008176640000

 

=={{header|CLIPS}}==

(if (or (not (integerp ?a)) (< ?a 0)) then

(printout t "Factorial Error!" crlf)

1

else

 

=={{header|Clojure}}==

 

=== Folding ===

 

=== Recursive ===

(if (< x 2)

1

 

=== Tail recursive ===

(loop [x x

acc 1]

(if (< x 2)

acc

 

=={{header|CMake}}==

set(product 1)

foreach(i RANGE 2 ${n})

 

factorial(f 12)

 

=={{header|COBOL}}==

=== Intrinsic Function ===

COBOL includes an intrinsic function which returns the factorial of its argument.

 

=== Iterative ===

DATA DIVISION.

LOCAL-STORAGE SECTION.

LINKAGE SECTION.

PROCEDURE DIVISION USING BY VALUE n RETURNING ret.

MOVE 1 TO ret

PERFORM VARYING i FROM 2 BY 1 UNTIL n < i

MULTIPLY i BY ret

END-PERFORM

 

=== Recursive ===

{{works with|Visual COBOL}}

DATA DIVISION.

LOCAL-STORAGE SECTION.

LINKAGE SECTION.

PROCEDURE DIVISION USING BY VALUE n RETURNING ret.

IF n = 0

ELSE

SUBTRACT 1 FROM n GIVING prev-n

END-IF

 

=={{header|CoffeeScript}}==

 

=== Recursive ===

if n <= 1

1

else

 

=== Functional ===

{{works with|JavaScript|1.8}} (See [https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Objects/Array/reduce MDC])

 

=={{header|Comal}}==

Recursive:

r:=1

IF n>1 THEN

ENDIF

RETURN r

 

=={{header|Common Lisp}}==

Recursive:

 

Iterative:

"Calculates N!"

(loop for result = 1 then (* result i)

for i from 2 to n

 

Functional:

 

=={{header|Computer/zero Assembly}}==

Both these programs find <math>x</math>!. Values of <math>x</math> higher than 5 are not supported, because their factorials will not fit into an unsigned byte.

===Iterative===

BRZ done_i ; 0! = 1

 

n: 0

 

 

===Lookup===

Since there is only a small range of possible values of <math>x</math>, storing the answers and looking up the one we want is much more efficient than actually calculating them. This lookup version uses 5 bytes of code and 7 bytes of data and finds 5! in 5 instructions, whereas the iterative solution uses 23 bytes of code and 6 bytes of data and takes 122 instructions to find 5!.

ADD x

STA load

120

 

 

=={{header|D}}==

===Iterative Version===

in {

assert(n <= 12);

// Computed and printed at run-time.

12.factorial.writeln;

{{out}}

<pre>479001600u

 

===Recursive Version===

in {

assert(n <= 12);

// Computed and printed at run-time.

12.factorial.writeln;

(Same output.)

 

===Functional Version===

 

uint factorial(in uint n) pure nothrow @nogc

// Computed and printed at run-time.

12.factorial.writeln;

(Same output.)

 

===Tail Recursive (at run-time, with DMD) Version===

in {

assert(n <= 12);

// Computed and printed at run-time.

12.factorial.writeln;

(Same output.)

 

=={{header|Dart}}==

===Recursive===

if(n<0) {

throw new IllegalArgumentException('Argument less than 0');

print(fact(10));

print(fact(-1));

===Iterative===

if(n<0) {

throw new IllegalArgumentException('Argument less than 0');

print(fact(10));

print(fact(-1));

 

=={{header|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

* For example, print the factorial of 50.

*]sz

 

=={{header|Delphi}}==

===Iterative===

 

{$APPTYPE CONSOLE}

begin

Writeln('5! = ', FactorialIterative(5));

 

===Recursive===

 

{$APPTYPE CONSOLE}

begin

Writeln('5! = ', FactorialRecursive(5));

 

===Tail Recursive===

 

{$APPTYPE CONSOLE}

begin

Writeln('5! = ', FactorialTailRecursive(5));

 

=={{header|DWScript}}==

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

===Iterative===

var

i : Integer;

for i := 2 to n do

Result *= i;

===Recursive===

begin

if n>1 then

Result := RecursiveFactorial(n-1)*n

else Result := 1;

 

=={{header|Dylan}}==

 

=={{header|E}}==

def factorial(n) {

return accum 1 for i in 2..n { _ * i }

 

=={{header|EchoLisp}}==

===Iterative===

(define (fact n)

(for/product ((f (in-range 2 (1+ n)))) f))

(fact 10)

→ 3628800

===Recursive with memoization===

(define (fact n)

(if (zero? n) 1

(fact 10)

→ 3628800

===Tail recursive===

(define (fact n (acc 1))

(if (zero? n) acc

(fact 10)

→ 3628800

===Primitive===

(factorial 10)

→ 3628800

===Numerical approximation===

(lib 'math)

math.lib v1.13 ® EchoLisp

(gamma 11)

→ 3628800.0000000005

 

=={{header|EGL}}==

===Iterative===

function fact(n int in) returns (bigint)

if (n < 0)

return (ans);

end

===Recursive===

function fact(n int in) returns (bigint)

if (n < 0)

end

end

 

=={{header|Eiffel}}==

 

note

description: "recursive and iterative factorial example of a positive integer."

 

end

 

=={{header|Ela}}==

Tail recursive version:

 

where fact' acc 0 = acc

 

=={{header|Elixir}}==

# Simple recursive function

def fac(0), do: 1

def fac_tail(1, acc), do: acc

def fac_tail(n, acc) when n > 1, do: fac_tail(n - 1, acc * n)

# Using Enumeration features

def fac_reduce(0), do: 1

def fac_reduce(n) when n > 0, do: Enum.reduce(1..n, 1, &*/2)

 

=={{header|Elm}}==

 

factorial n =

 

=={{header|Emacs Lisp}}==

 

 

The <code>calc</code> package (which comes with Emacs) has a builtin <code>fact()</code>. It automatically uses the bignums implemented by <code>calc</code>.

 

(calc-eval "fact(30)")

=>

 

=={{header|Erlang}}==

With a fold:

 

With a recursive function:

 

With a tail-recursive function:

fac(1,N) -> N;

 

=={{header|ERRE}}==

 

'''Iterative procedure:'''

PROCEDURE FACTORIAL(X%->F)

F=1

END IF

END PROCEDURE

 

'''Recursive procedure:'''

PROCEDURE FACTORIAL(FACT,X%->FACT)

IF X%>1 THEN FACTORIAL(X%*FACT,X%-1->FACT)

END IF

END PROCEDURE

Procedure call is for example FACTORIAL(1,5->N)

 

Straight forward methods

===Iterative===

atom f = 1

while n > 1 do

 

return f

 

===Recursive===

if n > 1 then

return factorial(n-1) * n

return 1

end if

 

===Tail Recursive===

{{works with|Euphoria|4.0.0}}

if n <= 0 then

return acc

return factorial(n-1, n*acc)

end if

 

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

 

 

enum MUL_LLL,

end if

ip += 1

 

=={{header|Ezhil}}==

Recursive

நிரல்பாகம் fact ( n )

@( n == 0 ) ஆனால்

 

பதிப்பி fact ( 10 )

 

=={{header|F_Sharp|F#}}==

// ^a -> ^a

// when ^a : (static member get_One : -> ^a) and

// ^a : (static member ( + ) : ^a * ^a -> ^a) and

// ^a : (static member ( * ) : ^a * ^a -> ^a)

<div style="width:full;overflow:scroll">

> factorial 8;;

=={{header|Factor}}==

{{trans|Haskell}}

 

 

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

 

=={{header|FALSE}}==

Recursive:

 

=={{header|Fancy}}==

def factorial {

1 upto: self . product

1 upto: 10 do_each: |i| {

i to_s ++ "! = " ++ (i factorial) println

 

=={{header|Fantom}}==

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

{

static Int factorialRecursive (Int n)

echo (factorialFunctional(20))

}

 

=={{header|Forth}}==

===Single Precision===

===Double Precision===

On a 64 bit computer, can compute up to 33! Also does error checking. In gforth, error code -24 is "invalid numeric argument."

dup 33 u> -24 and throw

dup 2 < IF

-5 factorial d.

:2: Invalid numeric argument

 

=={{header|Fortran}}==

===Fortran 90===

 

 

 

 

 

=={{header|friendly interactive shell}}==

 

===Iterative===

function factorial

set x $argv[1]

echo $result

end

 

===Recursive===

function factorial

set x $argv[1]

end

end

 

=={{header|Frink}}==

factorial2[x] := product[1 to x]

 

=={{header|FunL}}==

=== Procedural ===

if n < 0

error( 'factorial: n should be non-negative' )

res *= i

 

 

=== Recursive ===

factorial( (0|1) ) = 1

factorial( n )

| n > 0 = n*factorial( n - 1 )

 

=== Tail-recursive ===

| n >= 0 =

def

 

fact( 1, n )

 

=== Using a library function ===

| n >= 0 = product( 1..n )

 

=={{header|Futhark}}==

 

=== Recursive ===

 

fun fact(n: int): int =

if n == 0 then 1

else n * fact(n-1)

 

== Iterative ==

 

fun fact(n: int): int =

loop (out = 1) = for i < n do

out * (i+1)

in out

 

=={{header|FutureBasic}}==