82
\$\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\$
11
  • 13
    \$\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
  • 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 '11 at 3:21
  • 6
    \$\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\$ Aug 24 '17 at 21:20
  • 3
    \$\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 '19 at 2:02

195 Answers 195

1 2
3
4 5
7
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\$
    – ogogmad
    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\$

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 '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\$
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 '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\$
2
  • \$\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
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 '14 at 20:05
  • \$\begingroup\$ n.downto(1).inject(1,:*) \$\endgroup\$
    – histocrat
    Jul 24 '15 at 17:12
  • \$\begingroup\$ Or in fact (1..n).inject 1,:* seems to work fine. \$\endgroup\$
    – histocrat
    Jul 24 '15 at 17:14
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 '15 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 '15 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 '15 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 '15 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 '18 at 6:26
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 '19 at 11:38
  • \$\begingroup\$ I'm getting an error running that code on TIO. \$\endgroup\$ Sep 25 '19 at 20:38
  • \$\begingroup\$ Run this in an old version. (Works for most of my Keg answers) \$\endgroup\$
    – user85052
    Sep 25 '19 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\$
2
\$\begingroup\$

V (vim), 33 bytes

S<C-r>=r<Tab>1,<C-r>"<BS>)
<C-o>:%s/\n/*/g
<C-o>C<C-r>=<C-r>"<BS><BS>

Try it online!

Explanation:

S<C-r>=r<Tab>1,<C-r>"<BS>)  # Replace N with [1, ..., N]
<C-o>:%s/\n/*/g             # Merge all lines with *
<C-o>C<C-r>=<C-r>"<BS><BS>  # Remove trailing * and evaluate.

Overflows for any N greater than 49, but would work properly otherwise.

\$\endgroup\$
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 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 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 at 16:46
  • \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ Jul 14 at 16:53
  • \$\begingroup\$ @Razetime thx ))) \$\endgroup\$
    – AgentIvan
    Nov 4 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\$
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 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 at 21:25
  • 2
    \$\begingroup\$ That used to be the case, but we decided to revert that rule \$\endgroup\$
    – Mayube
    Nov 5 at 21:32
  • \$\begingroup\$ ah good to know \$\endgroup\$
    – Hydrazer
    Nov 6 at 1:57
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 '11 at 11:15
  • \$\begingroup\$ whoopsies, you're right. \$\endgroup\$
    – Origamiguy
    Jul 10 '11 at 12:38
  • 4
    \$\begingroup\$ int is way too small to hold 125!, which is something like 1.88e+209. \$\endgroup\$ Jul 12 '11 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 '11 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 '11 at 13:34
  • \$\begingroup\$ @Gareth Yeah, but Brain Fuck isn't right? \$\endgroup\$
    – Mob
    Aug 7 '11 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 '11 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 '16 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 '17 at 7:44
1
\$\begingroup\$

F# based on cfern's 63 36 characters

His didn't work on 125 for me. Adapted to use BigInteger

let f n:BigInteger=Seq.fold(*)BigInteger.One{BigInteger.One..n}

Edit: I just realized that double works too.

let f n:double=Seq.fold(*)1.{1.0..n}
\$\endgroup\$
1
  • \$\begingroup\$ 63 -> 36 is simply beautiful. "I reverse the floating point usage, you reverse your byte count!" \$\endgroup\$ Sep 30 '20 at 19:00
1
\$\begingroup\$

C++11 (35 chars)

Here's the function version:

int f(int x){return x?x*f(x-1):1;}

C++11 template version (103 chars)

And here's the template version:

template<int I>struct f{static const int v=I*f<I-1>::v;};template<>struct f<0>{static const int v=1;};
\$\endgroup\$
1
\$\begingroup\$

Golfscript — 16

{.!+,{(}%{*}*}:f

The way I handle 0! is to do this trick: .!+:

  • 0 + 0! = 0 + 1 = 1
  • a + a! = a + 0 = a (for every a != 0)

or:

{),{)}%);{*}*}:f

Here, I start of by increasing the argument by 1. But before I factor the array, I drop the last element.

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

PHP, 41

function f($i){return $i==1?:$i*f($i-1);}
\$\endgroup\$
1
\$\begingroup\$

C 20 characters

x(){while(n)f*=n--;}

Assuming f and n are global variables. Here is the entire program :

double n=5,f=1;

x(){while(n)f*=n--;}

main(){
x();
printf("%f",f);
}
\$\endgroup\$
1 2
3
4 5
7

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.