74
\$\begingroup\$

Create the shortest program or function that finds the factorial of a non-negative integer.

The factorial, represented with ! is defined as such

$$n!:=\begin{cases}1 & n=0\\n\cdot(n-1)!&n>0\end{cases}$$

In plain English the factorial of 0 is 1 and the factorial of n, where n is larger than 0 is n times the factorial of one less than n.

Your code should perform input and output using a standard methods.

Requirements:

  • Does not use any built-in libraries that can calculate the factorial (this includes any form of eval)
  • Can calculate factorials for numbers up to 125
  • Can calculate the factorial for the number 0 (equal to 1)
  • Completes in under a minute for numbers up to 125

The shortest submission wins, in the case of a tie the answer with the most votes at the time wins.

\$\endgroup\$
  • 10
    \$\begingroup\$ How many of the given answers can actually compute up to 125! without integer overflow? Wasn't that one of the requirements? Are results as exponential approximations acceptable (ie 125 ! = 1.88267718 × 10^209)? \$\endgroup\$ – Ami Feb 6 '11 at 22:43
  • 6
    \$\begingroup\$ @SHiNKiROU, even golfscript can manage 125! less than 1/10th of a second and it's and interpreted interpreted language! \$\endgroup\$ – gnibbler Feb 8 '11 at 3:21
  • 5
    \$\begingroup\$ @ugoren the two-character solution to the other question uses a built-in factorial function. That's not allowed in this version of the challenge. \$\endgroup\$ – Michael Stern Jan 7 '14 at 3:18
  • 4
    \$\begingroup\$ Completes in under a minute seems a very hardware-dependent requirement. Completes in under a minute on what hardware? \$\endgroup\$ – sergiol Aug 24 '17 at 18:05
  • 4
    \$\begingroup\$ @sergiol Incredibly that hasn't been an issue in the last 2 years, I suspect most languages can get it done in under a minute. \$\endgroup\$ – Kevin Brown Aug 24 '17 at 21:20

179 Answers 179

3
\$\begingroup\$

Python, 35 bytes

def f(n):return n and n*f(n-1) or 1

or

def f(n):return n*f(n-1) if n else 1
\$\endgroup\$
  • 3
    \$\begingroup\$ I posted a shorter similar solution. No need to repeat it you don't have an extra insight. \$\endgroup\$ – Alexandru Feb 7 '11 at 12:33
  • \$\begingroup\$ @Alexandru if he wrote this without referencing your answer, I don't see why he shouldn't be allowed to post it just because it's longer. All Runners in a race get to post their score regardless of being first or last. \$\endgroup\$ – akozi Feb 20 at 14:49
3
\$\begingroup\$

Jelly, 2 bytes

RP

Try it online!

Alternatively, a builtin answer is one byte:

!

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Befunge-93 24 22 20 bytes

Edit: Found a better way of generating the range of values

1&0>-#1:__\#0:#*_$.@

Try it online!

How it works:

1& Initialises the stack with 1 (for the special case of 0!) and the inputted factorial
  0>-#1:_ Adds the current factorial level-1 to the stack until it reaches 0
         _\# :# _ Pops another 0 and swaps the two top values of the stack. Duplicate the top value, and check whether it is 0.
         _ #0 #*_ If not, multiply the top two values of the stack and add an extra 0 so the underscore will point right. Repeat the above section.
                 $.@ If so, pop the extra 0, print the value and exit the program
\$\endgroup\$
2
\$\begingroup\$

PowerShell, 34

{($p=1)..$_-ge1|%{$p*=$_};$p}

Creates a list of numbers from one to the argument, selects those greater than or equal to one and multiplies those. For 0 the list 1, 0 will be created where then only 1 remains, yielding the correct answer.

To test:

> &{($p=1).."$args"-ge1|%{$p*=$_};$p} 125
1,88267717688893E+209

It's just a scriptblock; i.e. a function without a name.

\$\endgroup\$
2
\$\begingroup\$

C#: 37

int f(int n){return n>0?n*f(n-1):1;}

\$\endgroup\$
  • 2
    \$\begingroup\$ This function returns 1 always. \$\endgroup\$ – Alexandru Jul 4 '11 at 11:15
  • \$\begingroup\$ whoopsies, you're right. \$\endgroup\$ – Origamiguy Jul 10 '11 at 12:38
  • 3
    \$\begingroup\$ int is way too small to hold 125!, which is something like 1.88e+209. \$\endgroup\$ – Justin Morgan Jul 12 '11 at 19:05
2
\$\begingroup\$

Pico, 23

f(x):if(x=0,1,x*f(x-1))

but Pico max out at 12:

>f(12)
479001600
\$\endgroup\$
  • \$\begingroup\$ Does it work with 125? \$\endgroup\$ – user unknown Jan 11 '12 at 2:45
  • 1
    \$\begingroup\$ @userunknown No, it doesn't as Pico's number type has the same limits as C's int. and fixing it so that it could would require implementing big integer multiplication and that would require at least 500-4000 characters. \$\endgroup\$ – Dan D. Jan 11 '12 at 9:55
2
\$\begingroup\$

Golfscript, 10 chars:

~,{)}%{*}*
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 17

f = Times@@Range@#&

works more or less instantaneously for f[125].

\$\endgroup\$
  • \$\begingroup\$ 1##& is 1 byte shorter than Times \$\endgroup\$ – LLlAMnYP Jan 19 '17 at 10:01
2
\$\begingroup\$

Ruby, 35 characters,

def f(x);p 1.upto(x).inject(:*);end

Test:

f(5)

=> 120

\$\endgroup\$
2
\$\begingroup\$

Julia - 14 characters (19 with non-arbitrary-precision input)

f(n)=prod(1:n)

If you want it to work all the way up to n=125, precision becomes an issue. If requiring the input value to be "big" to match the output is unacceptable, then an extra 5 characters can be used to overcome the problem:

g(n)=prod(1:big(n))

big(n) converts n to an arbitrary precision integer, and the code remains in arbitrary precision from there. The alternative is, with the 14 character code above, making the input arbitrary precision - for instance, calling f(big(125)).

\$\endgroup\$
  • \$\begingroup\$ And it works fast enough even for ridiculously high n. For n=100,000 my old i5-2410 laptop needs only 10.3 seconds. Displaying the 456,574 digits of the result is kind of a problem, though ;) At first I didn’t see that there already was a Julia solution. I would have almost made a double post. \$\endgroup\$ – M L Jun 28 '15 at 7:44
2
\$\begingroup\$

Bash+coreutils, 21 bytes

seq $1|paste -sd\*|bc
\$\endgroup\$
2
\$\begingroup\$

R, 22 (9 w/o function def; 35 w/ recursion)

Simply

f=function(n)prod(1:n)

Or, without defining a function:

prod(1:n)

Or, recursive:

f=function(n)if(n<2)1 else n*f(n-1)
\$\endgroup\$
  • \$\begingroup\$ Only the last will work entirely (i.e. give 1 for n=0). A shorter solution would be : ifelse((n=scan())>0,prod(1:n),1), with 32 bytes. \$\endgroup\$ – Frédéric Aug 26 '16 at 16:11
  • \$\begingroup\$ @Frédéric or better yet "if"((n=scan())>0,prod(1:n),1) for 30 bytes. \$\endgroup\$ – Giuseppe Aug 24 '17 at 17:34
2
\$\begingroup\$

Haskell, 20

Gee, I sure hope folds don't count as built in functions...

f n=foldl(*)1[1..n]
\$\endgroup\$
  • \$\begingroup\$ product is probably shorter \$\endgroup\$ – Mega Man Aug 5 at 18:15
2
\$\begingroup\$

Swift: 43

var f:Double->Double;f={$0<1 ?0:f($0-1)*$0}

Swift is definitely not made for conciseness, but I though let's give it a try anyways. This solution is obviously recursive.

There's also the more native Swift way to do it which is a bit longer (57 characters):

let f={stride(from:1,through:$0,by:1.0).reduce(1){$0*$1}}

If it would be allowed to add an additional rule for very typey languages:

  • You may add functions with the same behaviour as functions in the standard library for the purpose of shorter names

Then I would declare these two:

func ...(lhs: Double, rhs: Double) -> StrideThrough<Double> {
    return stride(from: lhs, through: rhs, by: 1)
}

extension SequenceType {
    func r<T>(initial: T, @noescape _ combine: (T, Self.Generator.Element) -> T) -> T {
        return reduce(initial, combine: combine)
    }
}

which redeclares stride(from: a, through: b, to:1.0) to a...b which I even think should be in the standard library, and reduce(a, combine: f) becomes r(a, f). This would one enable to do this:

let f={(1...$0).r(1,*)}

which would be 23 characters.

I'm even thinking about creating a Code Golf Swift extension, which just redeclares all the standard methods to something more concise.

Any of those can be called like:

f(0) // 0
f(120) // 6.689502913449124e+198
f(170) // 7.257415615307994e+306

All of them can go up to 170, where the result will be Double.infinity when above.

The times are as follows (for input 170):

recursive (43 chars): 0.00000101 s
native (rule-bend)  : 0.00000027 s
native              : 0.00000027 s
\$\endgroup\$
  • \$\begingroup\$ Why is it var f:Double->Double? Isn't that declaring the type twice? var seems to declare it to be of "variable" type, whereas Double->Double seems to declare it to be a function that accepts a double and returns a double. If this is not the case, can I get an explanation of the type signature for someone who doesn't know swift? \$\endgroup\$ – Cyoce Feb 5 '16 at 6:21
  • \$\begingroup\$ @Cyoce If I was using let instead, the compiler would complain because I'm using the function itself in its definition without it being declared beforehand. By using var we can trick the compiler into thinking that f is declared already. \$\endgroup\$ – Kametrixom Feb 5 '16 at 13:30
  • \$\begingroup\$ ok, thanks for the clarification \$\endgroup\$ – Cyoce Feb 5 '16 at 15:56
2
\$\begingroup\$

JavaScript ES6 21 chars

Note: I'm just extending Casey Chu's answer using ES6 with minor change

f=(n)=>n<2?1:n*f(n-1)

fiddle: Factorial

1) Does not use any built-in functions

2) Calculates factorial up to 170

3) Calculates factorial for 0 too

4) Execution time is less than a millisecond

Note: It will work only in browsers that supports ES6. FF(22+) and Chrome(45+) supports arrow functions as per MDN at the time of writing this answer.

\$\endgroup\$
  • \$\begingroup\$ You don't need parens around the argument. f=n=>… is fine. \$\endgroup\$ – Cyoce Jan 27 '16 at 3:34
2
\$\begingroup\$

Simplex v.0.5, 12 bytes

(The Docs page may be outdated; mainly, the * also increments the pointer and the J being the max of two elements.)

h*M{*LTRpM}]

This defines a macro that performs the factorial function on the current byte. It maintains the structure of the strip, but inserts an extra 0 at the next byte. You can delete this by adding another command p before the function ends.

This one works for inputs on a strip whose sole member is the input. I.e., a strip which looks like [N,/,/,...] (/ is the empty or null bit.) It clocks in at…

11 Bytes!!

This beats the GolfScript entry, FYI.

h{*M}pwT1J]

This is what it does:

h{*M}pwT1J]
h         ] ~~ define new macro
 {  }       ~~ repeat inside until zero met
  *         ~~ copy the current byte and increment pointer
   M        ~~ decrement byte
     p      ~~ remove trailing zero
      wT    ~~ spreads T (multiplication) across strip backwards; sets pointer to after the result
        1J  ~~ Takes the maximum of 1 and the current byte

Here the non-destructive version being used in an example code:

h*M{*LTRpM}p]ih0o

This defines the macro, asks for numeric input (i), calls the first macro (h0) and outputs the byte as a number (o).

Here is the pseudo-code I used:

Function factorial(N)
    A = N - 1
    While A > 1
        N = A * N
        A = A - 1
    End While
    Return N
End Function

This is the expanded explanation.

h    ~~ open macro, implicit [
 *   ~~ A=N [N,A]
 M   ~~ A=N-1 [N,A-1]
 {   ~~ Loop until current byte is zero
  *  ~~ [N,A-1,A-1]
  LT ~~ [N*(A-1),0,A-1]
  Rp ~~ [N*(A-1),A-1]
  M  ~~ [N*(A-1),A-2]
 }
 p   ~~ [N!]
]    ~~ close macro
\$\endgroup\$
2
\$\begingroup\$

Burlesque, 4 bytes

Burlesque has a built-in ?! to do that, but since that is forbidden by the rules we can just use ropd (runs in less than a fraction of a second):

blsq ) 125ropd
188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000
blsq ) 5ropd
120
blsq ) 125?!
188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000

Basically factorial is just the product of a list [1..N] and ro creates [1..N] and pd is the product of a list. Simple as that.

\$\endgroup\$
  • \$\begingroup\$ Does this account for 0!=1? \$\endgroup\$ – AdmBorkBork Nov 23 '15 at 20:16
  • 1
    \$\begingroup\$ Yes, because pd (Product) is defined to be 1 for empty lists. \$\endgroup\$ – mroman Nov 24 '15 at 9:37
2
\$\begingroup\$

Python - 33

f=lambda n:n*(n and f(n-1))+(n<1)
\$\endgroup\$
  • \$\begingroup\$ We already have this shorter answer using the same approach. \$\endgroup\$ – lirtosiast Jan 24 '16 at 23:25
2
\$\begingroup\$

JacobFck, noncompeting

43 bytes. This answer is noncompeting, because the language was invented after the challenge was posted.

Might be a bit late but this is too good to pass up.

<^0|=_s~$t$c:m^1^c|=_e-$c^t*$t_m:e^t>!:s^1>

Here is the commented and expanded: here

\$\endgroup\$
2
\$\begingroup\$

Python, 29 bytes

f=lambda x:x and x*f(x-1)or 1
\$\endgroup\$
2
\$\begingroup\$

JavaScript, 52 bytes

function f(m){n=1;for(i=1;i<=m;i++){n*=i;}return n;}
\$\endgroup\$
  • \$\begingroup\$ You can shorten that too function f(m){for(n=i=1;i<=m;)n*=i++;return n}. It's 6 character in less. \$\endgroup\$ – HoLyVieR Feb 7 '11 at 3:57
2
\$\begingroup\$

K, 9 bytes

f:*/1f+!:

k) f 125 
1.882677e+209

Computes 125! in under a millisecond; 15ms for 10k iterations

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 4 bytes (non-competing)

Since the language postdates the challenge, this is non-competing

Code:

L0KP

Explanation:

L     # Create the list [1, ..., input]
 0K   # Remove all occurencies of zero
   P  # Calculate the product

I have no idea why this works for 0, but it does.

\$\endgroup\$
  • \$\begingroup\$ Why does the list in the range [1,N] for N=0 becomes [0].. I did know taking the product of [] becomes 1. Both seem to be the ideal situation for the 0 edge-case here.. xD \$\endgroup\$ – Kevin Cruijssen Aug 9 '18 at 14:04
  • 1
    \$\begingroup\$ ݦP is one byte shorter. \$\endgroup\$ – Grimy May 29 at 13:28
2
\$\begingroup\$

Detour (non-competing), 5 bytes

?1RP.

Try it online!

?1 means "if n is 0, set n to 1"
RP means product [1..n], . is output

Terminates in 6ms for 170 (the highest number whose factorial can be represented in JS) on my craptop 4-year-old macbook air with 2GB RAM.


Here's a 100% symbolic method:

Detour, 10 bytes

[{<]?1}&*.

Try it online!


Old recursive way:

Detour, 17 13 11 bytes

<Q0\
.$;p>P

Try it online!


This is non-competing, as I just finished the language today.

There's no good way to explain it, the website will give a visualization of the data flow at runtime.

It's a shame I have to handle 0!=1, or this could be a one-liner.

Another 11-byte solution (faster):


Detour, 11 bytes

?1[$Q<]x
P.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Sage, 19 bytes

For some reason, Guido hates prod(). But, Sage supports it:

f=lambda n:prod(1..n)

edit: just had a statement previously, not a function

\$\endgroup\$
2
\$\begingroup\$

Scheme - 33 characters

Improved answer using an unnamed procedure and the λ symbol.

(λ(n)(if(= 0 n)1(* n(!(- n 1)))))

Old 40 character answer below

(define(! n)(if(= 0 n)1(* n(!(- n 1)))))

The white-space requirement is almost as much of a problem as the brackets for bloating things in scheme.

Testing:

> ((λ(n) (if(= 0 n)1(* n(!(- n 1))))) 0)
1
> ((λ(n) (if(= 0 n)1(* n(!(- n 1))))) 125)
188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000
\$\endgroup\$
  • \$\begingroup\$ what about removing the space between define and (! n) \$\endgroup\$ – jkabrg Oct 13 '15 at 21:49
  • \$\begingroup\$ Thanks NaN - can actually remove a lot of spaces so 47 down to 40. \$\endgroup\$ – Penguino Oct 13 '15 at 22:12
  • \$\begingroup\$ Doesn't work for me (the lambda one) - ! is undefined (running in DrRacket 6.4) \$\endgroup\$ – kronicmage Jun 9 '16 at 13:30
2
\$\begingroup\$

Pyth, 8 bytes

It's a shame that, 5 years after the challenge has been posted, there is no pyth answer. So I'm doing it now, even if it's ridiculous :). BTW, this is non-competiting, since the language is newer than the challenge...

Lu*GHSb1

You call it with yx, where x is a number. Test it here !

Explanation

Lu*GHSb1
L          Defines a lambda 'y' with argument 'b'
     Sb    Create a range from one to 'b' (function argument)  
  *GH      Lambda function that takes two arguments and multiply them
 u     1   Reduce the range with the above lambda.
\$\endgroup\$
  • \$\begingroup\$ L*F+1Sb is a bit shorter. \$\endgroup\$ – FryAmTheEggman Apr 9 '16 at 19:08
  • \$\begingroup\$ @FryAmTheEggman What kind of sorcery is this ? \$\endgroup\$ – FliiFe Apr 9 '16 at 19:38
  • \$\begingroup\$ F is fold, basically a reduce over the list, it expands pretty much into what you did, but without the start at 1 thing. So I manually add a 1 to the list Sb creates, which of course won't change the product. \$\endgroup\$ – FryAmTheEggman Apr 9 '16 at 19:40
  • \$\begingroup\$ @FryAmTheEggman I still have a lot to learn... \$\endgroup\$ – FliiFe Apr 9 '16 at 20:20
2
\$\begingroup\$

Common Lisp, 38 bytes

Disclaimer: I'm not responsible for any traumatic effect caused by the extreme density of parentheses. It's the language specification's fault.

(defun a(b)(if(< b 2)1(*(a(- b 1))b)))

Ungolfed & explained:

(defun a (b)                               ;Define a function called "a". It has one parameter called "b"
            (if (< b 2)                    ;If b is a number that is smaller than 2 (0 and 1 satisfy this)
                       1                   ;Return 1
                        (* (a (- b 1)) b)));Otherwise, return a(b-1) multiplied by b
\$\endgroup\$
  • \$\begingroup\$ Hi, your solution does not handle the input value '0'; you should modify the code as follows: (defun a(b)(if(= b 0)1(*(a(- b 1))b))). \$\endgroup\$ – PieCot Jun 6 '16 at 21:47
  • \$\begingroup\$ You can save a byte by using (1- b) instead of (- b 1) \$\endgroup\$ – djeis Apr 12 '17 at 16:40
2
\$\begingroup\$

PHP, 39 bytes

<?=array_product(range(1,$argv[1]))?:1;

breakdown

<?=                          // 4. print result
    array_product(           // 2. get product of the elements - special: 0
        range(1,$argv[1])    // 1. build array from 1 to N - special: [1,0]
    )
    ?:1                      // 3. special: if falsy, return 1
;
\$\endgroup\$
  • \$\begingroup\$ for($p=1;$i++<$argn;)$p*=$i;echo$p; is shorter and <?=array_product($argn?range(1,$argn):[]); is a more interesting way \$\endgroup\$ – Jörg Hülsermann Jul 9 '17 at 0:41
2
\$\begingroup\$

CJAM 9

I'm pretty sure this mmets all requirements. It ran on the online compiler for 125 is far less than a second.

1ri,{)*}%

It works as follows:

1         puts 1 on stack
ri        accepts input as integer
,         creates list of all non negative integers less than input
{         start block
          increments integer by 1
          multiplies current product by integer, current product starts with 1
}         repeat block for each element in list
\$\endgroup\$
  • \$\begingroup\$ ri,1f+:* is even shorter \$\endgroup\$ – kaine Nov 4 '14 at 22:01
  • \$\begingroup\$ Can you remove the -? It's throwing off the leaderboard snippet, thinks you're at negative 9 bytes. \$\endgroup\$ – Pavel Jan 19 '17 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.