90
\$\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\$
12
  • 15
    \$\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, 2011 at 22:43
  • 7
    \$\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, 2011 at 3:21
  • 8
    \$\begingroup\$ Completes in under a minute seems a very hardware-dependent requirement. Completes in under a minute on what hardware? \$\endgroup\$
    – sergiol
    Aug 24, 2017 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\$ Aug 24, 2017 at 21:20
  • 5
    \$\begingroup\$ Why aren't built-ins allowed? You haven't specified what built-ins are, and if you said that it was up to a "reasonable person" to decide (which is completely subjective, but ignoring that), you still say that any form of eval is a built-in for the factorial, even though it evaluates code, not the factorial of a given number. \$\endgroup\$
    – MilkyWay90
    May 7, 2019 at 2:02

212 Answers 212

1 2
3
4 5
8
2
\$\begingroup\$

JavaScript, 52 bytes

function f(m){n=1;for(i=1;i<=m;i++){n*=i;}return n;}
\$\endgroup\$
1
  • \$\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, 2011 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
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\$
4
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\$
3
  • \$\begingroup\$ what about removing the space between define and (! n) \$\endgroup\$
    – wlad
    Oct 13, 2015 at 21:49
  • \$\begingroup\$ Thanks NaN - can actually remove a lot of spaces so 47 down to 40. \$\endgroup\$
    – Penguino
    Oct 13, 2015 at 22:12
  • \$\begingroup\$ Doesn't work for me (the lambda one) - ! is undefined (running in DrRacket 6.4) \$\endgroup\$
    – kronicmage
    Jun 9, 2016 at 13:30
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\$
2
  • \$\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, 2016 at 21:47
  • \$\begingroup\$ You can save a byte by using (1- b) instead of (- b 1) \$\endgroup\$
    – djeis
    Apr 12, 2017 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\$
1
  • \$\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\$ Jul 9, 2017 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\$
2
  • \$\begingroup\$ ri,1f+:* is even shorter \$\endgroup\$
    – kaine
    Nov 4, 2014 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, 2017 at 2:10
2
\$\begingroup\$

Ruby, 22 bytes

n.downto(1).inject(:*)
\$\endgroup\$
3
  • \$\begingroup\$ Unfortunately, this doesn't work for 0, so you probably have to add a ternary operator. \$\endgroup\$ Nov 29, 2014 at 20:05
  • \$\begingroup\$ n.downto(1).inject(1,:*) \$\endgroup\$
    – histocrat
    Jul 24, 2015 at 17:12
  • \$\begingroup\$ Or in fact (1..n).inject 1,:* seems to work fine. \$\endgroup\$
    – histocrat
    Jul 24, 2015 at 17:14
2
\$\begingroup\$

><>, 17 16 bytes

1v;n
$<*}-1.!?::

-1 byte thanks to Jo King.

Since the question asks for a function as opposed to a full program, I allowed myself to accept the input from the stack without counting an additional 3 bytes for using the -v option.

This manages to be shorter than the other ><> answer because it jumps to the end-of-iteration code without having to hardcode the jump destination address : the current iteration counter (duplicated) is used as an address.
The iteration stops when the counter is 0, and jumping to (0, 0) while the direction pointer points to the right will execute the n; code that is otherwise unreachable, displaying the result and stopping the execution.

It handles 0! correctly and executes in 10*(n+1) ticks for n > 0 or 9 ticks for n = 0.

You can try it online.

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

Python, 30 bytes

f=lambda n:n*f(n-1)if n else 1

Saves some characters by using lambda syntax and a ternary if-else.

\$\endgroup\$
4
  • \$\begingroup\$ This is very similar to the Python answer on the first page, and doesn't really add anything. \$\endgroup\$
    – lirtosiast
    Jun 22, 2015 at 14:51
  • \$\begingroup\$ Firstly, there are many Python answers. Secondly, which answers are on which page is dependent on how you sort the answers. Thirdly, even if my answer doesn't add anything super cool or unique, it's still different enough for me to post it as my own. Because it IS my own. I created it without reading the other answers first. \$\endgroup\$
    – mbomb007
    Jun 22, 2015 at 18:32
  • 1
    \$\begingroup\$ There are five Python answers; two of them are exactly yours except that the authors used and/or rather than ternary or forgot to use lambda. If I had this solution, I would post it as an improvement comment on those answers due to similarity, or not post if there is no improvement. \$\endgroup\$
    – lirtosiast
    Jun 22, 2015 at 18:46
  • 3
    \$\begingroup\$ Using and/or instead of ternary is pretty different in Python for this challenge. Your feedback is appreciated, but I'm not removing my answer. This answer was posted 5 months ago and was fine. \$\endgroup\$
    – mbomb007
    Jun 22, 2015 at 18:51
2
\$\begingroup\$

Brain-Flak, 52 bytes

Came up with the solution independently, thanks JoKing for telling me that it's possible to get 52 bytes.

<>(())<>{(({})<({<>({})<><({}[()])>}{})<>{}>[()])}<>

Try it online!


Ungolfed:

<>(())<>		# push 1 on the other stack
{			# while x:
 (
  ({})			# copy x to the 3rd stack
  <(			# push the
   {			# running total of
    <>({})<>		# top of the other stack
    <({}[()])>		# (while decrementing x)
   }
   {}			# pop redundant 0
  )<>{}>
  [()]
 )			# push x-1
}
<>

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ It's interesting that you don't always end up on the same stack at the end. Here's my own 52 byte answer if anyone else is interested. \$\endgroup\$
    – Jo King
    May 22, 2018 at 6:26
2
\$\begingroup\$

Flobnar, 19 bytes

|\@<:
1&::
<>-*
  1

Try it online!

An interesting sibling to Befunge. This uses the -d flag to enable decimal input.

Explanation:

This is basically equivalent to the recursive function:

def f(x):
  if x == 0:
    return 1
  else:
    return x*f(x-1)

The program starts from the @, and evaluates to its left. The \ evaluates underneath itself and stores that in the call stack. Underneath it is the &, which gives decimal input. If EOF has been reached, it evaluates underneath itself. Underneath, the > pushes the pointer right and returns the top value of the call stack minus 1.

That's this section:

 \@
 &:
 >-
  1

The \ basically counts down from the input and stores the latest version in the call stack.

After that, it hits the |, which evaluates further along, and returns either the value above it if the evaluated value is non-zero, else the value below it. The : returns the top of the call stack, so if it is zero, the | goes down and returns 1, else it goes up and wraps around the field. It hits the < which wraps it around again, and then multiplies the top of the call stack by the next iteration of the function.

|  <:
1  :
<  *
\$\endgroup\$
1
  • \$\begingroup\$ You beat me to this answer and probably outgolfed any attempt I might have made! Looks like the -d flag is misdocumented as -e - that should be fixed soon. \$\endgroup\$ Aug 7, 2018 at 20:41
2
\$\begingroup\$

Julia 1.0, 12 bytes

n->prod(1:n)

Try it online!

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

Keg, 16 bytes

(:|:1-)_(!1-|*).

This takes a top-of-stack item and returns [0..top]. Then, it discards the 0. After that, it multiplies everything in the stack, returning the factorial. (This is indeed too long.)

\$\endgroup\$
3
  • \$\begingroup\$ Nicely golfed, I gave my own shot at this but was only able to get 18 bytes, +1 \$\endgroup\$
    – EdgyNerd
    Aug 10, 2019 at 11:38
  • \$\begingroup\$ I'm getting an error running that code on TIO. \$\endgroup\$ Sep 25, 2019 at 20:38
  • \$\begingroup\$ Run this in an old version. (Works for most of my Keg answers) \$\endgroup\$
    – user85052
    Sep 25, 2019 at 22:42
2
\$\begingroup\$

Python 3, 30 Bytes

f=lambda n:n*f(n-1)if n else 1

125! took less than 1 second to do on IDLE and TIO.

How it works: the function f returns n*f(n-1) if n is not 0 and it returns 1 otherwise, the definition of a factorial.

Try it online!

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

JavaScript (Node.js), 17 bytes

Recursion. Usage of arrow function declaration and OR operator that checks whether x is 0 (if not, continue multiplying).

f=x=>!x||x*f(x-1)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ How would the method posted on sci.comp.stackexchange.com performs compared to the above methods. The method basically cut the number of multiplications by half. See link below. I cannot code but I am curious to know how the method performs. scicomp.stackexchange.com/questions/42510/… \$\endgroup\$
    – user25406
    Mar 1 at 19:46
2
\$\begingroup\$

Hexagony, 25 bytes

?{)"(&=}<!{\.@*$><>}=/\._

Formatted:

   ? { ) "
  ( & = } <
 ! { \ . @ *
$ > < > } = /
 \ . _ . . .
  . . . . .
   . . . .

Try it online! or Try it online differently!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 17 bytes \$\endgroup\$
    – Jo King
    Apr 24, 2021 at 0:41
  • \$\begingroup\$ @JoKing you should post that as a separate answer considering it's more than just adjusting mine. \$\endgroup\$
    – Underslash
    Apr 24, 2021 at 0:53
2
\$\begingroup\$

Ruby - 20 chars

f=->n{0**n|n*f[n-1]}

Test

irb(main):009:0> f=->n{0**n|n*f[n-1]}
=> #<Proc:0x25a6d48@(irb):9 (lambda)>
irb(main):010:0> f[125]
=> 188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I'm pretty sure the recursive call needs to be g[n-1] \$\endgroup\$
    – Razetime
    Jul 14, 2021 at 16:46
  • \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ Jul 14, 2021 at 16:53
  • \$\begingroup\$ @Razetime thx ))) \$\endgroup\$
    – AgentIvan
    Nov 4, 2021 at 18:54
2
\$\begingroup\$

Rust, 48 bytes

fn f(n:f64)->f64{if n==0.0{1.0}else{n*f(n-1.0)}}

Try it online!

Standard recursive solution. Unfortunately the recursion means I can't save bytes by using a closure.

Note that this solution, along with almost every non python-based answer here, uses 64-bit floats, meaning large answers such as 125! are calculated with some precision loss. This is more noticeable in rust than in, for example, JS, because JS prints the number in scientific notation, while rust prints the whole number.

Rust with num, 61/85/102 bytes

fn f(n:i64)->BigInt{if n==0{1.into()}else{(n*f(n-1)).into()}}

Try it in Rust Playground

This answer is longer, but uses the BigInt type provided by the num crate and as a result calculates with maximum precision.

+24 bytes for a total of 85 if you want to count use num::bigint::BigInt;
or
+41 bytes for a total of 102 if you want to count extern crate num;use num::bigint::BigInt;

Rust Playground can be a little unpredictable, so if you get a timeout when trying to run this, keep trying. It should work eventually.

\$\endgroup\$
1
  • \$\begingroup\$ -11 bytes for the shorter f64 solution (if making it non-recursive is ok). \$\endgroup\$
    – JSorngard
    Mar 7 at 12:13
2
\$\begingroup\$

Husk, 2 bytes

With Product (2 bytes)

Πḣ
    implicit parameter ⁰ (last argument)
 ḣ  get the range from 1 to n
Πḣ  get the product of that list

Try it online!

With Fold (4 bytes)

F*1ḣ
       implicit parameter ⁰ (last argument)
   ḣ   get the range from 1 to n
F*1ḣ   fold left on multiplication starting with 1

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Why is this non competing? \$\endgroup\$
    – Mayube
    Nov 5, 2021 at 14:07
  • \$\begingroup\$ i thought it was non competing if the language was created after the problem but i can change it \$\endgroup\$
    – Hydrazer
    Nov 5, 2021 at 21:25
  • 2
    \$\begingroup\$ That used to be the case, but we decided to revert that rule \$\endgroup\$
    – Mayube
    Nov 5, 2021 at 21:32
  • \$\begingroup\$ ah good to know \$\endgroup\$
    – Hydrazer
    Nov 6, 2021 at 1:57
2
\$\begingroup\$

Bash, 14

seq -s\* $1|bc
  • 7 bytes saved thanks to @JuanIgnacioDíaz

Try it online!

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

JavaScript, arbitrary precision, 18 bytes

f=x=>x?x*f(--x):1n

This uses the bignum type for arbitrarily long integers.

f(125n) // 18826771768889260997437677024916008575954036487149…375565007131770880000000000000000000000000000000n

If you are content with doubles, only giving approximate results for $125!$, then you only need 17 bytes:

g=x=>x?x*g(x-1):1

We see that the double result is only accurate up to 22:

for(x=0;f(BigInt(++x))==BigInt(g(x)););x // 23
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Jan 4, 2022 at 18:30
  • \$\begingroup\$ How would the method posted on sci.comp.stackexchange.com performs compared to the above methods. The method basically cut the number of multiplications by half. See link below. I cannot code but I am curious to know how the method performs. scicomp.stackexchange.com/questions/42510/… \$\endgroup\$
    – user25406
    Mar 1 at 19:42
1
\$\begingroup\$

C#: 37

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

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

JavaScript, 41

function(n,r){for(r=1;n;r*=n--);return r}

or 39 if globals are okay.

\$\endgroup\$
1
\$\begingroup\$

><>, 18 22

Launch with -v number for inputting the argument, or put it before the one.

Now also handles 0, some more intelligent direction usage, and some more space for putting numbers up to ff* or 225:

   1&:?\&n;
:-1&*&:/?=0

Old version

 1&>:&*&\
;n&\?-1 /
\$\endgroup\$
1
\$\begingroup\$

JAVA

I rarely see Java solutions here. Why is that?

    public static void main(String[] args)
 {
     int tot = 1;
 for(int i = 1;i<=5;i++)
     tot *= i;
     System.out.println(tot);
}
\$\endgroup\$
7
  • \$\begingroup\$ Yes, and it can calculate the factorial for 0. Put the factorial value in the loop continuation condition. i.e 5 \$\endgroup\$
    – Mob
    Aug 6, 2011 at 11:17
  • \$\begingroup\$ Java's a pretty verbose language, so it's not great for getting the lowest character count. \$\endgroup\$
    – Gareth
    Aug 6, 2011 at 13:34
  • \$\begingroup\$ @Gareth Yeah, but Brain Fuck isn't right? \$\endgroup\$
    – Mob
    Aug 7, 2011 at 19:13
  • \$\begingroup\$ You asked why you rarely see Java solutions here - it's because Java's verbose and less likely to win at code-golf. That's not to say there are no Java solutions, or that people shouldn't post Java solutions - they're just rarer for that reason. \$\endgroup\$
    – Gareth
    Aug 7, 2011 at 20:06
  • 3
    \$\begingroup\$ This is code-golf. With barely any work at all, you can significantly reduce the length by removing unnecessary whitespace and using 1-letter variable names \$\endgroup\$
    – Cyoce
    Feb 5, 2016 at 6:30
1
\$\begingroup\$

Scala, 39

def f(x:BigInt)=(BigInt(1)to x).product
\$\endgroup\$
1
\$\begingroup\$

Ruby, 19

[1,*2..n].inject :*

The extra hardcoded 1 at the beginning makes it work for when n=0.
Ruby auto-converts to BigInt after a certain point, so it has 100% accuracy.

\$\endgroup\$
1
\$\begingroup\$

In Q (18 characters)

f:{(*/)9h$1+til x}

Computes in less than one millisecond.

q)\t f 125
0
\$\endgroup\$
1
  • \$\begingroup\$ f:{prd 1f+til x} for 16. f:{prd 1f+(!)x} for 15. \$\endgroup\$
    – mkst
    Sep 13, 2017 at 7:44
1 2
3
4 5
8

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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