Factorial
You are encouraged to solve this task according to the task description, using any language you may know.
- Definitions
-
- The factorial of 0 (zero) is defined as being 1 (unity).
- The Factorial Function of a positive integer, n, is defined as the product of the sequence:
n, n-1, n-2, ... 1
- Task
Write a function to return the factorial of a number.
Solutions can be iterative or recursive.
Support for trapping negative n errors is optional.
- Related task
0815[edit]
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
11l[edit]
F factorial(n)
V result = 1
L(i) 2..n
result *= i
R result
L(n) 0..5
print(n‘ ’factorial(n))
- Output:
0 1 1 1 2 2 3 6 4 24 5 120
360 Assembly[edit]
For maximum compatibility, this program uses only the basic instruction set.
FACTO CSECT
USING FACTO,R13
SAVEAREA B STM-SAVEAREA(R15)
DC 17F'0'
DC CL8'FACTO'
STM STM R14,R12,12(R13)
ST R13,4(R15)
ST R15,8(R13)
LR R13,R15 base register and savearea pointer
ZAP N,=P'1' n=1
LOOPN CP N,NN if n>nn
BH ENDLOOPN then goto endloop
LA R1,PARMLIST
L R15,=A(FACT)
BALR R14,R15 call fact(n)
ZAP F,0(L'R,R1) f=fact(n)
DUMP EQU *
MVC S,MASK
ED S,N
MVC WTOBUF+5(2),S+30
MVC S,MASK
ED S,F
MVC WTOBUF+9(32),S
WTO MF=(E,WTOMSG)
AP N,=P'1' n=n+1
B LOOPN
ENDLOOPN EQU *
RETURN EQU *
L R13,4(0,R13)
LM R14,R12,12(R13)
XR R15,R15
BR R14
FACT EQU * function FACT(l)
L R2,0(R1)
L R3,12(R2)
ZAP L,0(L'N,R2) l=n
ZAP R,=P'1' r=1
ZAP I,=P'2' i=2
LOOP CP I,L if i>l
BH ENDLOOP then goto endloop
MP R,I r=r*i
AP I,=P'1' i=i+1
B LOOP
ENDLOOP EQU *
LA R1,R return r
BR R14 end function FACT
DS 0D
NN DC PL16'29'
N DS PL16
F DS PL16
C DS CL16
II DS PL16
PARMLIST DC A(N)
S DS CL33
MASK DC X'40',29X'20',X'212060' CL33
WTOMSG DS 0F
DC H'80',XL2'0000'
WTOBUF DC CL80'FACT(..)=................................ '
L DS PL16
R DS PL16
I DS PL16
LTORG
YREGS
END FACTO
- Output:
FACT(29)= 8841761993739701954543616000000
68000 Assembly[edit]
This implementation takes a 16-bit parameter as input and outputs a 32-bit product. It does not trap overflow from 0xFFFFFFFF to 0, and treats both input and output as unsigned.
Factorial:
;input: D0.W: number you wish to get the factorial of.
;output: D0.L
CMP.W #0,D0
BEQ .isZero
CMP.W #1,D0
BEQ .isOne
MOVEM.L D4-D5,-(SP)
MOVE.W D0,D4
MOVE.W D0,D5
SUBQ.W #2,D5 ;D2 = LOOP COUNTER.
;Since DBRA stops at FFFF we can't use it as our multiplier.
;If we did, we'd always return 0!
.loop:
SUBQ.L #1,D4
MOVE.L D1,-(SP)
MOVE.L D4,D1
JSR MULU_48 ;multiplies D0.L by D1.W
EXG D0,D1 ;output is in D1 so we need to put it in D0
MOVE.L (SP)+,D1
DBRA D5,.loop
MOVEM.L (SP)+,D4-D5
RTS
.isZero:
.isOne:
MOVEQ #1,D0
RTS
MULU_48:
;"48-BIT" MULTIPLICATION.
;OUTPUTS HIGH LONG IN D0, LOW LONG IN D1
;INPUT: D0.L, D1.W = FACTORS
MOVEM.L D2-D7,-(SP)
SWAP D1
CLR.W D1
SWAP D1 ;CLEAR THE TOP WORD OF D1.
MOVE.L D1,D2
EXG D0,D1 ;D1 IS OUR BASE VALUE, WE'LL USE BIT SHIFTS TO REPEATEDLY MULTIPLY.
MOVEQ #0,D0 ;CLEAR UPPER LONG OF PRODUCT
MOVE.L D1,D3 ;BACKUP OF "D1" (WHICH USED TO BE D0)
;EXAMPLE: $40000000*$225 = ($40000000 << 9) + ($40000000 << 5) + ($40000000 << 2) + $40000000
;FACTOR OUT AS MANY POWERS OF 2 AS POSSIBLE.
MOVEQ #0,D0
LSR.L #1,D2
BCS .wasOdd ;if odd, leave D1 alone. Otherwise, clear it. This is our +1 for an odd second operand.
MOVEQ #0,D1
.wasOdd:
MOVEQ #31-1,D6 ;30 BITS TO CHECK
MOVEQ #1-1,D7 ;START AT BIT 1, MINUS 1 IS FOR DBRA CORRECTION FACTOR
.shiftloop:
LSR.L #1,D2
BCC .noShift
MOVE.W D7,-(SP)
MOVEQ #0,D4
MOVE.L D3,D5
.innershiftloop:
ANDI #%00001111,CCR ;clear extend flag
ROXL.L D5
ROXL.L D4
DBRA D7,.innershiftloop
ANDI #%00001111,CCR
ADDX.L D5,D1
ADDX.L D4,D0
MOVE.W (SP)+,D7
.noShift:
addq.l #1,d7
dbra d6,.shiftloop
MOVEM.L (SP)+,D2-D7
RTS
- Output:
10! = 0x375F00 or 3,628,800
AArch64 Assembly[edit]
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program factorial64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessLargeNumber: .asciz "Number N to large. \n"
szMessNegNumber: .asciz "Number N is negative. \n"
szMessResult: .asciz "Resultat = @ \n" // message result
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
mov x0,#-5
bl factorial
mov x0,#10
bl factorial
mov x0,#20
bl factorial
mov x0,#30
bl factorial
100: // standard end of the program
mov x0,0 // return code
mov x8,EXIT // request to exit program
svc 0 // perform the system call
/********************************************/
/* calculation */
/********************************************/
/* x0 contains number N */
factorial:
stp x1,lr,[sp,-16]! // save registers
cmp x0,#0
blt 99f
beq 100f
cmp x0,#1
beq 100f
bl calFactorial
cmp x0,#-1 // overflow ?
beq 98f
ldr x1,qAdrsZoneConv
bl conversion10
ldr x0,qAdrszMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
b 100f
98: // display error message
ldr x0,qAdrszMessLargeNumber
bl affichageMess
b 100f
99: // display error message
ldr x0,qAdrszMessNegNumber
bl affichageMess
100:
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
qAdrszMessNegNumber: .quad szMessNegNumber
qAdrszMessLargeNumber: .quad szMessLargeNumber
qAdrsZoneConv: .quad sZoneConv
qAdrszMessResult: .quad szMessResult
/******************************************************************/
/* calculation */
/******************************************************************/
/* x0 contains the number N */
calFactorial:
cmp x0,1 // N = 1 ?
beq 100f // yes -> return
stp x20,lr,[sp,-16]! // save registers
mov x20,x0 // save N in x20
sub x0,x0,1 // call function with N - 1
bl calFactorial
cmp x0,-1 // error overflow ?
beq 99f // yes -> return
mul x10,x20,x0 // multiply result by N
umulh x11,x20,x0 // x11 is the hi rd if <> 0 overflow
cmp x11,0
mov x11,-1 // if overflow -1 -> x0
csel x0,x10,x11,eq // else x0 = x10
99:
ldp x20,lr,[sp],16 // restaur 2 registers
100:
ret // return to address lr x30
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
- Output:
Number N is negative. Resultat = 3628800 Resultat = 2432902008176640000 Number N to large.
ABAP[edit]
Iterative[edit]
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.
Recursive[edit]
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.
Action![edit]
Action! language does not support recursion. Another limitation are integer variables of size up to 16-bit.
CARD FUNC Factorial(INT n BYTE POINTER err)
CARD i,res
IF n<0 THEN
err^=1 RETURN (0)
ELSEIF n>8 THEN
err^=2 RETURN (0)
FI
res=1
FOR i=2 TO n
DO
res=res*i
OD
err^=0
RETURN (res)
PROC Main()
INT i,f
BYTE err
FOR i=-2 TO 10
DO
f=Factorial(i,@err)
IF err=0 THEN
PrintF("%I!=%U%E",i,f)
ELSEIF err=1 THEN
PrintF("%I is negative value%E",i)
ELSE
PrintF("%I! is to big%E",i)
FI
OD
RETURN
- Output:
Screenshot from Atari 8-bit computer
-2 is negative value -1 is negative value 0!=1 1!=1 2!=2 3!=6 4!=24 5!=120 6!=720 7!=5040 8!=40320 9! is to big 10! is to big
ActionScript[edit]
Iterative[edit]
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;
}
Recursive[edit]
public static function factorial(n:int):int
{
if (n < 0)
return 0;
if (n == 0)
return 1;
return n * factorial(n - 1);
}
Ada[edit]
Iterative[edit]
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;
Recursive[edit]
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;
Numerical Approximation[edit]
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)
Agda[edit]
factorial : ℕ → ℕ
factorial zero = 1
factorial (suc n) = suc n * factorial n
Aime[edit]
Iterative[edit]
integer
factorial(integer n)
{
integer i, result;
result = 1;
i = 1;
while (i < n) {
i += 1;
result *= i;
}
return result;
}
ALGOL 60[edit]
begin
comment factorial - algol 60;
integer procedure factorial(n); integer n;
begin
integer i,fact;
fact:=1;
for i:=2 step 1 until n do
fact:=fact*i;
factorial:=fact
end;
integer i;
for i:=1 step 1 until 10 do outinteger(1,factorial(i));
outstring(1,"\n")
end
- Output:
1 2 6 24 120 720 5040 40320 362880 3628800
ALGOL 68[edit]
Iterative[edit]
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[edit]
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
Recursive[edit]
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
; ~
ALGOL W[edit]
Iterative solution
begin
% computes factorial n iteratively %
integer procedure factorial( integer value n ) ;
if n < 2
then 1
else begin
integer f;
f := 2;
for i := 3 until n do f := f * i;
f
end factorial ;
for t := 0 until 10 do write( "factorial: ", t, factorial( t ) );
end.
ALGOL-M[edit]
INTEGER FUNCTION FACTORIAL( N ); INTEGER N;
BEGIN
INTEGER I, FACT;
FACT := 1;
FOR I := 2 STEP 1 UNTIL N DO
FACT := FACT * I;
FACTORIAL := FACT;
END;
AmigaE[edit]
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
AntLang[edit]
AntLang is a functional language, but it isn't made for recursion - it's made for list processing.
factorial:{1 */ 1+range[x]} /Call: factorial[1000]
Apex[edit]
Iterative[edit]
public static long fact(final Integer n) {
if (n < 0) {
System.debug('No negative numbers');
return 0;
}
long ans = 1;
for (Integer i = 1; i <= n; i++) {
ans *= i;
}
return ans;
}
Recursive[edit]
public static long factRec(final Integer n) {
if (n < 0){
System.debug('No negative numbers');
return 0;
}
return (n < 2) ? 1 : n * fact(n - 1);
}
APL[edit]
Both GNU APL and the DYALOG dialect of APL provides a factorial function:
!6
720
But, if we want to reimplement it, we can start by noting that n! is found by multiplying together a vector of integers 1, 2... n. This definition ('multiply'—'together'—'integers from 1 to'—'n') can be expressed directly in APL notation:
FACTORIAL←{×/⍳⍵} ⍝ OR: FACTORIAL←×/⍳
And the resulting function can then be used instead of the (admittedly more convenient) builtin one:
FACTORIAL 6
720
AppleScript[edit]
Iteration[edit]
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
Recursion[edit]
Curiously, this recursive version executes a little faster than the iterative version above. (Perhaps because the iterative code is making use of list splats)
-- factorial :: Int -> Int
on factorial(x)
if x > 1 then
x * (factorial(x - 1))
else
1
end if
end factorial
Fold[edit]
We can also define factorial as product(enumFromTo(1, x)), where product is defined in terms of a fold.
------------------------ FACTORIAL -----------------------
-- factorial :: Int -> Int
on factorial(x)
product(enumFromTo(1, x))
end factorial
--------------------------- TEST -------------------------
on run
factorial(11)
--> 39916800
end run
-------------------- GENERIC FUNCTIONS -------------------
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m ≤ n then
set xs to {}
repeat with i from m to n
set end of xs to i
end repeat
xs
else
{}
end if
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- product :: [Num] -> Num
on product(xs)
script multiply
on |λ|(a, b)
a * b
end |λ|
end script
foldl(multiply, 1, xs)
end product
- Output:
39916800
Arendelle[edit]
< n > { @n = 0 , ( return , 1 ) , ( return , @n * !factorial( @n - ! ) ) }
ARM Assembly[edit]
/* ARM assembly Raspberry PI */
/* program factorial.s */
/* Constantes */
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessLargeNumber: .asciz "Number N to large. \n"
szMessNegNumber: .asciz "Number N is negative. \n"
szMessResult: .ascii "Resultat = " @ message result
sMessValeur: .fill 12, 1, ' '
.asciz "\n"
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
push {fp,lr} @ saves 2 registers
mov r0,#-5
bl factorial
mov r0,#10
bl factorial
mov r0,#20
bl factorial
100: @ standard end of the program
mov r0, #0 @ return code
pop {fp,lr} @restaur 2 registers
mov r7, #EXIT @ request to exit program
swi 0 @ perform the system call
/********************************************/
/* calculation */
/********************************************/
/* r0 contains number N */
factorial:
push {r1,r2,lr} @ save registres
cmp r0,#0
blt 99f
beq 100f
cmp r0,#1
beq 100f
bl calFactorial
cmp r0,#-1 @ overflow ?
beq 98f
ldr r1,iAdrsMessValeur
bl conversion10 @ call function with 2 parameter (r0,r1)
ldr r0,iAdrszMessResult
bl affichageMess @ display message
b 100f
98: @ display error message
ldr r0,iAdrszMessLargeNumber
bl affichageMess
b 100f
99: @ display error message
ldr r0,iAdrszMessNegNumber
bl affichageMess
100:
pop {r1,r2,lr} @ restaur registers
bx lr @ return
iAdrszMessNegNumber: .int szMessNegNumber
iAdrszMessLargeNumber: .int szMessLargeNumber
iAdrsMessValeur: .int sMessValeur
iAdrszMessResult: .int szMessResult
/******************************************************************/
/* calculation */
/******************************************************************/
/* r0 contains the number N */
calFactorial:
cmp r0,#1 @ N = 1 ?
bxeq lr @ yes -> return
push {fp,lr} @ save registers
sub sp,#4 @ 4 byte on the stack
mov fp,sp @ fp <- start address stack
str r0,[fp] @ fp contains N
sub r0,#1 @ call function with N - 1
bl calFactorial
cmp r0,#-1 @ error overflow ?
beq 100f @ yes -> return
ldr r1,[fp] @ load N
umull r0,r2,r1,r0 @ multiply result by N
cmp r2,#0 @ r2 is the hi rd if <> 0 overflow
movne r0,#-1 @ if overflow -1 -> r0
100:
add sp,#4 @ free 4 bytes on stack
pop {fp,lr} @ restau2 registers
bx lr @ return
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {fp,lr} /* save registres */
push {r0,r1,r2,r7} /* save others registers */
mov r2,#0 /* counter length */
1: /* loop length calculation */
ldrb r1,[r0,r2] /* read octet start position + index */
cmp r1,#0 /* if 0 its over */
addne r2,r2,#1 /* else add 1 in the length */
bne 1b /* and loop */
/* so here r2 contains the length of the message */
mov r1,r0 /* address message in r1 */
mov r0,#STDOUT /* code to write to the standard output Linux */
mov r7, #WRITE /* code call system "write" */
swi #0 /* call systeme */
pop {r0,r1,r2,r7} /* restaur others registers */
pop {fp,lr} /* restaur des 2 registres */
bx lr /* return */
/******************************************************************/
/* Converting a register to a decimal */
/******************************************************************/
/* r0 contains value and r1 address area */
conversion10:
push {r1-r4,lr} /* save registers */
mov r3,r1
mov r2,#10
1: @ start loop
bl divisionpar10 @ r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
sub r2,#1 @ previous position
cmp r0,#0 @ stop if quotient = 0 */
bne 1b @ else loop
@ and move spaves in first on area
mov r1,#' ' @ space
2:
strb r1,[r3,r2] @ store space in area
subs r2,#1 @ @ previous position
bge 2b @ loop if r2 >= zéro
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/
/* division par 10 signé */
/* Thanks to http://thinkingeek.com/arm-assembler-raspberry-pi/*
/* and http://www.hackersdelight.org/ */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10:
/* r0 contains the argument to be divided by 10 */
push {r2-r4} /* save registers */
mov r4,r0
ldr r3, .Ls_magic_number_10 /* r1 <- magic_number */
smull r1, r2, r3, r0 /* r1 <- Lower32Bits(r1*r0). r2 <- Upper32Bits(r1*r0) */
mov r2, r2, ASR #2 /* r2 <- r2 >> 2 */
mov r1, r0, LSR #31 /* r1 <- r0 >> 31 */
add r0, r2, r1 /* r0 <- r2 + r1 */
add r2,r0,r0, lsl #2 /* r2 <- r0 * 5 */
sub r1,r4,r2, lsl #1 /* r1 <- r4 - (r2 * 2) = r4 - (r0 * 10) */
pop {r2-r4}
bx lr /* leave function */
.align 4
.Ls_magic_number_10: .word 0x66666667
ArnoldC[edit]
LISTEN TO ME VERY CAREFULLY factorial
I NEED YOUR CLOTHES YOUR BOOTS AND YOUR MOTORCYCLE n
GIVE THESE PEOPLE AIR
BECAUSE I'M GOING TO SAY PLEASE n
BULLS***
I'LL BE BACK 1
YOU HAVE NO RESPECT FOR LOGIC
HEY CHRISTMAS TREE product
YOU SET US UP @NO PROBLEMO
STICK AROUND n
GET TO THE CHOPPER product
HERE IS MY INVITATION product
YOU'RE FIRED n
ENOUGH TALK
GET TO THE CHOPPER n
HERE IS MY INVITATION n
GET DOWN @NO PROBLEMO
ENOUGH TALK
CHILL
I'LL BE BACK product
HASTA LA VISTA, BABY
Arturo[edit]
Recursive[edit]
factorial: $[n][
if? n>0 [n * factorial n-1]
else [1]
]
Fold[edit]
factorial: $[n][
fold.seed:1 1..n [a,b][a*b]
]
Product[edit]
factorial: $[n][product 1..n]
loop 1..19 [x][
print ["Factorial of" x "=" factorial x]
]
- Output:
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 Factorial of 13 = 6227020800 Factorial of 14 = 87178291200 Factorial of 15 = 1307674368000 Factorial of 16 = 20922789888000 Factorial of 17 = 355687428096000 Factorial of 18 = 6402373705728000 Factorial of 19 = 121645100408832000
AsciiDots[edit]
/---------*--~-$#-&
| /--;---\| [!]-\
| *------++--*#1/
| | /1#\ ||
[*]*{-}-*~<+*?#-.
*-------+-</
\-#0----/
ATS[edit]
Iterative[edit]
fun
fact
(
n: int
) : int = res where
{
var n: int = n
var res: int = 1
val () = while (n > 0) (res := res * n; n := n - 1)
}
Recursive[edit]
fun
factorial
(n:int): int =
if n > 0 then n * factorial(n-1) else 1
// end of [factorial]
Tail-recursive[edit]
fun
factorial
(n:int): int = let
fun loop(n: int, res: int): int =
if n > 0 then loop(n-1, n*res) else res
in
loop(n, 1)
end // end of [factorial]
AutoHotkey[edit]
Iterative[edit]
MsgBox % factorial(4)
factorial(n)
{
result := 1
Loop, % n
result *= A_Index
Return result
}
Recursive[edit]
MsgBox % factorial(4)
factorial(n)
{
return n > 1 ? n-- * factorial(n) : 1
}
AutoIt[edit]
Iterative[edit]
;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
Recursive[edit]
;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
Avail[edit]
Avail has a built-in factorial method using the standard exclamation point.
Assert: 7! = 5040;
Its implementation is quite simple, using iterative left fold_through_
.
Method "_`!" is [n : [0..1] | 1];
Method "_`!" is
[
n : [2..∞)
|
left fold 2 to n through [k : [2..∞), s : [2..∞) | k × s]
];
AWK[edit]
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
}
Axe[edit]
Iterative
Lbl FACT
1→R
For(I,1,r₁)
R*I→R
End
R
Return
Recursive
Lbl FACT
r₁??1,r₁*FACT(r₁-1)
Return
Babel[edit]
Iterative[edit]
((main
{(0 1 2 3 4 5 6 7 8 9 10)
{fact ! %d nl <<}
each})
(fact
{({dup 0 =}{ zap 1 }
{dup 1 =}{ zap 1 }
{1 }{ <- 1 {iter 1 + *} -> 1 - times })
cond}))
Recursive[edit]
((main
{(0 1 2 3 4 5 6 7 8 9 10)
{fact ! %d nl <<}
each})
(fact
{({dup 0 =}{ zap 1 }
{dup 1 =}{ zap 1 }
{1 }{ dup 1 - fact ! *})
cond}))
When run, either code snippet generates the following
- Output:
1 1 2 6 24 120 720 5040 40320 362880 3628800
bash[edit]
Recursive[edit]
factorial()
{
if [ $1 -le 1 ]
then
echo 1
else
result=$(factorial $[$1-1])
echo $((result*$1))
fi
}
BASIC[edit]
Iterative[edit]
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
Recursive[edit]
FUNCTION factorial (n AS Integer) AS Integer
IF n < 2 THEN
factorial = 1
ELSE
factorial = n * factorial(n-1)
END IF
END FUNCTION
Applesoft BASIC[edit]
Iterative[edit]
100 N = 4 : GOSUB 200"FACTORIAL
110 PRINT N
120 END
200 N = INT(N)
210 IF N > 1 THEN FOR I = N - 1 TO 2 STEP -1 : N = N * I : NEXT I
220 RETURN
Recursive[edit]
10 A = 768:L = 7
20 DATA 165,157,240,3
30 DATA 32,149,217,96
40 FOR I = A TO A + L
50 READ B: POKE I,B: NEXT
60 H = 256: POKE 12,A / H
70 POKE 11,A - PEEK (12) * H
80 DEF FN FA(N) = USR (N < 2) + N * FN FA(N - 1)
90 PRINT FN FA(4)
BaCon[edit]
Overflow occurs at 21 or greater. Negative values treated as 0.
' Factorial
FUNCTION factorial(NUMBER n) TYPE NUMBER
IF n <= 1 THEN
RETURN 1
ELSE
RETURN n * factorial(n - 1)
ENDIF
END FUNCTION
n = VAL(TOKEN$(ARGUMENT$, 2))
PRINT n, factorial(n) FORMAT "%ld! = %ld\n"
- Output:
prompt$ ./factorial 0 0! = 1 prompt$ ./factorial 20 20! = 2432902008176640000
BASIC256[edit]
Iterative[edit]
print "enter a number, n = ";
input n
print string(n) + "! = " + string(factorial(n))
function factorial(n)
factorial = 1
if n > 0 then
for p = 1 to n
factorial *= p
next p
end if
end function
Recursive[edit]
print "enter a number, n = ";
input n
print string(n) + "! = " + string(factorial(n))
function factorial(n)
if n > 0 then
factorial = n * factorial(n-1)
else
factorial = 1
end if
end function
BBC BASIC[edit]
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
Commodore BASIC[edit]
All numbers in Commodore BASIC are stored as floating-point with a 32-bit mantissa. The maximum representable value is 1.70141183 × 1038, so it can handle factorials up to 33! = 8.68331762 × 1036, but only keeps 32 bits of precision. That means that what you see is what you get; the mantissa for 33! is 8.68331762 exactly instead of 8.68331761881188649551819440128.
Iterative[edit]
10 REM FACTORIAL
20 REM COMMODORE BASIC 2.0
30 INPUT "N=";N: GOSUB 100
40 PRINT N;"! =";F
50 GOTO 30
100 REM FACTORIAL CALC USING SIMPLE LOOP
110 F = 1
120 FOR I=1 TO N
130 F = F*I
140 NEXT
150 RETURN
Recursive with memoization and demo[edit]
The demo stops at 13!, which is when the numbers start being formatted in scientific notation.
100 REM FACTORIAL
110 DIM F(35): F(0)=1: REM MEMOS
120 DIM S(35): SP=0: REM STACK+PTR
130 FOR I=1 TO 13
140 : S(SP)=I: SP=SP+1: REM PUSH(I)
150 : GOSUB 200
160 : SP=SP-1: REM POP
170 : PRINT I;"! = ";S(SP)
180 NEXT I
190 END
200 REM FACTORIAL: S(SP-1) = S(SP-1)!
210 IF F(S(SP-1)) THEN 240: REM MEMOIZED
220 S(SP)=S(SP-1)-1: SP=SP+1: GOSUB 200: REM RECURSE
230 SP=SP-1: F(S(SP-1))=S(SP-1)*S(SP): REM MEMOIZE
240 S(SP-1)=F(S(SP-1)): REM PUSH(RESULT)
250 RETURN
- Output:
1 ! = 1 2 ! = 2 3 ! = 6 4 ! = 24 5 ! = 120 6 ! = 720 7 ! = 5040 8 ! = 40320 9 ! = 362880 10 ! = 3628800 11 ! = 39916800 12 ! = 479001600 13 ! = 6.2270208E+09
FreeBASIC[edit]
' FB 1.05.0 Win64
Function Factorial_Iterative(n As Integer) As Integer
Var result = 1
For i As Integer = 2 To n
result *= i
Next
Return result
End Function
Function Factorial_Recursive(n As Integer) As Integer
If n = 0 Then Return 1
Return n * Factorial_Recursive(n - 1)
End Function
For i As Integer = 1 To 5
Print i; " =>"; Factorial_Iterative(i)
Next
For i As Integer = 6 To 10
Print Using "##"; i;
Print " =>"; Factorial_Recursive(i)
Next
Print
Print "Press any key to quit"
Sleep
- Output:
1 => 1 2 => 2 3 => 6 4 => 24 5 => 120 6 => 720 7 => 5040 8 => 40320 9 => 362880 10 => 3628800
FTCBASIC[edit]
define f = 1, n = 0
print "Factorial"
print "Enter an integer: " \
input n
do
let f = f * n
-1 n
loop n > 0
print f
pause
end
FutureBasic[edit]
window 1, @"Factorial", ( 0, 0, 300, 550 )
local fn factorialIterative( n as long ) as double
double f
long i
if ( n > 1 )
f = 1
for i = 2 to n
f = f * i
next
else
f = 1
end if
end fn = f
local fn factorialRecursive( n as long ) as double
double f
if ( n < 2 )
f = 1
else
f = n * fn factorialRecursive( n -1 )
end if
end fn = f
long i
for i = 0 to 12
print "Iterative:"; using "####"; i; " = "; fn factorialIterative( i )
print "Recursive:"; using "####"; i; " = "; fn factorialRecursive( i )
print
next
HandleEvents
Output:
Iterative: 0 = 1 Recursive: 0 = 1 Iterative: 1 = 1 Recursive: 1 = 1 Iterative: 2 = 2 Recursive: 2 = 2 Iterative: 3 = 6 Recursive: 3 = 6 Iterative: 4 = 24 Recursive: 4 = 24 Iterative: 5 = 120 Recursive: 5 = 120 Iterative: 6 = 720 Recursive: 6 = 720 Iterative: 7 = 5040 Recursive: 7 = 5040 Iterative: 8 = 40320 Recursive: 8 = 40320 Iterative: 9 = 362880 Recursive: 9 = 362880 Iterative: 10 = 3628800 Recursive: 10 = 3628800 Iterative: 11 = 39916800 Recursive: 11 = 39916800 Iterative: 12 = 479001600 Recursive: 12 = 479001600
Gambas[edit]
' Task: Factorial
' Language: Gambas
' Author: Sinuhe Masan (2019)
' Function factorial iterative
Function factorial_iter(num As Integer) As Long
Dim fact As Long
Dim i As Integer
fact = 1
If num > 1 Then
For i = 2 To num
fact = fact * i
Next
Endif
Return fact
End
' Function factorial recursive
Function factorial_rec(num As Integer) As Long
If num <= 1 Then
Return 1
Else
Return num * factorial_rec(num - 1)
Endif
End
Public Sub Main()
Print factorial_iter(6)
Print factorial_rec(7)
End
Output:
720 5040
GW-BASIC[edit]
10 INPUT "Enter a non/negative integer: ", N
20 IF N < 0 THEN GOTO 10
30 F# = 1
40 IF N = 0 THEN PRINT F# : END
50 F# = F# * N
60 N = N - 1
70 GOTO 40
IS-BASIC[edit]
100 DEF FACT(N)
110 LET F=1
120 FOR I=2 TO N
130 LET F=F*I
140 NEXT
150 LET FACT=F
160 END DEF
Liberty BASIC[edit]
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
Microsoft Small Basic[edit]
'Factorial - smallbasic - 05/01/2019
For n = 1 To 25
f = 1
For i = 1 To n
f = f * i
EndFor
TextWindow.WriteLine("Factorial(" + n + ")=" + f)
EndFor
- Output:
Factorial(25)=15511210043330985984000000
PowerBASIC[edit]
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
PureBasic[edit]
Iterative[edit]
Procedure factorial(n)
Protected i, f = 1
For i = 2 To n
f = f * i
Next
ProcedureReturn f
EndProcedure
Recursive[edit]
Procedure Factorial(n)
If n < 2
ProcedureReturn 1
Else
ProcedureReturn n * Factorial(n - 1)
EndIf
EndProcedure
QB64[edit]
REDIM fac#(0)
Factorial fac#(), 655, 10, power#
PRINT power#
SUB Factorial (fac#(), n&, numdigits%, power#)
power# = 0
fac#(0) = 1
remain# = 0
stx& = 0
slog# = 0
NumDiv# = 10 ^ numdigits%
FOR fac# = 1 TO n&
slog# = slog# + LOG(fac#) / LOG(10)
FOR x& = 0 TO stx&
fac#(x&) = fac#(x&) * fac# + remain#
tx# = fac#(x&) MOD NumDiv#
remain# = (fac#(x&) - tx#) / NumDiv#
fac#(x&) = tx#
NEXT
IF remain# > 0 THEN
stx& = UBOUND(fac#) + 1
REDIM _PRESERVE fac#(stx&)
fac#(stx&) = remain#
remain# = 0
END IF
NEXT
scanz& = LBOUND(fac#)
DO
IF scanz& < UBOUND(fac#) THEN
IF fac#(scanz&) THEN
EXIT DO
ELSE
scanz& = scanz& + 1
END IF
ELSE
EXIT DO
END IF
LOOP
FOR x& = UBOUND(fac#) TO scanz& STEP -1
m$ = LTRIM$(RTRIM$(STR$(fac#(x&))))
IF x& < UBOUND(fac#) THEN
WHILE LEN(m$) < numdigits%
m$ = "0" + m$
WEND
END IF
PRINT m$; " ";
power# = power# + LEN(m$)
NEXT
power# = power# + (scanz& * numdigits%) - 1
PRINT slog#
END SUB
QB64_2022[edit]
N = 18: DIM F AS DOUBLE ' Factorial.bas from Russia
F = 1: FOR I = 1 TO N: F = F * I: NEXT: PRINT F
'N = 5 F = 120
'N = 18 F = 6402373705728000
Run BASIC[edit]
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
Sinclair ZX81 BASIC[edit]
Iterative[edit]
10 INPUT N
20 LET FACT=1
30 FOR I=2 TO N
40 LET FACT=FACT*I
50 NEXT I
60 PRINT FACT
- Input:
13
- Output:
6227020800
Recursive[edit]
A GOSUB
is just a procedure call that doesn't pass parameters.
10 INPUT N
20 LET FACT=1
30 GOSUB 60
40 PRINT FACT
50 STOP
60 IF N=0 THEN RETURN
70 LET FACT=FACT*N
80 LET N=N-1
90 GOSUB 60
100 RETURN
- Input:
13
- Output:
6227020800
TI-83 BASIC[edit]
TI-83 BASIC has a built-in factorial operator: x! is the factorial of x. An other way is to use a combination of prod() and seq() functions:
10→N
N! ---> 362880
prod(seq(I,I,1,N)) ---> 362880
Note: maximum integer value is:
13! ---> 6227020800
TI-89 BASIC[edit]
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:
Tiny BASIC[edit]
10 LET F = 1
20 PRINT "Enter an integer."
30 INPUT N
40 IF N = 0 THEN GOTO 80
50 LET F = F * N
60 LET N = N - 1
70 GOTO 40
80 PRINT F
90 END
Tiny Craft Basic[edit]
10 let f = 1
20 print "factorial"
30 input "enter an integer (1-34): ", n
40 rem loop
60 let f = f * n
70 let n = n - 1
80 if n > 0 then 40
90 print f
100 shell "pause"
True BASIC[edit]
Iterative[edit]
DEF FNfactorial(n)
LET f = 1
FOR i = 2 TO n
LET f = f*i
NEXT i
LET FNfactorial = f
END DEF
END
Recursive[edit]
DEF FNfactorial(n)
IF n < 2 THEN
LET FNfactorial = 1
ELSE
LET FNfactorial = n * FNfactorial(n-1)
END IF
END DEF
END
VBA[edit]
Public Function factorial(n As Integer) As Long
factorial = WorksheetFunction.Fact(n)
End Function
For numbers < 170 only
Option Explicit
Sub Main()
Dim i As Integer
For i = 1 To 17
Debug.Print "Factorial " & i & " , recursive : " & FactRec(i) & ", iterative : " & FactIter(i)
Next
Debug.Print "Factorial 120, recursive : " & FactRec(120) & ", iterative : " & FactIter(120)
End Sub
Private Function FactRec(Nb As Integer) As String
If Nb > 170 Or Nb < 0 Then FactRec = 0: Exit Function
If Nb = 1 Or Nb = 0 Then
FactRec = 1
Else
FactRec = Nb * FactRec(Nb - 1)
End If
End Function
Private Function FactIter(Nb As Integer)
If Nb > 170 Or Nb < 0 Then FactIter = 0: Exit Function
Dim i As Integer, F
F = 1
For i = 1 To Nb
F = F * i
Next i
FactIter = F
End Function
- Output:
Factorial 1 , recursive : 1, iterative : 1 Factorial 2 , recursive : 2, iterative : 2 Factorial 3 , recursive : 6, iterative : 6 Factorial 4 , recursive : 24, iterative : 24 Factorial 5 , recursive : 120, iterative : 120 Factorial 6 , recursive : 720, iterative : 720 Factorial 7 , recursive : 5040, iterative : 5040 Factorial 8 , recursive : 40320, iterative : 40320 Factorial 9 , recursive : 362880, iterative : 362880 Factorial 10 , recursive : 3628800, iterative : 3628800 Factorial 11 , recursive : 39916800, iterative : 39916800 Factorial 12 , recursive : 479001600, iterative : 479001600 Factorial 13 , recursive : 6227020800, iterative : 6227020800 Factorial 14 , recursive : 87178291200, iterative : 87178291200 Factorial 15 , recursive : 1307674368000, iterative : 1307674368000 Factorial 16 , recursive : 20922789888000, iterative : 20922789888000 Factorial 17 , recursive : 355687428096000, iterative : 355687428096000 Factorial 120, recursive : 6,68950291344919E+198, iterative : 6,68950291344912E+198
VBScript[edit]
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
Visual Basic[edit]
Option Explicit
Sub Main()
Dim i As Variant
For i = 1 To 27
Debug.Print "Factorial(" & i & ")= , recursive : " & Format$(FactRec(i), "#,###") & " - iterative : " & Format$(FactIter(i), "#,####")
Next
End Sub 'Main
Private Function FactRec(n As Variant) As Variant
n = CDec(n)
If n = 1 Then
FactRec = 1#
Else
FactRec = n * FactRec(n - 1)
End If
End Function 'FactRec
Private Function FactIter(n As Variant)
Dim i As Variant, f As Variant
f = 1#
For i = 1# To CDec(n)
f = f * i
Next i
FactIter = f
End Function 'FactIter
- Output:
Factorial(1)= , recursive : 1 - iterative : 1 Factorial(2)= , recursive : 2 - iterative : 2 Factorial(3)= , recursive : 6 - iterative : 6 Factorial(4)= , recursive : 24 - iterative : 24 Factorial(5)= , recursive : 120 - iterative : 120 Factorial(6)= , recursive : 720 - iterative : 720 Factorial(7)= , recursive : 5,040 - iterative : 5,040 Factorial(8)= , recursive : 40,320 - iterative : 40,320 Factorial(9)= , recursive : 362,880 - iterative : 362,880 Factorial(10)= , recursive : 3,628,800 - iterative : 3,628,800 Factorial(11)= , recursive : 39,916,800 - iterative : 39,916,800 Factorial(12)= , recursive : 479,001,600 - iterative : 479,001,600 Factorial(13)= , recursive : 6,227,020,800 - iterative : 6,227,020,800 Factorial(14)= , recursive : 87,178,291,200 - iterative : 87,178,291,200 Factorial(15)= , recursive : 1,307,674,368,000 - iterative : 1,307,674,368,000 Factorial(16)= , recursive : 20,922,789,888,000 - iterative : 20,922,789,888,000 Factorial(17)= , recursive : 355,687,428,096,000 - iterative : 355,687,428,096,000 Factorial(18)= , recursive : 6,402,373,705,728,000 - iterative : 6,402,373,705,728,000 Factorial(19)= , recursive : 121,645,100,408,832,000 - iterative : 121,645,100,408,832,000 Factorial(20)= , recursive : 2,432,902,008,176,640,000 - iterative : 2,432,902,008,176,640,000 Factorial(21)= , recursive : 51,090,942,171,709,440,000 - iterative : 51,090,942,171,709,440,000 Factorial(22)= , recursive : 1,124,000,727,777,607,680,000 - iterative : 1,124,000,727,777,607,680,000 Factorial(23)= , recursive : 25,852,016,738,884,976,640,000 - iterative : 25,852,016,738,884,976,640,000 Factorial(24)= , recursive : 620,448,401,733,239,439,360,000 - iterative : 620,448,401,733,239,439,360,000 Factorial(25)= , recursive : 15,511,210,043,330,985,984,000,000 - iterative : 15,511,210,043,330,985,984,000,000 Factorial(26)= , recursive : 403,291,461,126,605,635,584,000,000 - iterative : 403,291,461,126,605,635,584,000,000 Factorial(27)= , recursive : 10,888,869,450,418,352,160,768,000,000 - iterative : 10,888,869,450,418,352,160,768,000,000
Visual Basic .NET[edit]
Various type implementations follow. No error checking, so don't try to evaluate a number less than zero, or too large of a number.
Imports System
Imports System.Numerics
Imports System.Linq
Module Module1
' Type Double:
Function DofactorialI(n As Integer) As Double ' Iterative
DofactorialI = 1 : For i As Integer = 1 To n : DofactorialI *= i : Next
End Function
' Type Unsigned Long:
Function ULfactorialI(n As Integer) As ULong ' Iterative
ULfactorialI = 1 : For i As Integer = 1 To n : ULfactorialI *= i : Next
End Function
' Type Decimal:
Function DefactorialI(n As Integer) As Decimal ' Iterative
DefactorialI = 1 : For i As Integer = 1 To n : DefactorialI *= i : Next
End Function
' Extends precision by "dehydrating" and "rehydrating" the powers of ten
Function DxfactorialI(n As Integer) As String ' Iterative
Dim factorial as Decimal = 1, zeros as integer = 0
For i As Integer = 1 To n : factorial *= i
If factorial Mod 10 = 0 Then factorial /= 10 : zeros += 1
Next : Return factorial.ToString() & New String("0", zeros)
End Function
' Arbitrary Precision:
Function FactorialI(n As Integer) As BigInteger ' Iterative
factorialI = 1 : For i As Integer = 1 To n : factorialI *= i : Next
End Function
Function Factorial(number As Integer) As BigInteger ' Functional
Return Enumerable.Range(1, number).Aggregate(New BigInteger(1),
Function(acc, num) acc * num)
End Function
Sub Main()
Console.WriteLine("Double : {0}! = {1:0}", 20, DoFactorialI(20))
Console.WriteLine("ULong : {0}! = {1:0}", 20, ULFactorialI(20))
Console.WriteLine("Decimal : {0}! = {1:0}", 27, DeFactorialI(27))
Console.WriteLine("Dec.Ext : {0}! = {1:0}", 32, DxFactorialI(32))
Console.WriteLine("Arb.Prec: {0}! = {1}", 250, Factorial(250))
End Sub
End Module
- Output:
Note that the first four are the maximum possible for their type without causing a run-time error.
Double : 20! = 2432902008176640000 ULong : 20! = 2432902008176640000 Decimal : 27! = 10888869450418352160768000000 Dec.Ext : 32! = 263130836933693530167218012160000000 Arb.Prec: 250! = 3232856260909107732320814552024368470994843717673780666747942427112823747555111209488817915371028199450928507353189432926730931712808990822791030279071281921676527240189264733218041186261006832925365133678939089569935713530175040513178760077247933065402339006164825552248819436572586057399222641254832982204849137721776650641276858807153128978777672951913990844377478702589172973255150283241787320658188482062478582659808848825548800000000000000000000000000000000000000000000000000000000000000
Yabasic[edit]
// recursive
sub factorial(n)
if n > 1 then return n * factorial(n - 1) else return 1 end if
end sub
//iterative
sub factorial2(n)
local i, t
t = 1
for i = 1 to n
t = t * i
next
return t
end sub
for n = 0 to 9
print "Factorial(", n, ") = ", factorial(n)
next
ZX Spectrum Basic[edit]
Iterative[edit]
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
Recursive[edit]
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))
Some little tricks with string slicing can get us there though:
DEF FN f(n) = VAL "n*FN f(n-1)*1"((n<1)*10+1 TO )
(lack of spaces important) will jump to the 11th character of the string ("1") on the last iteration, allowing the function call to unroll.
Batch File[edit]
@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
bc[edit]
#! /usr/bin/bc -q
define f(x) {
if (x <= 1) return (1); return (f(x-1) * x)
}
f(1000)
quit
Beads[edit]
beads 1 program Factorial
// only works for cardinal numbers 0..N
calc main_init
log to_str(Iterative(4)) // 24
log to_str(Recursive(5)) // 120
calc Iterative(
n:num -- number of iterations
):num -- result
var total = 1
loop from:2 to:n index:ix
total = ix * total
return total
calc Recursive ditto
if n <= 1
return 1
else
return n * Recursive(n-1)
- Output:
24 120
beeswax[edit]
Infinite loop for entering n
and getting the result n!
:
p <
_>1FT"pF>M"p~.~d
>Pd >~{Np
d <
Calculate n!
only once:
p <
_1FT"pF>M"p~.~d
>Pd >~{;
Limits for UInt64 numbers apply to both examples.
Examples:
i
indicates that the program expects the user to enter an integer.
julia> beeswax("factorial.bswx")
i0
1
i1
1
i2
2
i3
6
i10
3628800
i22
17196083355034583040
Input of negative numbers forces the program to quit with an error message.
Befunge[edit]
&1\> :v v *<
^-1:_$>\:|
@.$<
BQN[edit]
Fac ← ×´1+↕
! 720 ≡ Fac 6
Bracmat[edit]
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
Brainf***[edit]
Prints sequential factorials in an infinite loop.
>++++++++++>>>+>+[>>>+[-[<<<<<[+<<<<<]>>[[-]>[<<+>+>-]<[>+<-]<[>+<-[>+<-[>
+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>>>>+>+<<<<<<-[>+<-]]]]]]]]]]]>[<+>-
]+>>>>>]<<<<<[<<<<<]>>>>>>>[>>>>>]++[-<<<<<]>>>>>>-]+>>>>>]<[>++<-]<<<<[<[
>+<-]<<<<]>>[->[-]++++++[<++++++++>-]>>>>]<<<<<[<[>+>+<<-]>.<<<<<]>.>>>>]
Brat[edit]
factorial = { x |
true? x == 0 1 { x * factorial(x - 1)}
}
Burlesque[edit]
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
C[edit]
Iterative[edit]
int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; ++i)
result *= i;
return result;
}
Handle negative n (returning -1)
int factorialSafe(int n) {
int result = 1;
if(n<0)
return -1;
for (int i = 1; i <= n; ++i)
result *= i;
return result;
}
Recursive[edit]
int factorial(int n) {
return n == 0 ? 1 : n * factorial(n - 1);
}
Handle negative n (returning -1).
int factorialSafe(int n) {
return n<0 ? -1 : n == 0 ? 1 : n * factorialSafe(n - 1);
}
Tail Recursive[edit]
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 fac_auxSafe(int n, int acc) {
return n<0 ? -1 : n < 1 ? acc : fac_aux(n - 1, acc * n);
}
int factorial(int n) {
return fac_aux(n, 1);
}
Obfuscated[edit]
This is simply beautiful, 1995 IOCCC winning entry by Michael Savastio, largest factorial possible : 429539!
#include <stdio.h>
#define l11l 0xFFFF
#define ll1 for
#define ll111 if
#define l1l1 unsigned
#define l111 struct
#define lll11 short
#define ll11l long
#define ll1ll putchar
#define l1l1l(l) l=malloc(sizeof(l111 llll1));l->lll1l=1-1;l->ll1l1=1-1;
#define l1ll1 *lllll++=l1ll%10000;l1ll/=10000;
#define l1lll ll111(!l1->lll1l){l1l1l(l1->lll1l);l1->lll1l->ll1l1=l1;}\
lllll=(l1=l1->lll1l)->lll;ll=1-1;
#define llll 1000
l111 llll1 {
l111 llll1 *
lll1l,*ll1l1 ;l1l1 lll11 lll [
llll];};main (){l111 llll1 *ll11,*l1l,*
l1, *ll1l, * malloc ( ) ; l1l1 ll11l l1ll ;
ll11l l11,ll ,l;l1l1 lll11 *lll1,* lllll; ll1(l
=1-1 ;l< 14; ll1ll("\t\"8)>l\"9!.)>vl" [l]^'L'),++l
);scanf("%d",&l);l1l1l(l1l) l1l1l(ll11 ) (l1=l1l)->
lll[l1l->lll[1-1] =1]=l11l;ll1(l11 =1+1;l11<=l;
++l11){l1=ll11; lll1 = (ll1l=( ll11=l1l))->
lll; lllll =( l1l=l1)->lll; ll=(l1ll=1-1
);ll1(;ll1l-> lll1l||l11l!= *lll1;){l1ll
+=l11**lll1++ ;l1ll1 ll111 (++ll>llll){
l1lll lll1=( ll1l =ll1l-> lll1l)->lll;
}}ll1(;l1ll; ){l1ll1 ll111 (++ll>=llll)
{ l1lll} } * lllll=l11l;}
ll1(l=(ll=1- 1);(l<llll)&&
(l1->lll[ l] !=l11l);++l); ll1 (;l1;l1=
l1->ll1l1,l= llll){ll1(--l ;l>=1-1;--l,
++ll)printf( (ll)?((ll%19) ?"%04d":(ll=
19,"\n%04d") ):"%4d",l1-> lll[l] ) ; }
ll1ll(10); }
C#[edit]
Iterative[edit]
using System;
class Program
{
static int Factorial(int number)
{
if(number < 0)
throw new ArgumentOutOfRangeException(nameof(number), number, "Must be zero or a positive number.");
var accumulator = 1;
for (var factor = 1; factor <= number; factor++)
{
accumulator *= factor;
}
return accumulator;
}
static void Main()
{
Console.WriteLine(Factorial(10));
}
}
Recursive[edit]
using System;
class Program
{
static int Factorial(int number)
{
if(number < 0)
throw new ArgumentOutOfRangeException(nameof(number), number, "Must be zero or a positive number.");
return number == 0 ? 1 : number * Factorial(number - 1);
}
static void Main()
{
Console.WriteLine(Factorial(10));
}
}
Tail Recursive[edit]
using System;
class Program
{
static int Factorial(int number)
{
if(number < 0)
throw new ArgumentOutOfRangeException(nameof(number), number, "Must be zero or a positive number.");
return Factorial(number, 1);
}
static int Factorial(int number, int accumulator)
{
if(number < 0)
throw new ArgumentOutOfRangeException(nameof(number), number, "Must be zero or a positive number.");
if(accumulator < 1)
throw new ArgumentOutOfRangeException(nameof(accumulator), accumulator, "Must be a positive number.");
return number == 0 ? accumulator : Factorial(number - 1, number * accumulator);
}
static void Main()
{
Console.WriteLine(Factorial(10));
}
}
Functional[edit]
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));
}
}
Arbitrary Precision[edit]
Factorial()
can calculate 200000! in around 40 seconds over at Tio.run.
FactorialQ()
can calculate 1000000! in around 40 seconds over at Tio.run.
The "product tree" algorithm multiplies pairs of items on a list until there is only one item. Even though around the same number of multiply operations occurs (compared to the plain "accumulator" method), this is faster because the "bigger" numbers are generated near the end of the algorithm, instead of around halfway through. There is a significant space overhead incurred due to the creation of the temporary array to hold the partial results. The additional time overhead for array creation is negligible compared with the time savings of not dealing with the very large numbers until near the end of the algorithm.
For example, for 50!, here are the number of digits created for each product for either method:
plain:
1 1 1 2 3 3 4 5 6 7 8 9 10 11 13 14 15 16 18 19 20 22 23 24 26 27 29 30 31 33 34 36 37 39 41 42 44 45 47 48 50 52 53 55 57 58 60 62 63 65
product tree:
2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 5 5 5 6 6 6 6 6 6 6 6 6 8 11 11 11 11 11 13 21 21 23 42 65
One can see the plain method increases linearly up to the final value of 65. The product tree method stays low for quite awhile, then jumps up at the end.
For 200000!, when one sums up the number of digits of each product for all 199999 multiplications, the plain method is nearly 93 billion, while the product tree method is only about 17.3 million.
using System;
using System.Numerics;
using System.Linq;
class Program
{
static BigInteger factorial(int n) // iterative
{
BigInteger acc = 1; for (int i = 1; i <= n; i++) acc *= i; return acc;
}
static public BigInteger Factorial(int number) // functional
{
return Enumerable.Range(1, number).Aggregate(new BigInteger(1), (acc, num) => acc * num);
}
static public BI FactorialQ(int number) // functional quick, uses prodtree method
{
var s = Enumerable.Range(1, number).Select(num => new BI(num)).ToArray();
int top = s.Length, nt, i, j;
while (top > 1) {
for (i = 0, j = top, nt = top >> 1; i < nt; i++) s[i] *= s[--j];
top = nt + ((top & 1) == 1 ? 1 : 0);
}
return s[0];
}
static void Main(string[] args)
{
Console.WriteLine(Factorial(250));
}
}
- Output:
3232856260909107732320814552024368470994843717673780666747942427112823747555111209488817915371028199450928507353189432926730931712808990822791030279071281921676527240189264733218041186261006832925365133678939089569935713530175040513178760077247933065402339006164825552248819436572586057399222641254832982204849137721776650641276858807153128978777672951913990844377478702589172973255150283241787320658188482062478582659808848825548800000000000000000000000000000000000000000000000000000000000000
C++[edit]
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>());
}
Iterative[edit]
This version of the program is iterative, with a while loop.
//iteration with while
long long int factorial(long long int n)
{
long long int r = 1;
while(1<n)
r *= n--;
return r;
}
Template[edit]
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
}
Compare all Solutions (except the meta)[edit]
#include <algorithm>
#include <chrono>
#include <iostream>
#include <numeric>
#include <vector>
#include <boost/iterator/counting_iterator.hpp>
using ulli = unsigned long long int;
// bad style do-while and wrong for Factorial1(0LL) -> 0 !!!
ulli Factorial1(ulli m_nValue) {
ulli result = m_nValue;
ulli result_next;
ulli pc = m_nValue;
do {
result_next = result * (pc - 1);
result = result_next;
pc--;
} while (pc > 2);
return result;
}
// iteration with while
ulli Factorial2(ulli n) {
ulli r = 1;
while (1 < n)
r *= n--;
return r;
}
// recursive
ulli Factorial3(ulli n) {
return n < 2 ? 1 : n * Factorial3(n - 1);
}
// tail recursive
inline ulli _fac_aux(ulli n, ulli acc) {
return n < 1 ? acc : _fac_aux(n - 1, acc * n);
}
ulli Factorial4(ulli n) {
return _fac_aux(n, 1);
}
// accumulate with functor
ulli Factorial5(ulli n) {
// last is one-past-end
return std::accumulate(boost::counting_iterator<ulli>(1ULL),
boost::counting_iterator<ulli>(n + 1ULL), 1ULL,
std::multiplies<ulli>());
}
// accumulate with lambda
ulli Factorial6(ulli n) {
// last is one-past-end
return std::accumulate(boost::counting_iterator<ulli>(1ULL),
boost::counting_iterator<ulli>(n + 1ULL), 1ULL,
[](ulli a, ulli b) { return a * b; });
}
int main() {
ulli v = 20; // max value with unsigned long long int
ulli result;
std::cout << std::fixed;
using duration = std::chrono::duration<double, std::micro>;
{
auto t1 = std::chrono::high_resolution_clock::now();
result = Factorial1(v);
auto t2 = std::chrono::high_resolution_clock::now();
std::cout << "do-while(1) result " << result << " took " << duration(t2 - t1).count() << " µs\n";
}
{
auto t1 = std::chrono::high_resolution_clock::now();
result = Factorial2(v);
auto t2 = std::chrono::high_resolution_clock::now();
std::cout << "while(2) result " << result << " took " << duration(t2 - t1).count() << " µs\n";
}
{
auto t1 = std::chrono::high_resolution_clock::now();
result = Factorial3(v);
auto t2 = std::chrono::high_resolution_clock::now();
std::cout << "recursive(3) result " << result << " took " << duration(t2 - t1).count() << " µs\n";
}
{
auto t1 = std::chrono::high_resolution_clock::now();
result = Factorial3(v);
auto t2 = std::chrono::high_resolution_clock::now();
std::cout << "tail recursive(4) result " << result << " took " << duration(t2 - t1).count() << " µs\n";
}
{
auto t1 = std::chrono::high_resolution_clock::now();
result = Factorial5(v);
auto t2 = std::chrono::high_resolution_clock::now();
std::cout << "std::accumulate(5) result " << result << " took " << duration(t2 - t1).count() << " µs\n";
}
{
auto t1 = std::chrono::high_resolution_clock::now();
result = Factorial6(v);
auto t2 = std::chrono::high_resolution_clock::now();
std::cout << "std::accumulate lambda(6) result " << result << " took " << duration(t2 - t1).count() << " µs\n";
}
}
do-while(1) result 2432902008176640000 took 0.110000 µs while(2) result 2432902008176640000 took 0.078000 µs recursive(3) result 2432902008176640000 took 0.057000 µs tail recursive(4) result 2432902008176640000 took 0.056000 µs std::accumulate(5) result 2432902008176640000 took 0.056000 µs std::accumulate lambda(6) result 2432902008176640000 took 0.079000 µs
C3[edit]
Iterative[edit]
fn int factorial(int n)
{
int result = 1;
for (int i = 1; i <= n; ++i)
{
result *= i;
}
return result;
}
Recursive[edit]
fn int factorial(int n)
{
return n == 0 ? 1 : n * factorial(n - 1);
}
Recursive macro[edit]
In this case the value of x is compiled to a constant.
macro int factorial($n)
{
$if ($n == 0):
return 1;
$else:
return $n * @factorial($n - 1);
$endif;
}
fn void test()
{
int x = @factorial(10);
}
Cat[edit]
Taken direct from the Cat manual:
define rec_fac
{ dup 1 <= [pop 1] [dec rec_fac *] if }
Ceylon[edit]
shared void run() {
Integer? recursiveFactorial(Integer n) =>
switch(n <=> 0)
case(smaller) null
case(equal) 1
case(larger) if(exists f = recursiveFactorial(n - 1)) then n * f else null;
Integer? iterativeFactorial(Integer n) =>
switch(n <=> 0)
case(smaller) null
case(equal) 1
case(larger) (1:n).reduce(times);
for(Integer i in 0..10) {
print("the iterative factorial of ``i`` is ``iterativeFactorial(i) else "negative"``
and the recursive factorial of ``i`` is ``recursiveFactorial(i) else "negative"``\n");
}
}
Chapel[edit]
proc fac(n) {
var r = 1;
for i in 1..n do
r *= i;
return r;
}
Chef[edit]
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.
ChucK[edit]
Recursive[edit]
0 => int total;
fun int factorial(int i)
{
if (i == 0) return 1;
else
{
i * factorial(i - 1) => total;
}
return total;
}
// == another way
fun int factorial(int x)
{
if (x <= 1 ) return 1;
else return x * factorial (x - 1);
}
// call
factorial (5) => int answer;
// test
if ( answer == 120 ) <<<"success">>>;
Iterative[edit]
1 => int total;
fun int factorial(int i)
{
while(i > 0)
{
total * i => total;
1 -=> i;
}
return total;
}
Clay[edit]
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
}
Clio[edit]
Recursive[edit]
fn factorial n:
if n <= 1: n
else:
n * (n - 1 -> factorial)
10 -> factorial -> print
CLIPS[edit]
(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))))))
Clojure[edit]
Folding[edit]
(defn factorial [x]
(apply * (range 2 (inc x))))
Recursive[edit]
(defn factorial [x]
(if (< x 2)
1
(* x (factorial (dec x)))))
Tail recursive[edit]
(defn factorial [x]
(loop [x x
acc 1]
(if (< x 2)
acc
(recur (dec x) (* acc x)))))
CLU[edit]
factorial = proc (n: int) returns (int) signals (negative)
if n<0 then signal negative
elseif n=0 then return(1)
else return(n * factorial(n-1))
end
end factorial
start_up = proc ()
po: stream := stream$primary_output()
for i: int in int$from_to(0, 10) do
fac: int := factorial(i)
stream$putl(po, int$unparse(i) || "! = " || int$unparse(fac))
end
end start_up
- Output:
0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800
CMake[edit]
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}")
COBOL[edit]
The following functions have no need to check if their parameters are negative because they are unsigned.
Intrinsic Function[edit]
COBOL includes an intrinsic function which returns the factorial of its argument.
MOVE FUNCTION FACTORIAL(num) TO result
Iterative[edit]
IDENTIFICATION DIVISION.
FUNCTION-ID. factorial_iterative.
DATA DIVISION.
LOCAL-STORAGE SECTION.
01 i PIC 9(38).
LINKAGE SECTION.
01 n PIC 9(38).
01 ret PIC 9(38).
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
GOBACK.
END FUNCTION factorial_iterative.
Recursive[edit]
IDENTIFICATION DIVISION.
FUNCTION-ID. factorial_recursive.
DATA DIVISION.
LOCAL-STORAGE SECTION.
01 prev-n PIC 9(38).
LINKAGE SECTION.
01 n PIC 9(38).
01 ret PIC 9(38).
PROCEDURE DIVISION USING BY VALUE n RETURNING ret.
IF n = 0
MOVE 1 TO ret
ELSE
SUBTRACT 1 FROM n GIVING prev-n
MULTIPLY n BY factorial_recursive(prev-n) GIVING ret
END-IF
GOBACK.
END FUNCTION factorial_recursive.
Test[edit]
IDENTIFICATION DIVISION.
PROGRAM-ID. factorial_test.
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
REPOSITORY.
FUNCTION factorial_iterative
FUNCTION factorial_recursive.
DATA DIVISION.
LOCAL-STORAGE SECTION.
01 i PIC 9(38).
PROCEDURE DIVISION.
DISPLAY
"i = "
WITH NO ADVANCING
END-DISPLAY.
ACCEPT i END-ACCEPT.
DISPLAY SPACE END-DISPLAY.
DISPLAY
"factorial_iterative(i) = "
factorial_iterative(i)
END-DISPLAY.
DISPLAY
"factorial_recursive(i) = "
factorial_recursive(i)
END-DISPLAY.
GOBACK.
END PROGRAM factorial_test.
- Output:
i = 14 factorial_iterative(i) = 00000000000000000000000000087178291200 factorial_recursive(i) = 00000000000000000000000000087178291200
CoffeeScript[edit]
Several solutions are possible in JavaScript:
Recursive[edit]
fac = (n) ->
if n <= 1
1
else
n * fac n-1
Functional[edit]
(See MDC)fac = (n) ->
[1..n].reduce (x,y) -> x*y
Comal[edit]
Recursive:
PROC Recursive(n) CLOSED
r:=1
IF n>1 THEN
r:=n*Recursive(n-1)
ENDIF
RETURN r
ENDPROC Recursive
Comefrom0x10[edit]
This is iterative; recursion is not possible in Comefrom0x10.
n = 5 # calculates n!
acc = 1
factorial
comefrom
comefrom accumulate if n < 1
accumulate
comefrom factorial
acc = acc * n
comefrom factorial if n is 0
n = n - 1
acc # prints the result
Common Lisp[edit]
Recursive:
(defun factorial (n)
(if (zerop n) 1 (* n (factorial (1- n)))))
or
(defun factorial (n)
(if (< n 2) 1 (* n (factorial (1- n)))))
Tail Recursive:
(defun factorial (n &optional (m 1))
(if (zerop n) m (factorial (1- n) (* m n))))
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)))
Alternate solution[edit]
;; Project : Factorial
(defun factorial (n)
(cond ((= n 1) 1)
(t (* n (factorial (- n 1))))))
(format t "~a" "factorial of 8: ")
(factorial 8)
Output:
factorial of 8: 40320
Computer/zero Assembly[edit]
Both these programs find !. Values of higher than 5 are not supported, because their factorials will not fit into an unsigned byte.
Iterative[edit]
LDA x
BRZ done_i ; 0! = 1
STA i
loop_i: LDA fact
STA n
LDA i
SUB one
BRZ done_i
STA j
loop_j: LDA fact
ADD n
STA fact
LDA j
SUB one
BRZ done_j
STA j
JMP loop_j
done_j: LDA i
SUB one
STA i
JMP loop_i
done_i: LDA fact
STP
one: 1
fact: 1
i: 0
j: 0
n: 0
x: 5
Lookup[edit]
Since there is only a small range of possible values of , 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!.
LDA load
ADD x
STA load
load: LDA fact
STP
fact: 1
1
2
6
24
120
x: 5
Craft Basic[edit]
'factorial example
'accurate between 1-12
let f = 1
alert "factorial"
input "enter an integer: ", n
do
let f = f * n
let n = n - 1
loop n > 0
print f
Crystal[edit]
Iterative[edit]
def factorial(x : Int)
ans = 1
(1..x).each do |i|
ans *= i
end
return ans
end
Recursive[edit]
def factorial(x : Int)
if x <= 1
return 1
end
return x * factorial(x - 1)
end
D[edit]
Iterative Version[edit]
uint factorial(in uint n) pure nothrow @nogc
in {
assert(n <= 12);
} body {
uint result = 1;
foreach (immutable i; 1 .. n + 1)
result *= i;
return result;
}
// Computed and printed at compile-time.
pragma(msg, 12.factorial);
void main() {
import std.stdio;
// Computed and printed at run-time.
12.factorial.writeln;
}
- Output:
479001600u 479001600
Recursive Version[edit]
uint factorial(in uint n) pure nothrow @nogc
in {
assert(n <= 12);
} body {
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
// Computed and printed at compile-time.
pragma(msg, 12.factorial);
void main() {
import std.stdio;
// Computed and printed at run-time.
12.factorial.writeln;
}
(Same output.)
Functional Version[edit]
import std.stdio, std.algorithm, std.range;
uint factorial(in uint n) pure nothrow @nogc
in {
assert(n <= 12);
} body {
return reduce!q{a * b}(1u, iota(1, n + 1));
}
// Computed and printed at compile-time.
pragma(msg, 12.factorial);
void main() {
// Computed and printed at run-time.
12.factorial.writeln;
}
(Same output.)
Tail Recursive (at run-time, with DMD) Version[edit]
uint factorial(in uint n) pure nothrow
in {
assert(n <= 12);
} body {
static uint inner(uint n, uint acc) pure nothrow @nogc {
if (n < 1)
return acc;
else
return inner(n - 1, acc * n);
}
return inner(n, 1);
}
// Computed and printed at compile-time.
pragma(msg, 12.factorial);
void main() {
import std.stdio;
// Computed and printed at run-time.
12.factorial.writeln;
}
(Same output.)
Dart[edit]
Recursive[edit]
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));
}
Iterative[edit]
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));
}
dc[edit]
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
Delphi[edit]
Iterative[edit]
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.
Recursive[edit]
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.
Tail Recursive[edit]
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.
Draco[edit]
/* Note that ulong is 32 bits, so fac(12) is the largest
* supported value. This is why the input parameter
* is a byte. The parameters are all unsigned. */
proc nonrec fac(byte n) ulong:
byte i;
ulong rslt;
rslt := 1;
for i from 2 upto n do
rslt := rslt * i
od;
rslt
corp
proc nonrec main() void:
byte i;
for i from 0 upto 12 do
writeln(i:2, "! = ", fac(i):9)
od
corp
- Output:
0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800 11! = 39916800 12! = 479001600
Dragon[edit]
select "std"
factorial = 1
n = readln()
for(i=1,i<=n,++i)
{
factorial = factorial * i
}
showln "factorial of " + n + " is " + factorial
DWScript[edit]
Note that Factorial is part of the standard DWScript maths functions.
Iterative[edit]
function IterativeFactorial(n : Integer) : Integer;
var
i : Integer;
begin
Result := 1;
for i := 2 to n do
Result *= i;
end;
Recursive[edit]
function RecursiveFactorial(n : Integer) : Integer;
begin
if n>1 then
Result := RecursiveFactorial(n-1)*n
else Result := 1;
end;
Dyalect[edit]
func factorial(n) {
if n < 2 {
1
} else {
n * factorial(n - 1)
}
}
Dylan[edit]
Functional[edit]
define method factorial (n)
if (n < 1)
error("invalid argument");
else
reduce1(\*, range(from: 1, to: n))
end
end method;
Iterative[edit]
define method factorial (n)
if (n < 1)
error("invalid argument");
else
let total = 1;
for (i from n to 2 by -1)
total := total * i;
end;
total
end
end method;
Recursive[edit]
define method factorial (n)
if (n < 1)
error("invalid argument");
end;
local method loop (n)
if (n <= 2)
n
else
n * loop(n - 1)
end
end;
loop(n)
end method;
Tail recursive[edit]
define method factorial (n)
if (n < 1)
error("invalid argument");
end;
// Dylan implementations are required to perform tail call optimization so
// this is equivalent to iteration.
local method loop (n, total)
if (n <= 2)
total
else
let next = n - 1;
loop(next, total * next)
end
end;
loop(n, n)
end method;
Déjà Vu[edit]
Iterative[edit]
factorial:
1
while over:
* over
swap -- swap
drop swap
Recursive[edit]
factorial:
if dup:
* factorial -- dup
else:
1 drop
E[edit]
pragma.enable("accumulator")
def factorial(n) {
return accum 1 for i in 2..n { _ * i }
}
EasyLang[edit]
func factorial n . r .
r = 1
for i = 2 to n
r *= i
.
.
call factorial 7 r
print r
EchoLisp[edit]
Iterative[edit]
(define (fact n)
(for/product ((f (in-range 2 (1+ n)))) f))
(fact 10)
→ 3628800
Recursive with memoization[edit]
(define (fact n)
(if (zero? n) 1
(* n (fact (1- n)))))
(remember 'fact)
(fact 10)
→ 3628800
Tail recursive[edit]
(define (fact n (acc 1))
(if (zero? n) acc
(fact (1- n) (* n acc))))
(fact 10)
→ 3628800
Primitive[edit]
(factorial 10)
→ 3628800
Numerical approximation[edit]
(lib 'math)
math.lib v1.13 ® EchoLisp
(gamma 11)
→ 3628800.0000000005
Ecstasy[edit]
module ShowFactorials
{
static <Value extends IntNumber> Value factorial(Value n)
{
assert:arg n >= Value.zero();
return n <= Value.one() ? n : n * factorial(n-Value.one());
}
@Inject Console console;
void run()
{
// 128-bit test
UInt128 bigNum = 34;
console.print($"factorial({bigNum})={factorial(bigNum)}");
// 64-bit test
for (Int i : 10..-1)
{
console.print($"factorial({i})={factorial(i)}");
}
}
}
- Output:
factorial(34)=295232799039604140847618609643520000000 factorial(10)=3628800 factorial(9)=362880 factorial(8)=40320 factorial(7)=5040 factorial(6)=720 factorial(5)=120 factorial(4)=24 factorial(3)=6 factorial(2)=2 factorial(1)=1 factorial(0)=0 2023-01-19 10:14:52.716 Service "ShowFactorials" (id=1) at ^ShowFactorials (CallLaterRequest: native), fiber 1: Unhandled exception: IllegalArgument: "n >= Value.zero()": n=-1, Value.zero()=0, Value=Int at factorial(Type<IntNumber>, factorial(?)#Value) (test.x:5) at run() (test.x:19) at ^ShowFactorials (CallLaterRequest: native)
EGL[edit]
Iterative[edit]
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
Recursive[edit]
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
Eiffel[edit]
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
Ela[edit]
Tail recursive version:
fact = fact' 1L
where fact' acc 0 = acc
fact' acc n = fact' (n * acc) (n - 1)
Elixir[edit]
defmodule Factorial do
# Simple recursive function
def fac(0), do: 1
def fac(n) when n > 0, do: n * fac(n - 1)
# Tail recursive function
def fac_tail(0), do: 1
def fac_tail(n), do: fac_tail(n, 1)
def fac_tail(1, acc), do: acc
def fac_tail(n, acc) when n > 1, do: fac_tail(n - 1, acc * n)
# Tail recursive function with default parameter
def fac_default(n, acc \\ 1)
def fac_default(0, acc), do: acc
def fac_default(n, acc) when n > 0, do: fac_default(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)
# Using Enumeration features with pipe operator
def fac_pipe(0), do: 1
def fac_pipe(n) when n > 0, do: 1..n |> Enum.reduce(1, &*/2)
end
Elm[edit]
Recursive[edit]
factorial : Int -> Int
factorial n =
if n < 1 then 1 else n*factorial(n-1)
Tail Recursive[edit]
factorialAux : Int -> Int -> Int
factorialAux a acc =
if a < 2 then acc else factorialAux (a - 1) (a * acc)
factorial : Int -> Int
factorial a =
factorialAux a 1
Functional[edit]
import List exposing (product, range)
factorial : Int -> Int
factorial a =
product (range 1 a)
Emacs Lisp[edit]
;; Functional (most elegant and best suited to Lisp dialects):
(defun fact (n)
"Return the factorial of integer N, which require to be positive or 0."
;; Elisp won't do any type checking automatically, so
;; good practice would be doing that ourselves:
(if (not (and (integerp n) (>= n 0)))
(error "Function fact (N): Not a natural number or 0: %S" n))
;; But the actual code is very short:
(apply '* (number-sequence 1 n)))
;; (For N = 0, number-sequence returns the empty list, resp. nil,
;; and the * function works with zero arguments, returning 1.)
;; Recursive:
(defun fact (n)
"Return the factorial of integer N, which require to be positive or 0."
(if (not (and (integerp n) (>= n 0))) ; see above
(error "Function fact (N): Not a natural number or 0: %S" n))
(cond ; (or use an (if ...) with an else part)
((or (= n 0) (= n 1)) 1)
(t (* n (fact (1- n))))))
Both of these only work up to N = 19, beyond which arithmetic overflow seems to happen.
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"
embedded C for AVR MCU[edit]
Iterative[edit]
long factorial(int n) {
long result = 1;
do {
result *= n;
while(--n);
return result;
}
Erlang[edit]
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).
ERRE[edit]
You must use a procedure to implement factorial because ERRE has one-line FUNCTION only.
Iterative procedure:
PROCEDURE FACTORIAL(X%->F)
F=1
IF X%<>0 THEN
FOR I%=X% TO 2 STEP Ä1 DO
F=F*X%
END FOR
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)
Euphoria[edit]
Straight forward methods
Iterative[edit]
function factorial(integer n)
atom f = 1
while n > 1 do
f *= n
n -= 1
end while
return f
end function
Recursive[edit]
function factorial(integer n)
if n > 1 then
return factorial(n-1) * n
else
return 1
end if
end function
Tail Recursive[edit]
function factorial(integer n, integer acc = 1)
if n <= 0 then
return acc
else
return factorial(n-1, n*acc)
end if
end function
'Paper tape' / Virtual Machine version[edit]
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
Excel[edit]
Choose a cell and write in the function bar on the top :
=fact(5)
The result is shown as :
120
Ezhil[edit]
Recursive
நிரல்பாகம் fact ( n )
@( n == 0 ) ஆனால்
பின்கொடு 1
இல்லை
பின்கொடு n*fact( n - 1 )
முடி
முடி
பதிப்பி fact ( 10 )
F#[edit]
//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
Factor[edit]
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.
FALSE[edit]
[1\[$][$@*\1-]#%]f:
^'0- f;!.
Recursive:
[$1=~[$1-f;!*]?]f:
Fancy[edit]
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
}
Fantom[edit]
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))
}
}
Fermat[edit]
The factorial function is built in.
666!
- Output:
10106320568407814933908227081298764517575823983241454113404208073574138021 ` 03697022989202806801491012040989802203557527039339704057130729302834542423840165 ` 85642874066153029797241068282869939717688434251350949378748077490349338925526287 ` 83417618832618994264849446571616931313803111176195730515264233203896418054108160 ` 67607893067483259816815364609828668662748110385603657973284604842078094141556427 ` 70874534510059882948847250594907196772727091196506088520929434066550648022642608 ` 33579015030977811408324970137380791127776157191162033175421999994892271447526670 ` 85796752482688850461263732284539176142365823973696764537603278769322286708855475 ` 06983568164371084614056976933006577541441308350104365957229945444651724282400214 ` 05551404642962910019014384146757305529649145692697340385007641405511436428361286 ` 13304734147348086095123859660926788460671181469216252213374650499557831741950594 ` 82714722569989641408869425126104519667256749553222882671938160611697400311264211 ` 15613325735032129607297117819939038774163943817184647655275750142521290402832369 ` 63922624344456975024058167368431809068544577258472983979437818072648213608650098 ` 74936976105696120379126536366566469680224519996204004154443821032721047698220334 ` 84585960930792965695612674094739141241321020558114937361996687885348723217053605 ` 11305248710796441479213354542583576076596250213454667968837996023273163069094700 ` 42946710666392541958119313633986054565867362395523193239940480940410876723200000 ` 00000000000000000000000000000000000000000000000000000000000000000000000000000000 ` 00000000000000000000000000000000000000000000000000000000000000000000000000000000
FOCAL[edit]
1.1 F N=0,10; D 2
1.2 S N=-3; D 2
1.3 S N=100; D 2
1.4 S N=300; D 2
1.5 Q
2.1 I (N)3.1,4.1
2.2 S R=1
2.3 F I=1,N; S R=R*I
2.4 T "FACTORIAL OF ", %3.0, N, " IS ", %8.0, R, !
2.9 R
3.1 T "N IS NEGATIVE" !; D 2.9
4.1 T "FACTORIAL OF 0 IS 1" !; D 2.9
- Output:
FACTORIAL OF 0 IS 1 FACTORIAL OF = 1 IS = 1 FACTORIAL OF = 2 IS = 2 FACTORIAL OF = 3 IS = 6 FACTORIAL OF = 4 IS = 24 FACTORIAL OF = 5 IS = 120 FACTORIAL OF = 6 IS = 720 FACTORIAL OF = 7 IS = 5040 FACTORIAL OF = 8 IS = 40320 FACTORIAL OF = 9 IS = 362880 FACTORIAL OF = 10 IS = 3628800 N IS NEGATIVE FACTORIAL OF = 100 IS = 0.93325720E+158 FACTORIAL OF = 300 IS = 0.30605100E+615
The factorial of 300 is the largest one which FOCAL can compute, 301 causes an overflow.
Forth[edit]
Single Precision[edit]
: fac ( n -- n! ) 1 swap 1+ 1 ?do i * loop ;
Double Precision[edit]
On a 64 bit computer, can compute up to 33! Also does error checking. In gforth, error code -24 is "invalid numeric argument."
: factorial ( n -- d )
dup 33 u> -24 and throw
dup 2 < IF
drop 1.
ELSE
1.
rot 1+ 2 DO
i 1 m*/
LOOP
THEN ;
33 factorial d. 8683317618811886495518194401280000000 ok
-5 factorial d.
:2: Invalid numeric argument
Fortran[edit]
Fortran 90[edit]
A simple one-liner is sufficient.
nfactorial = PRODUCT((/(i, i=1,n)/))
Recursive functions were added in Fortran 90, allowing the following:
INTEGER RECURSIVE FUNCTION RECURSIVE_FACTORIAL(X) RESULT(ANS)
INTEGER, INTENT(IN) :: X
IF (X <= 1) THEN
ANS = 1
ELSE
ANS = X * RECURSIVE_FACTORIAL(X-1)
END IF
END FUNCTION RECURSIVE_FACTORIAL
FORTRAN 77[edit]
INTEGER FUNCTION MFACT(N)
INTEGER N,I,FACT
FACT=1
IF (N.EQ.0) GOTO 20
DO 10 I=1,N
FACT=FACT*I
10 CONTINUE
20 CONTINUE
MFACT = FACT
RETURN
END
friendly interactive shell[edit]
Asterisk is quoted to prevent globbing.
Iterative[edit]
function factorial
set x $argv[1]
set result 1
for i in (seq $x)
set result (expr $i '*' $result)
end
echo $result
end
Recursive[edit]
function factorial
set x $argv[1]
if [ $x -eq 1 ]
echo 1
else
expr (factorial (expr $x - 1)) '*' $x
end
end
Frink[edit]
Frink has a built-in factorial operator and function that creates arbitrarily-large numbers and caches results so that subsequent calls are fast. Some notes on its implementation:
- Factorials are calculated once and cached in memory so further recalculation is fast.
- There is a limit to the size of factorials that gets cached in memory. Currently this limit is 10000!. Numbers larger than this will not be cached, but re-calculated on demand.
- When calculating a factorial within the caching limit, say, 5000!, all of the factorials smaller than this will get calculated and cached in memory.
- Calculations of huge factorials larger than the cache limit 10000! are calculated by a binary splitting algorithm which makes them significantly faster on Java 1.8 and later. (Did you know that Java 1.8's BigInteger calculations got drastically faster because Frink's internal algorithms were contributed to it?)
- Functions that calculate binomial coefficients like binomial[m,n] are more efficient because of the use of binary splitting algorithms, especially for large numbers.
- The function factorialRatio[a, b] allows efficient calculation of the ratio of two factorials a! / b!, using a binary splitting algorithm.
// Calculate factorial with math operator
x = 5
println[x!]
// Calculate factorial with built-in function
println[factorial[x]]
Building a factorial function with no recursion
// Build factorial function with using a range and product function.
factorial2[x] := product[1 to x]
println[factorial2[5]]
Building a factorial function with recursion
factorial3[x] :=
{
if x <= 1
return 1
else
return x * factorial3[x-1] // function calling itself
}
println[factorial3[5]]
FunL[edit]
Procedural[edit]
def factorial( n ) =
if n < 0
error( 'factorial: n should be non-negative' )
else
res = 1
for i <- 2..n
res *= i
res
Recursive[edit]
def
factorial( (0|1) ) = 1
factorial( n )
| n > 0 = n*factorial( n - 1 )
| otherwise = error( 'factorial: n should be non-negative' )
Tail-recursive[edit]
def factorial( n )
| n >= 0 =
def
fact( acc, 0 ) = acc
fact( acc, n ) = fact( acc*n, n - 1 )
fact( 1, n )
| otherwise = error( 'factorial: n should be non-negative' )
Using a library function[edit]
def factorial( n )
| n >= 0 = product( 1..n )
| otherwise = error( 'factorial: n should be non-negative' )
Futhark[edit]
Recursive[edit]
fun fact(n: int): int =
if n == 0 then 1
else n * fact(n-1)
Iterative[edit]
fun fact(n: int): int =
loop (out = 1) = for i < n do
out * (i+1)
in out
GAP[edit]
# Built-in
Factorial(5);
# An implementation
fact := n -> Product([1 .. n]);
Genyris[edit]
def factorial (n)
if (< n 2) 1
* n
factorial (- n 1)
GML[edit]
n = argument0
j = 1
for(i = 1; i <= n; i += 1)
j *= i
return j
gnuplot[edit]
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)
Go[edit]
Iterative[edit]
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, exact[edit]
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))
}
Efficient exact[edit]
For a bigger step up, an algorithm fast enough to compute factorials of numbers up to a million or so, see Factorial/Go.
Built in, Gamma[edit]
package main
import (
"fmt"
"math"
)
func factorial(n float64) float64 {
return math.Gamma(n + 1)
}
func main() {
for i := 0.; i <= 10; i++ {
fmt.Println(i, factorial(i))
}
fmt.Println(100, factorial(100))
}
- Output:
0 1 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3.6288e+06 100 9.332621544394405e+157
Built in, Lgamma[edit]
package main
import (
"fmt"
"math"
"math/big"
)
func lfactorial(n float64) float64 {
l, _ := math.Lgamma(n + 1)
return l
}
func factorial(n float64) *big.Float {
i, frac := math.Modf(lfactorial(n) * math.Log2E)
z := big.NewFloat(math.Exp2(frac))
return z.SetMantExp(z, int(i))
}
func main() {
for i := 0.; i <= 10; i++ {
fmt.Println(i, factorial(i))
}
fmt.Println(100, factorial(100))
fmt.Println(800, factorial(800))
}
- Output:
0 1 1 1 2 2 3 6 4 24 5 119.99999999999994 6 720.0000000000005 7 5039.99999999999 8 40320.000000000015 9 362880.0000000001 10 3.6288000000000084e+06 100 9.332621544394454e+157 800 7.710530113351238e+1976
Golfscript[edit]
Iterative (uses folding)
{.!{1}{,{)}%{*}*}if}:fact;
5fact puts # test
or
{),(;{*}*}:fact;
Recursive
{.1<{;1}{.(fact*}if}:fact;
Gridscript[edit]
#FACTORIAL.
@width 14
@height 8
(1,3):START
(7,1):CHECKPOINT 0
(3,3):INPUT INT TO n
(5,3):STORE n
(7,3):GO EAST
(9,3):DECREMENT n
(11,3):SWITCH n
(11,5):MULTIPLY BY n
(11,7):GOTO 0
(13,3):PRINT
Groovy[edit]
Recursive[edit]
A recursive closure must be pre-declared.
def rFact
rFact = { (it > 1) ? it * rFact(it - 1) : 1 as BigInteger }
Iterative[edit]
def iFact = { (it > 1) ? (2..it).inject(1 as BigInteger) { i, j -> i*j } : 1 }
Test Program:
def time = { Closure c ->
def start = System.currentTimeMillis()
def result = c()
def elapsedMS = (System.currentTimeMillis() - start)/1000
printf '(%6.4fs elapsed)', elapsedMS
result
}
def dashes = '---------------------'
print " n! elapsed time "; (0..15).each { def length = Math.max(it - 3, 3); printf " %${length}d", it }; println()
print "--------- -----------------"; (0..15).each { def length = Math.max(it - 3, 3); print " ${dashes[0..<length]}" }; println()
[recursive:rFact, iterative:iFact].each { name, fact ->
printf "%9s ", name
def factList = time { (0..15).collect {fact(it)} }
factList.each { printf ' %3d', it }
println()
}
- Output:
n! elapsed time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --------- ----------------- --- --- --- --- --- --- --- ---- ----- ------ ------- -------- --------- ---------- ----------- ------------ recursive (0.0040s elapsed) 1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000 iterative (0.0060s elapsed) 1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000
Guish[edit]
Recursive[edit]
fact = {
if eq(@1, 0) {
return 1
} else {
return mul(@1, fact(sub(@1, 1)))
}
}
puts fact(7)
Tail recursive[edit]
fact = {
if eq(@1, 1) {
return @2
}
return fact(sub(@1, 1), mul(@1, @2))
}
puts fact(7, 1)
Haskell[edit]
The simplest description: factorial is the product of the numbers from 1 to n:
factorial n = product [1..n]
Or, using composition and omitting the argument (partial application):
factorial = product . enumFromTo 1
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)
Using postfix notation:
{-# LANGUAGE PostfixOperators #-}
(!) :: Integer -> Integer
(!) 0 = 1
(!) n = n * (pred n !)
main :: IO ()
main = do
print (5 !)
print ((4 !) !)
Binary splitting[edit]
The following method is more efficient for large numbers.
-- product of [a,a+1..b]
productFromTo a b =
if a>b then 1
else if a == b then a
else productFromTo a c * productFromTo (c+1) b
where c = (a+b) `div` 2
factorial = productFromTo 1
Haxe[edit]
Iterative[edit]
static function factorial(n:Int):Int {
var result = 1;
while (1<n)
result *= n--;
return result;
}
Recursive[edit]
static function factorial(n:Int):Int {
return n == 0 ? 1 : n * factorial2(n - 1);
}
Tail-Recursive[edit]
inline static function _fac_aux(n, acc:Int):Int {
return n < 1 ? acc : _fac_aux(n - 1, acc * n);
}
static function factorial(n:Int):Int {
return _fac_aux(n,1);
}
Functional[edit]
static function factorial(n:Int):Int {
return [for (i in 1...(n+1)) i].fold(function(num, total) return total *= num, 1);
}
Comparison[edit]
using StringTools;
using Lambda;
class Factorial {
// iterative
static function factorial1(n:Int):Int {
var result = 1;
while (1<n)
result *= n--;
return result;
}
// recursive
static function factorial2(n:Int):Int {
return n == 0 ? 1 : n * factorial2(n - 1);
}
// tail-recursive
inline static function _fac_aux(n, acc:Int):Int {
return n < 1 ? acc : _fac_aux(n - 1, acc * n);
}
static function factorial3(n:Int):Int {
return _fac_aux(n,1);
}
// functional
static function factorial4(n:Int):Int {
return [for (i in 1...(n+1)) i].fold(function(num, total) return total *= num, 1);
}
static function main() {
var v = 12;
// iterative
var start = haxe.Timer.stamp();
var result = factorial1(v);
var duration = haxe.Timer.stamp() - start;
Sys.println('iterative'.rpad(' ', 20) + 'result: $result time: $duration ms');
// recursive
start = haxe.Timer.stamp();
result = factorial2(v);
duration = haxe.Timer.stamp() - start;
Sys.println('recursive'.rpad(' ', 20) + 'result: $result time: $duration ms');
// tail-recursive
start = haxe.Timer.stamp();
result = factorial3(v);
duration = haxe.Timer.stamp() - start;
Sys.println('tail-recursive'.rpad(' ', 20) + 'result: $result time: $duration ms');
// functional
start = haxe.Timer.stamp();
result = factorial4(v);
duration = haxe.Timer.stamp() - start;
Sys.println('functional'.rpad(' ', 20) + 'result: $result time: $duration ms');
}
}
- Output:
iterative result: 479001600 time: 6.198883056640625e-06 ms recursive result: 479001600 time: 1.31130218505859375e-05 ms tail-recursive result: 479001600 time: 1.9073486328125e-06 ms functional result: 479001600 time: 1.40666961669921875e-05 ms
hexiscript[edit]
Iterative[edit]
fun fac n
let acc 1
while n > 0
let acc (acc * n--)
endwhile
return acc
endfun
Recursive[edit]
fun fac n
if n <= 0
return 1
else
return n * fac (n - 1)
endif
endfun
HicEst[edit]
WRITE(Clipboard) factorial(6) ! pasted: 720
FUNCTION factorial(n)
factorial = 1
DO i = 2, n
factorial = factorial * i
ENDDO
END
HolyC[edit]
Iterative[edit]
U64 Factorial(U64 n) {
U64 i, result = 1;
for (i = 1; i <= n; ++i)
result *= i;
return result;
}
Print("1: %d\n", Factorial(1));
Print("10: %d\n", Factorial(10));
Note: Does not support negative numbers.
Recursive[edit]
I64 Factorial(I64 n) {
if (n == 0)
return 1;
if (n < 0)
return -1 * ((-1 * n) * Factorial((-1 * n) - 1));
return n * Factorial(n - 1));
}
Print("+1: %d\n", Factorial(1));
Print("+10: %d\n", Factorial(10));
Print("-10: %d\n", Factorial(-10));
Hy[edit]
(defn ! [n]
(reduce *
(range 1 (inc n))
1))
(print (! 6)) ; 720
(print (! 0)) ; 1
i[edit]
concept factorial(n) {
return n!
}
software {
print(factorial(-23))
print(factorial(0))
print(factorial(1))
print(factorial(2))
print(factorial(3))
print(factorial(22))
}
Icon and Unicon[edit]
Recursive[edit]
Iterative[edit]
The factors provides the following iterative procedure which can be included with 'link factors':IDL[edit]
function fact,n
return, product(lindgen(n)+1)
end
Inform 6[edit]
[ factorial n;
if (n == 0)
return 1;
else
return n * factorial(n - 1);
];
Io[edit]
Factorials are built-in to Io:
3 factorial
J[edit]
Operator[edit]
! 8 NB. Built in factorial operator
40320
Iterative / Functional[edit]
*/1+i.8
40320
Recursive[edit]
(*$:@:<:)^:(1&<) 8
40320
Generalization[edit]
Factorial, like most of J's primitives, is generalized (mathematical generalization is often something to avoid in application code while being something of a curated virtue in utility code):
! 8 0.8 _0.8 NB. Generalizes as 1 + the gamma function
40320 0.931384 4.59084
! 800x NB. Also arbitrarily large
7710530113353860041446393977750283605955564018160102391634109940339708518270930693670907697955390330926478612242306774446597851526397454014801846531749097625044706382742591201733097017026108750929188168469858421505936237186038616420630788341172340985137252...
Janet[edit]
Recursive[edit]
Non-Tail Recursive[edit]
(defn factorial [x]
(cond
(< x 0) nil
(= x 0) 1
(* x (factorial (dec x)))))
Tail Recursive[edit]
Given the initial recursive sample is not using tail recursion, there is a possibility to hit a stack overflow (if the user has lowered Janet's very high default max stack size) or exhaust the host's available memory.
The recursive sample can be written with tail recursion (Janet supports TCO) to perform the algorithm in linear time and constant space, instead of linear space.
(defn factorial-iter [product counter max-count]
(if (> counter max-count)
product
(factorial-iter (* counter product) (inc counter) max-count)))
(defn factorial [n]
(factorial-iter 1 1 n))
Iterative[edit]
(defn factorial [x]
(cond
(< x 0) nil
(= x 0) 1
(do
(var fac 1)
(for i 1 (inc x)
(*= fac i))
fac)))
Functional[edit]
(defn factorial [x]
(cond
(< x 0) nil
(= x 0) 1
(product (range 1 (inc x)))))
Java[edit]
Iterative[edit]
package programas;
import java.math.BigInteger;
import java.util.InputMismatchException;
import java.util.Scanner;
public class IterativeFactorial {
public BigInteger factorial(BigInteger n) {
if ( n == null ) {
throw new IllegalArgumentException();
}
else if ( n.signum() == - 1 ) {
// negative
throw new IllegalArgumentException("Argument must be a non-negative integer");
}
else {
BigInteger factorial = BigInteger.ONE;
for ( BigInteger i = BigInteger.ONE; i.compareTo(n) < 1; i = i.add(BigInteger.ONE) ) {
factorial = factorial.multiply(i);
}
return factorial;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BigInteger number, result;
boolean error = false;
System.out.println("FACTORIAL OF A NUMBER");
do {
System.out.println("Enter a number:");
try {
number = scanner.nextBigInteger();
result = new IterativeFactorial().factorial(number);
error = false;
System.out.println("Factorial of " + number + ": " + result);
}
catch ( InputMismatchException e ) {
error = true;
scanner.nextLine();
}
catch ( IllegalArgumentException e ) {
error = true;
scanner.nextLine();
}
}
while ( error );
scanner.close();
}
}
Recursive[edit]
package programas;
import java.math.BigInteger;
import java.util.InputMismatchException;
import java.util.Scanner;
public class RecursiveFactorial {
public BigInteger factorial(BigInteger n) {
if ( n == null ) {
throw new IllegalArgumentException();
}
else if ( n.equals(BigInteger.ZERO) ) {
return BigInteger.ONE;
}
else if ( n.signum() == - 1 ) {
// negative
throw new IllegalArgumentException("Argument must be a non-negative integer");
}
else {
return n.equals(BigInteger.ONE)
? BigInteger.ONE
: factorial(n.subtract(BigInteger.ONE)).multiply(n);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BigInteger number, result;
boolean error = false;
System.out.println("FACTORIAL OF A NUMBER");
do {
System.out.println("Enter a number:");
try {
number = scanner.nextBigInteger();
result = new RecursiveFactorial().factorial(number);
error = false;
System.out.println("Factorial of " + number + ": " + result);
}
catch ( InputMismatchException e ) {
error = true;
scanner.nextLine();
}
catch ( IllegalArgumentException e ) {
error = true;
scanner.nextLine();
}
}
while ( error );
scanner.close();
}
}
Simplified and Combined Version[edit]
import java.math.BigInteger;
import java.util.InputMismatchException;
import java.util.Scanner;
public class LargeFactorial {
public static long userInput;
public static void main(String[]args){
Scanner input = new Scanner(System.in);
System.out.println("Input factorial integer base: ");
try {
userInput = input.nextLong();
System.out.println(userInput + "! is\n" + factorial(userInput) + " using standard factorial method.");
System.out.println(userInput + "! is\n" + factorialRec(userInput) + " using recursion method.");
}catch(InputMismatchException x){
System.out.println("Please give integral numbers.");
}catch(StackOverflowError ex){
if(userInput > 0) {
System.out.println("Number too big.");
}else{
System.out.println("Please give non-negative(positive) numbers.");
}
}finally {
System.exit(0);
}
}
public static BigInteger factorialRec(long n){
BigInteger result = BigInteger.ONE;
return n == 0 ? result : result.multiply(BigInteger.valueOf(n)).multiply(factorial(n-1));
}
public static BigInteger factorial(long n){
BigInteger result = BigInteger.ONE;
for(int i = 1; i <= n; i++){
result = result.multiply(BigInteger.valueOf(i));
}
return result;
}
}
JavaScript[edit]
Iterative[edit]
function factorial(n) {
//check our edge case
if (n < 0) { throw "Number must be non-negative"; }
var result = 1;
//we skip zero and one since both are 1 and are identity
while (n > 1) {
result *= n;
n--;
}
return result;
}
Recursive[edit]
ES5 (memoized )[edit]
(function(x) {
var memo = {};
function factorial(n) {
return n < 2 ? 1 : memo[n] || (memo[n] = n * factorial(n - 1));
}
return factorial(x);
})(18);
- Output:
6402373705728000
Or, assuming that we have some sort of integer range function, we can memoize using the accumulator of a fold/reduce:
(function () {
'use strict';
// factorial :: Int -> Int
function factorial(x) {
return range(1, x)
.reduce(function (a, b) {
return a * b;
}, 1);
}
// range :: Int -> Int -> [Int]
function range(m, n) {
var a = Array(n - m + 1),
i = n + 1;
while (i-- > m) a[i - m] = i;
return a;
}
return factorial(18);
})();
- Output:
6402373705728000
ES6[edit]
var factorial = n => (n < 2) ? 1 : n * factorial(n - 1);
Or, as an alternative to recursion, we can fold/reduce a product function over the range of integers 1..n
(() => {
'use strict';
// factorial :: Int -> Int
const factorial = n =>
enumFromTo(1, n)
.reduce(product, 1);
const test = () =>
factorial(18);
// --> 6402373705728000
// GENERIC FUNCTIONS ----------------------------------
// product :: Num -> Num -> Num
const product = (a, b) => a * b;
// range :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
Array.from({
length: (n - m) + 1
}, (_, i) => m + i);
// MAIN ------
return test();
})();
- Output:
6402373705728000
The first part outputs the factorial for every addition to the array and the second part calculates factorial from a single number.
<html>
<body>
<button onclick="incrementFact()">Factorial</button>
<p id="FactArray"></p>
<p id="Factorial"></p>
<br>
</body>
</html>
<input id="userInput" value="">
<br>
<button onclick="singleFact()">Single Value Factorial</button>
<p id="SingleFactArray"></p>
<p id="SingleFactorial"></p>
<script>
function mathFact(total, sum) {
return total * sum;
}
var incNumbers = [1];
function incrementFact() {
var n = incNumbers.pop();
incNumbers.push(n);
incNumbers.push(n + 1);
document.getElementById("FactArray").innerHTML = incNumbers;
document.getElementById("Factorial").innerHTML = incNumbers.reduceRight(mathFact);
}
var singleNum = [];
function singleFact() {
var x = document.getElementById("userInput").value;
for (i = 0; i < x; i++) {
singleNum.push(i + 1);
document.getElementById("SingleFactArray").innerHTML = singleNum;
}
document.getElementById("SingleFactorial").innerHTML = singleNum.reduceRight(mathFact);
singleNum = [];
}
</script>
JOVIAL[edit]
PROC FACTORIAL(ARG) U;
BEGIN
ITEM ARG U;
ITEM TEMP U;
TEMP = 1;
FOR I:2 BY 1 WHILE I<=ARG;
TEMP = TEMP*I;
FACTORIAL = TEMP;
END
Joy[edit]
<DEFINE ! == [1] [*] primrec.
6!.
jq[edit]
An efficient and idiomatic definition in jq is simply to multiply the first n integers:def fact:
reduce range(1; .+1) as $i (1; . * $i);
def fact(n):
if n <= 1 then n
else n * fact(n-1)
end;
def fact:
def _fact:
# Input: [accumulator, counter]
if .[1] <= 1 then .
else [.[0] * .[1], .[1] - 1]| _fact
end;
# Extract the accumulated value from the output of _fact:
[1, .] | _fact | .[0] ;
Jsish[edit]
/* Factorial, in Jsish */
/* recursive */
function fact(n) { return ((n < 2) ? 1 : n * fact(n - 1)); }
/* iterative */
function factorial(n:number) {
if (n < 0) throw format("factorial undefined for negative values: %d", n);
var fac = 1;
while (n > 1) fac *= n--;
return fac;
}
if (Interp.conf('unitTest') > 0) {
;fact(18);
;fact(1);
;factorial(18);
;factorial(42);
try { factorial(-1); } catch (err) { puts(err); }
}
- Output:
prompt$ jsish --U factorial.jsi fact(18) ==> 6402373705728000 fact(1) ==> 1 factorial(18) ==> 6402373705728000 factorial(42) ==> 1.40500611775288e+51 factorial undefined for negative values: -1
Julia[edit]
Built-in version:
help?> factorial search: factorial Factorization factorize factorial(n) Factorial of n. If n is an Integer, the factorial is computed as an integer (promoted to at least 64 bits). Note that this may overflow if n is not small, but you can use factorial(big(n)) to compute the result exactly in arbitrary precision. If n is not an Integer, factorial(n) is equivalent to gamma(n+1). julia> factorial(6) 720 julia> factorial(21) ERROR: OverflowError() [...] julia> factorial(21.0) 5.109094217170944e19 julia> factorial(big(21)) 51090942171709440000
Dynamic version:
function fact(n::Integer)
n < 0 && return zero(n)
f = one(n)
for i in 2:n
f *= i
end
return f
end
for i in 10:20
println("$i -> ", fact(i))
end
- Output:
10 -> 3628800 11 -> 39916800 12 -> 479001600 13 -> 6227020800 14 -> 87178291200 15 -> 1307674368000 16 -> 20922789888000 17 -> 355687428096000 18 -> 6402373705728000 19 -> 121645100408832000 20 -> 2432902008176640000
Alternative version:
fact2(n::Integer) = prod(Base.OneTo(n))
@show fact2(20)
- Output:
fact2(20) = 2432902008176640000
K[edit]
Iterative[edit]
facti:*/1+!:
facti 5
120
Recursive[edit]
factr:{:[x>1;x*_f x-1;1]}
factr 6
720
Klingphix[edit]
{ recursive }
:factorial
dup 1 great (
[dup 1 - factorial *]
[drop 1]
) if
;
{ iterative }
:factorial2
1 swap [*] for
;
( 0 22 ) [
"Factorial(" print dup print ") = " print factorial2 print nl
] for
" " input
- Output:
Factorial(0) = 1 Factorial(1) = 1 Factorial(2) = 2 Factorial(3) = 6 Factorial(4) = 24 Factorial(5) = 120 Factorial(6) = 720 Factorial(7) = 5040 Factorial(8) = 40320 Factorial(9) = 362880 Factorial(10) = 3628800 Factorial(11) = 39916800 Factorial(12) = 479001600 Factorial(13) = 6.22703e+9 Factorial(14) = 8.71783e+10 Factorial(15) = 1.30768e+12 Factorial(16) = 2.09228e+13 Factorial(17) = 3.55688e+14 Factorial(18) = 6.40238e+15 Factorial(19) = 1.21646e+17 Factorial(20) = 2.4329e+18 Factorial(21) = 5.1091e+19 Factorial(22) = 1.124e+21
Klong[edit]
Based on the K examples above.
factRecursive::{:[x>1;x*.f(x-1);1]}
factIterative::{*/1+!x}
KonsolScript[edit]
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;
}
Kotlin[edit]
fun facti(n: Int) = when {
n < 0 -> throw IllegalArgumentException("negative numbers not allowed")
else -> {
var ans = 1L
for (i in 2..n) ans *= i
ans
}
}
fun factr(n: Int): Long = when {
n < 0 -> throw IllegalArgumentException("negative numbers not allowed")
n < 2 -> 1L
else -> n * factr(n - 1)
}
fun main(args: Array<String>) {
val n = 20
println("$n! = " + facti(n))
println("$n! = " + factr(n))
}
- Output:
20! = 2432902008176640000 20! = 2432902008176640000
Lambdatalk[edit]
{def fac
{lambda {:n}
{if {< :n 1}
then 1
else {long_mult :n {fac {- :n 1}}}}}}
{fac 6}
-> 720
{fac 100}
-> 93326215443944152681699238856266700490715968264381621468592963895217599993229
915608941463976156518286253697920827223758251185210916864000000000000000000000000
Lang5[edit]
Folding[edit]
: fact iota 1 + '* reduce ;
5 fact
120
Recursive[edit]
: fact dup 2 < if else dup 1 - fact * then ;
5 fact
120
langur[edit]
Folding[edit]
val .factorial = f fold(f .x x .y, pseries .n)
writeln .factorial(7)
val .factorial = f fold(f{x}, 2 to .n)
writeln .factorial(7)
Recursive[edit]
val .factorial = f if(.x < 2: 1; .x x self(.x - 1))
writeln .factorial(7)
Iterative[edit]
val .factorial = f(.i) {
var .answer = 1
for .x in 2 to .i {
.answer x= .x
}
.answer
}
writeln .factorial(7)
Iterative Folding[edit]
val .factorial = f(.n) for[=1] .x in .n { _for x= .x }
writeln .factorial(7)
- Output:
5040
Lasso[edit]
Iterative[edit]
define factorial(n) => {
local(x = 1)
with i in generateSeries(2, #n)
do {
#x *= #i
}
return #x
}
Recursive[edit]
define factorial(n) => #n < 2 ? 1 | #n * factorial(#n - 1)
Latitude[edit]
Functional[edit]
factorial := {
1 upto ($1 + 1) product.
}.
Recursive[edit]
factorial := {
takes '[n].
if { n == 0. } then {
1.
} else {
n * factorial (n - 1).
}.
}.
Iterative[edit]
factorial := {
local 'acc = 1.
1 upto ($1 + 1) do {
acc = acc * $1.
}.
acc.
}.
LFE[edit]
Non-Tail-Recursive Versions[edit]
The non-tail-recursive versions of this function are easy to read: they look like the math textbook definitions. However, they will cause the Erlang VM to throw memory errors when passed very large numbers. To avoid such errors, use the tail-recursive version below.
Using the cond form:
(defun factorial (n)
(cond
((== n 0) 1)
((> n 0) (* n (factorial (- n 1))))))
Using guards (with the when form):
(defun factorial
((n) (when (== n 0)) 1)
((n) (when (> n 0))
(* n (factorial (- n 1)))))
Using pattern matching and a guard:
(defun factorial
((0) 1)
((n) (when (> n 0))
(* n (factorial (- n 1)))))
Tail-Recursive Version[edit]
(defun factorial (n)
(factorial n 1))
(defun factorial
((0 acc) acc)
((n acc) (when (> n 0))
(factorial (- n 1) (* n acc))))
Example usage in the REPL:
> (lists:map #'factorial/1 (lists:seq 10 20))
(3628800
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
121645100408832000
2432902008176640000)
Or, using io:format to print results to stdout:
> (lists:foreach
(lambda (x)
(io:format '"~p~n" `(,(factorial x))))
(lists:seq 10 20))
3628800
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
121645100408832000
2432902008176640000
ok
Note that the use of progn above was simply to avoid the list of oks that are generated as a result of calling io:format inside a lists:map's anonymous function.
Lingo[edit]
Recursive[edit]
on fact (n)
if n<=1 then return 1
return n * fact(n-1)
end
Iterative[edit]
on fact (n)
res = 1
repeat with i = 2 to n
res = res*i
end repeat
return res
end
Lisaac[edit]
- factorial x : INTEGER : INTEGER <- (
+ result : INTEGER;
(x <= 1).if {
result := 1;
} else {
result := x * factorial(x - 1);
};
result
);
Little Man Computer[edit]
The Little Man can cope with integers up to 999. So he can calculate up to 6 factorial before it all gets too much for him.
// Little Man Computer
// Reads an integer n and prints n factorial
// Works for n = 0..6
LDA one // initialize factorial to 1
STA fac
INP // get n from user
BRZ done // if n = 0, return 1
STA n // else store n
LDA one // initialize k = 1
outer STA k // outer loop: store latest k
LDA n // test for k = n
SUB k
BRZ done // done if so
LDA fac // save previous factorial
STA prev
LDA k // initialize i = k
inner STA i // inner loop: store latest i
LDA fac // build factorial by repeated addition
ADD prev
STA fac
LDA i // decrement i
SUB one
BRZ next_k // if i = 0, move on to next k
BRA inner // else loop for another addition
next_k LDA k // increment k
ADD one
BRA outer // back to start of outer loop
done LDA fac // done, load the result
OUT // print it
HLT // halt
n DAT 0 // input value
k DAT 0 // outer loop counter, 1 up to n
i DAT 0 // inner loop counter, k down to 0
fac DAT 0 // holds k!, i.e. n! when done
prev DAT 0 // previous value of fac
one DAT 1 // constant 1
// end
LiveCode[edit]
// recursive
function factorialr n
if n < 2 then
return 1
else
return n * factorialr(n-1)
end if
end factorialr
// using accumulator
function factorialacc n acc
if n = 0 then
return acc
else
return factorialacc(n-1, n * acc)
end if
end factorialacc
function factorial n
return factorialacc(n,1)
end factorial
// iterative
function factorialit n
put 1 into f
if n > 1 then
repeat with i = 1 to n
multiply f by i
end repeat
end if
return f
end factorialit
LLVM[edit]
; ModuleID = 'factorial.c'
; source_filename = "factorial.c"
; target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
; target triple = "x86_64-pc-windows-msvc19.21.27702"
; This is not strictly LLVM, as it uses the C library function "printf".
; LLVM does not provide a way to print values, so the alternative would be
; to just load the string into memory, and that would be boring.
; Additional comments have been inserted, as well as changes made from the output produced by clang such as putting more meaningful labels for the jumps
$"\01??_C@_04PEDNGLFL@?$CFld?6?$AA@" = comdat any
@"\01??_C@_04PEDNGLFL@?$CFld?6?$AA@" = linkonce_odr unnamed_addr constant [5 x i8] c"%ld\0A\00", comdat, align 1
;--- The declaration for the external C printf function.
declare i32 @printf(i8*, ...)
; Function Attrs: noinline nounwind optnone uwtable
define i32 @factorial(i32) #0 {
;-- local copy of n
%2 = alloca i32, align 4
;-- long result
%3 = alloca i32, align 4
;-- int i
%4 = alloca i32, align 4
;-- local n = parameter n
store i32 %0, i32* %2, align 4
;-- result = 1
store i32 1, i32* %3, align 4
;-- i = 1
store i32 1, i32* %4, align 4
br label %loop
loop:
;-- i <= n
%5 = load i32, i32* %4, align 4
%6 = load i32, i32* %2, align 4
%7 = icmp sle i32 %5, %6
br i1 %7, label %loop_body, label %exit
loop_body:
;-- result *= i
%8 = load i32, i32* %4, align 4
%9 = load i32, i32* %3, align 4
%10 = mul nsw i32 %9, %8
store i32 %10, i32* %3, align 4
br label %loop_increment
loop_increment:
;-- ++i
%11 = load i32, i32* %4, align 4
%12 = add nsw i32 %11, 1
store i32 %12, i32* %4, align 4
br label %loop
exit:
;-- return result
%13 = load i32, i32* %3, align 4
ret i32 %13
}
; Function Attrs: noinline nounwind optnone uwtable
define i32 @main() #0 {
;-- factorial(5)
%1 = call i32 @factorial(i32 5)
;-- printf("%ld\n", factorial(5))
%2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @"\01??_C@_04PEDNGLFL@?$CFld?6?$AA@", i32 0, i32 0), i32 %1)
;-- return 0
ret i32 0
}
attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
!llvm.module.flags = !{!0, !1}
!llvm.ident = !{!2}
!0 = !{i32 1, !"wchar_size", i32 2}
!1 = !{i32 7, !"PIC Level", i32 2}
!2 = !{!"clang version 6.0.1 (tags/RELEASE_601/final)"}
- Output:
120
Logo[edit]
Recursive[edit]
to factorial :n
if :n < 2 [output 1]
output :n * factorial :n-1
end
Iterative[edit]
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
LOLCODE[edit]
HAI 1.3
HOW IZ I Faktorial YR Number
BOTH SAEM 1 AN BIGGR OF Number AN 1
O RLY?
YA RLY
FOUND YR 1
NO WAI
FOUND YR PRODUKT OF Number AN I IZ Faktorial YR DIFFRENCE OF Number AN 1 MKAY
OIC
IF U SAY SO
IM IN YR Loop UPPIN YR Index WILE DIFFRINT Index AN 13
VISIBLE Index "! = " I IZ Faktorial YR Index MKAY
IM OUTTA YR Loop
KTHXBYE
- Output:
0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800 11! = 39916800 12! = 479001600
Lua[edit]
Recursive[edit]
function fact(n)
return n > 0 and n * fact(n-1) or 1
end
Tail Recursive[edit]
function fact(n, acc)
acc = acc or 1
if n == 0 then
return acc
end
return fact(n-1, n*acc)
end
Memoization[edit]
The memoization table can be accessed directly (eg. fact[10]
) and will return the memoized value,
or nil
if the value has not been memoized yet.
If called as a function (eg. fact(10)
), the value will be calculated, memoized and returned.
fact = setmetatable({[0] = 1}, {
__call = function(t,n)
if n < 0 then return 0 end
if not t[n] then t[n] = n * t(n-1) end
return t[n]
end
})
M2000 Interpreter[edit]
M2000 Interpreter running in M2000 Environment, a Visual Basic 6.0 application. So we use Decimals, for output.
Normal Print overwrite console screen, and at the last line scroll up on line, feeding a new clear line. Some time needed to print over and we wish to erase the line before doing that. Here we use another aspect of this variant of Print. Any special formatting function $() are kept local, so after the end of statement formatting return to whatever has before.
We want here to change width of column. Normally column width for all columns are the same. For this statement (Print Over) this not hold, we can change column width as print with it. Also we can change justification, and we can choose on column the use of proportional or non proportional text rendering (console use any font as non proportional by default, and if it is proportional font then we can use it as proportional too). Because no new line append to end of this statement, we need to use a normal Print to send new line.
1@ is 1 in Decimal type (27 digits).
Module CheckIt {
Locale 1033 ' ensure #,### print with comma
Function factorial (n){
If n<0 then Error "Factorial Error!"
If n>27 then Error "Overflow"
m=1@:While n>1 {m*=n:n--}:=m
}
Const Proportional=4
Const ProportionalLeftJustification=5
Const NonProportional=0
Const NonProportionalLeftJustification=1
For i=1 to 27
\\ we can print over (erasing line first), without new line at the end
\\ and we can change how numbers apears, and the with of columns
\\ numbers by default have right justification
\\ all $() format have temporary use in this kind of print.
Print Over $(Proportional),$("\f\a\c\t\o\r\i\a\l\(#\)\=",15), i, $(ProportionalLeftJustification), $("#,###",40), factorial(i)
Print \\ new line
Next i
}
Checkit
- Output:
factorial(1)= 1 factorial(2)= 2 factorial(3)= 6 factorial(4)= 24 factorial(5)= 120 factorial(6)= 720 factorial(7)= 5,040 factorial(8)= 40,320 factorial(9)= 362,880 factorial(10)= 3,628,800 factorial(11)= 39,916,800 factorial(12)= 479,001,600 factorial(13)= 6,227,020,800 factorial(14)= 87,178,291,200 factorial(15)= 1,307,674,368,000 factorial(16)= 20,922,789,888,000 factorial(17)= 355,687,428,096,000 factorial(18)= 6,402,373,705,728,000 factorial(19)= 121,645,100,408,832,000 factorial(20)= 2,432,902,008,176,640,000 factorial(21)= 51,090,942,171,709,440,000 factorial(22)= 1,124,000,727,777,607,680,000 factorial(23)= 25,852,016,738,884,976,640,000 factorial(24)= 620,448,401,733,239,439,360,000 factorial(25)= 15,511,210,043,330,985,984,000,000 factorial(26)= 403,291,461,126,605,635,584,000,000 factorial(27)= 10,888,869,450,418,352,160,768,000,000
M4[edit]
define(`factorial',`ifelse(`$1',0,1,`eval($1*factorial(decr($1)))')')dnl
dnl
factorial(5)
- Output:
120
MAD[edit]
NORMAL MODE IS INTEGER
R CALCULATE FACTORIAL OF N
INTERNAL FUNCTION(N)
ENTRY TO FACT.
RES = 1
THROUGH FACMUL, FOR MUL = 2, 1, MUL.G.N
FACMUL RES = RES * MUL
FUNCTION RETURN RES
END OF FUNCTION
R USE THE FUNCTION TO PRINT 0! THROUGH 12!
VECTOR VALUES FMT = $I2,6H ! IS ,I9*$
THROUGH PRNFAC, FOR NUM = 0, 1, NUM.G.12
PRNFAC PRINT FORMAT FMT, NUM, FACT.(NUM)
END OF PROGRAM
- Output:
0! IS 1 1! IS 1 2! IS 2 3! IS 6 4! IS 24 5! IS 120 6! IS 720 7! IS 5040 8! IS 40320 9! IS 362880 10! IS 3628800 11! IS 39916800 12! IS 479001600
MANOOL[edit]
Recursive version, MANOOLish “cascading” notation:
{ let rec
{ Fact = -- compile-time constant binding
{ proc { N } as -- precondition: N.IsI48[] & (N >= 0)
: if N == 0 then 1 else
N * Fact[N - 1]
}
}
in -- use Fact here or just make the whole expression to evaluate to it:
Fact
}
Conventional notation (equivalent to the above up to AST):
{ let rec
{ Fact = -- compile-time constant binding
{ proc { N } as -- precondition: N.IsI48[] & (N >= 0)
{ if N == 0 then 1 else
N * Fact[N - 1]
}
}
}
in -- use Fact here or just make the whole expression to evaluate to it:
Fact
}
Iterative version (in MANOOL, probably more appropriate in this particular case):
{ let
{ Fact = -- compile-time constant binding
{ proc { N } as -- precondition: N.IsI48[] & (N >= 0)
: var { Res = 1 } in -- variable binding
: do Res after -- return result
: while N <> 0 do -- loop while N does not equal to zero
Res = N * Res; N = N - 1
}
}
in -- use Fact here or just make the whole expression to evaluate to it:
Fact
}
Maple[edit]
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
Mathematica / Wolfram Language[edit]
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[edit]
factorial[n_Integer] := n*factorial[n-1]
factorial[0] = 1
Iterative (direct loop)[edit]
factorial[n_Integer] :=
Block[{i, result = 1}, For[i = 1, i <= n, ++i, result *= i]; result]
Iterative (list)[edit]
factorial[n_Integer] := Block[{i}, Times @@ Table[i, {i, n}]]
MATLAB[edit]
Built-in[edit]
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)
Recursive[edit]
function f=fac(n)
if n==0
f=1;
return
else
f=n*fac(n-1);
end
Iterative[edit]
A possible iterative solution:
function b=factorial(a)
b=1;
for i=1:a
b=b*i;
end
Maude[edit]
fmod FACTORIAL is
protecting INT .
op undefined : -> Int .
op _! : Int -> Int .
var n : Int .
eq 0 ! = 1 .
eq n ! = if n < 0 then undefined else n * (sd(n, 1) !) fi .
endfm
red 11 ! .
Maxima[edit]
Built-in[edit]
n!
Recursive[edit]
fact(n) := if n < 2 then 1 else n * fact(n - 1)$
Iterative[edit]
fact2(n) := block([r: 1], for i thru n do r: r * i, r)$
MAXScript[edit]
Iterative[edit]
fn factorial n =
(
if n == 0 then return 1
local fac = 1
for i in 1 to n do
(
fac *= i
)
fac
)
Recursive[edit]
fn factorial_rec n =
(
local fac = 1
if n > 1 then
(
fac = n * factorial_rec (n - 1)
)
fac
)
Mercury[edit]
Recursive (using arbitrary large integers and memoisation)[edit]
:- module factorial.
:- interface.
:- import_module integer.
:- func factorial(integer) = integer.
:- implementation.
:- pragma memo(factorial/1).
factorial(N) =
( N =< integer(0)
-> integer(1)
; factorial(N - integer(1)) * N
).
A small test program:
:- module test_factorial.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module factorial.
:- import_module char, integer, list, string.
main(!IO) :-
command_line_arguments(Args, !IO),
filter(is_all_digits, Args, CleanArgs),
Arg1 = list.det_index0(CleanArgs, 0),
Number = integer.det_from_string(Arg1),
Result = factorial(Number),
Fmt = integer.to_string,
io.format("factorial(%s) = %s\n", [s(Fmt(Number)), s(Fmt(Result))], !IO).
Example output:
factorial(100) = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
min[edit]
((dup 0 ==) 'succ (dup pred) '* linrec) :factorial
MiniScript[edit]
Iterative[edit]
factorial = function(n)
result = 1
for i in range(2,n)
result = result * i
end for
return result
end function
print factorial(10)
Recursive[edit]
factorial = function(n)
if n <= 0 then return 1 else return n * factorial(n-1)
end function
print factorial(10)
- Output:
3628800
MiniZinc[edit]
var int: factorial(int: n) =
let {
array[0..n] of var int: factorial;
constraint forall(a in 0..n)(
factorial[a] == if (a == 0) then
1
else
a*factorial[a-1]
endif
)} in factorial[n];
var int: fac = factorial(6);
solve satisfy;
output [show(fac),"\n"];
MIPS Assembly[edit]
Iterative[edit]
##################################
# Factorial; iterative #
# By Keith Stellyes :) #
# Targets Mars implementation #
# August 24, 2016 #
##################################
# This example reads an integer from user, stores in register a1
# Then, it uses a0 as a multiplier and target, it is set to 1
# Pseudocode:
# a0 = 1
# a1 = read_int_from_user()
# while(a1 > 1)
# {
# a0 = a0*a1
# DECREMENT a1
# }
# print(a0)
.text ### PROGRAM BEGIN ###
### GET INTEGER FROM USER ###
li $v0, 5 #set syscall arg to READ_INTEGER
syscall #make the syscall
move $a1, $v0 #int from READ_INTEGER is returned in $v0, but we need $v0
#this will be used as a counter
### SET $a1 TO INITAL VALUE OF 1 AS MULTIPLIER ###
li $a0,1
### Multiply our multiplier, $a1 by our counter, $a0 then store in $a1 ###
loop: ble $a1,1,exit # If the counter is greater than 1, go back to start
mul $a0,$a0,$a1 #a1 = a1*a0
subi $a1,$a1,1 # Decrement counter
j loop # Go back to start
exit:
### PRINT RESULT ###
li $v0,1 #set syscall arg to PRINT_INTEGER
#NOTE: syscall 1 (PRINT_INTEGER) takes a0 as its argument. Conveniently, that
# is our result.
syscall #make the syscall
#exit
li $v0, 10 #set syscall arg to EXIT
syscall #make the syscall
Recursive[edit]
#reference code
#int factorialRec(int n){
# if(n<2){return 1;}
# else{ return n*factorial(n-1);}
#}
.data
n: .word 5
result: .word
.text
main:
la $t0, n
lw $a0, 0($t0)
jal factorialRec
la $t0, result
sw $v0, 0($t0)
addi $v0, $0, 10
syscall
factorialRec:
addi $sp, $sp, -8 #calling convention
sw $a0, 0($sp)
sw $ra, 4($sp)
addi $t0, $0, 2 #if (n < 2) do return 1
slt $t0, $a0, $t0 #else return n*factorialRec(n-1)
beqz $t0, anotherCall
lw $ra, 4($sp) #recursive anchor
lw $a0, 0($sp)
addi $sp, $sp, 8
addi $v0, $0, 1
jr $ra
anotherCall:
addi $a0, $a0, -1
jal factorialRec
lw $ra, 4($sp)
lw $a0, 0($sp)
addi $sp, $sp, 8
mul $v0, $a0, $v0
jr $ra
Mirah[edit]
def factorial_iterative(n:int)
2.upto(n-1) do |i|
n *= i
end
n
end
puts factorial_iterative 10
МК-61/52[edit]
ВП П0 1 ИП0 * L0 03 С/П
ML/I[edit]
Iterative[edit]
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)
Recursive[edit]
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)
Modula-2[edit]
MODULE Factorial;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,ReadChar;
PROCEDURE Factorial(n : CARDINAL) : CARDINAL;
VAR result : CARDINAL;
BEGIN
result := 1;
WHILE n#0 DO
result := result * n;
DEC(n)
END;
RETURN result
END Factorial;
VAR
buf : ARRAY[0..63] OF CHAR;
n : CARDINAL;
BEGIN
FOR n:=0 TO 10 DO
FormatString("%2c! = %7c\n", buf, n, Factorial(n));
WriteString(buf)
END;
ReadChar
END Factorial.
Modula-3[edit]
Iterative[edit]
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;
Recursive[edit]
PROCEDURE FactRec(n: CARDINAL): CARDINAL =
VAR result := 1;
BEGIN
IF n > 1 THEN
result := n * FactRec(n - 1);
END;
RETURN result;
END FactRec;
Mouse[edit]
Mouse 79[edit]
"PRIME NUMBERS!" N1 = (NN. 1 + = #P,N.; )
$P F1 = N1 =
( FF . 1 + = %AF. - ^ %AF./F. * %A - 1 + [N0 = 0 ^ ] )
N. [ %A! "!" ] @
$$
MUMPS[edit]
Iterative[edit]
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
Recursive[edit]
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
MyrtleScript[edit]
func factorial args: int a : returns: int {
int factorial = a
repeat int i = (a - 1) : i == 0 : i-- {
factorial *= i
}
return factorial
}
Nanoquery[edit]
def factorial(n)
result = 1
for i in range(1, n)
result = result * i
end
return result
end
Neko[edit]
var factorial = function(number) {
var i = 1;
var result = 1;
while(i <= number) {
result *= i;
i += 1;
}
return result;
};
$print(factorial(10));
Nemerle[edit]
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
}
}
NetRexx[edit]
/* 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)
newLISP[edit]
> (define (factorial n) (exp (gammaln (+ n 1))))
(lambda (n) (exp (gammaln (+ n 1))))
> (factorial 4)
24
Nial[edit]
(from Nial help file)
fact is recur [ 0 =, 1 first, pass, product, -1 +]
Using it
|fact 4
=24
Nickle[edit]
Factorial is a built-in operator in Nickle. To more correctly satisfy the task, it is wrapped in a function here, but does not need to be. Inputs of 1 or below, return 1.
int fact(int n) { return n!; }
- Output:
prompt$ nickle > load "fact.5c" > fact(66) 544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000 > fact(-5) 1 > -5! -120 > fact(1.1) Unhandled exception invalid_argument ("Incompatible argument", 0, 1.1) <stdin>:11: fact ((11/10));
Note the precedence of factorial before negation, (-5)! is 1 in Nickle, -5! is the negation of 5!, -120.
Also note how the input of 1.1 is internally managed as 11/10 in the error message.
Nim[edit]
Library[edit]
import math
let i:int = fac(x)
Recursive[edit]
proc factorial(x): int =
if x > 0: x * factorial(x - 1)
else: 1
Iterative[edit]
proc factorial(x: int): int =
result = 1
for i in 2..x:
result *= i
Niue[edit]
Recursive[edit]
[ dup 1 > [ dup 1 - factorial * ] when ] 'factorial ;
( test )
4 factorial . ( => 24 )
10 factorial . ( => 3628800 )
Nyquist[edit]
Lisp Syntax[edit]
Iterative:
(defun factorial (n)
(do ((x n (* x n)))
((= n 1) x)
(setq n (1- n))))
Recursive:
(defun factorial (n)
(if (= n 1)
1
(* n (factorial (1- n)))))
Oberon[edit]
MODULE Factorial;
IMPORT
Out;
VAR
i: INTEGER;
PROCEDURE Iterative(n: LONGINT): LONGINT;
VAR
i, r: LONGINT;
BEGIN
ASSERT(n >= 0);
r := 1;
FOR i := n TO 2 BY -1 DO
r := r * i
END;
RETURN r
END Iterative;
PROCEDURE Recursive(n: LONGINT): LONGINT;
VAR
r: LONGINT;
BEGIN
ASSERT(n >= 0);
r := 1;
IF n > 1 THEN
r := n * Recursive(n - 1)
END;
RETURN r
END Recursive;
BEGIN
FOR i := 0 TO 9 DO
Out.String("Iterative ");Out.Int(i,0);Out.String('! =');Out.Int(Iterative(i),0);Out.Ln;
END;
Out.Ln;
FOR i := 0 TO 9 DO
Out.String("Recursive ");Out.Int(i,0);Out.String('! =');Out.Int(Recursive(i),0);Out.Ln;
END
END Factorial.
- Output:
Iterative 0! =1 Iterative 1! =1 Iterative 2! =2 Iterative 3! =6 Iterative 4! =24 Iterative 5! =120 Iterative 6! =720 Iterative 7! =5040 Iterative 8! =40320 Iterative 9! =362880 Recursive 0! =1 Recursive 1! =1 Recursive 2! =2 Recursive 3! =6 Recursive 4! =24 Recursive 5! =120 Recursive 6! =720 Recursive 7! =5040 Recursive 8! =40320 Recursive 9! =362880
Objeck[edit]
Iterative[edit]
bundle Default {
class Fact {
function : Main(args : String[]) ~ Nil {
5->Factorial()->PrintLine();
}
}
}
OCaml[edit]
Recursive[edit]
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
Iterative[edit]
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 *