89
\$\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
  • 14
    \$\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
  • 7
    \$\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

208 Answers 208

1
3 4 5 6
7
0
\$\begingroup\$

ForceLang, 83 bytes

Noncompeting, language postdates the challenge

set a io.readnum()
set b 1
label l
set b b.mult a
set a a+-1
if a
goto l
io.write b
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 31 bytes

$s=1;map{$s*=$_}(2..<>);print$s

Prints the result in scientific notation, and takes care of the 0 value as well.

Another way to do it, but without the 0 case, for 26 bytes :

print eval join'*',(1..<>)
\$\endgroup\$
2
  • \$\begingroup\$ 26 bytes: $\=1;map$\*=$_,2..<>;print. Or 21 + 3 (flag -l61): map$\*=$_,2..<>;print. \$\endgroup\$ Nov 10, 2016 at 20:29
  • \$\begingroup\$ 21 bytes: map$.*=$_,2..<>;say$. \$\endgroup\$
    – Xcali
    Nov 15, 2017 at 23:15
0
\$\begingroup\$

Befunge-93, 24 22

0\0>-#1:_$> #\:#*_$:!+

As with the other Befunge answer(s?), this is a function in that you enter with your input on the top of the stack, start on the top-left with your pointer facing right, and exit still facing right with the result on top of the stack.

The difference is that this one is shorter, and only one row. And it still doesn't use wraparound or self-modification.

You can test it here. Testing six factorial:

6    0\0>-#1:_$> #\:#*_$:!+    .@

Outputs 720.

Testing zero:

0    0\0>-#1:_$> #\:#*_$:!+    .@

Outputs 1. The :!+ (formerly :0`!+) does at the end does nothing but check for zeroes.

EDIT: A suggestion golfed two characters off. Thanks!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You don't need the 0` part, ! will return the correct result directly. So instead your implementation should look like that 0\0>-#1:_$> #\:#*_$:!+ \$\endgroup\$
    – FliiFe
    Apr 7, 2016 at 11:14
  • \$\begingroup\$ Ah! Thank you. I'll change that now. \$\endgroup\$
    – Kasran
    Apr 9, 2016 at 17:10
0
\$\begingroup\$

Pyke, 2 bytes (non-competing)

SB

Try it here!

   - implicit input
S  -  range(1, input+1)
 B - product(^)
\$\endgroup\$
0
\$\begingroup\$

JavaScript ES6, 19 17 bytes

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

Saved two bytes by changing the conditional to n instead of n>1, because they are effectively equal.

Ungolfed

var factorial = function(n) {
  if (n > 1) {
    return f(n-1)*n;
  } else {
    return 1;
  }
}

Works just like a standard factorial. Defines a function f which multiplies it's input n by f(n-1). If n is equal to 0 or 1, then the function returns 1.

See it in Action

Check it out on JSFiddle!

\$\endgroup\$
1
  • \$\begingroup\$ Yes, exactly the same as my answer from 2 years previously. \$\endgroup\$
    – MT0
    Jun 8, 2016 at 20:06
0
\$\begingroup\$

Mathcad, tbd "bytes"

enter image description here


Mathcad byte-equivalence system yet to be determined. Some operators cannot be entered as text but have keyboard "shortcuts" instead (or can be picked from a toolbar). For example, the product operator is inserted using the key combination ctl-# ; this results in a capital Pi symbol being placed upon the Mathcad worksheet, together with 4 associated placeholders (black rectangles) which hold the iteration variable, starting value, final value and the expression for each element of the product. Balanced parentheses can be entered (in most cases) using the quote key. Typing : enters the assignment operator :=.

Mathcad has both a standard IEEE numerical floating point processing system and a longnum symbolic processing system that run in parallel over the same worksheet. = is the numeric evaluation operator whilst → is the symbolic evaluation operator.

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

Java, 51 bytes

class a{double A(double b){return b<1?1:b*A(b-1);}}

I'm actually glad Coding Ground can handle more stack frames than what is needed to overflow a double with this.

\$\endgroup\$
1
  • \$\begingroup\$ I'd +1 if the result was precise for n=125, but it is not (also, not that I reduced your byte count to 39). \$\endgroup\$ Dec 24, 2017 at 11:09
0
\$\begingroup\$

Neoscript, 31 bytes

{n|(0:(]:n):reduce({x y|x*y}1)}
\$\endgroup\$
0
\$\begingroup\$

Logy, 47 bytes

f[X]->include["@stdlib.logy"]~product[..[2,X]];

Trivial. Return the product of the range [2..n]

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

Bash w/Core Utils & BC, 15 Bytes

Saw 2 other bash solutions, but both longer than this one:

seq -s* `dd`|bc

number to factorial for from stdin, factorial to stdout

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

Tcl, 41 37 35 bytes

proc f n {expr $n?($n)*\[f $n-1]:1}

Try it online!

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

Recursiva, 12 bytes

=a0:1!*a#~a$

Try it online!

Explanation:

=a0:1!*a#~a$
=a0:1        - If a==0 return 1
     !       - Else
      *      - Multiply
       a     - a
        #~a$ - Call self but with parameter a-1
\$\endgroup\$
0
\$\begingroup\$

Axiom, 42 31 bytes

h x==(x=0=>1;product(i,i=1..x))

The 42 bytes one

s(x)==(x=0=>1;reduce(*,[j for j in 1..x]))

There could be even the 37 bytes

f(x)==(x=0=>1;reduce(*,expand(1..x)))

but there is one warning when I use it the first time

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

Brainfuck, 109 Bytes

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

The factorial is left on the tape at position 4, user input is taken as an ASCII character. Meets all requirements except for completing in under a minute.

How it works:

>>>,

Gets user input and stores it in position 4. The rest of the code is in brackets to account for an input of zero. In that case, none of the following code is executed, and it skips to the last command.

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

Move the input number to positions 1, 3, and 5.

>-[<+>-]

Decreases the number at 5, and moves it to 4.

<<<<-

Decrease the number at 1. This serves as a counter for how many times we need to multiply

This is where most of the work occurs:

[                | While 1 is non-zero (n-1 times)
  >>[            | Move to 3, and while it's non-zero
    >[           | Move to 4
      >+>+<<-    | Copy it into 5 and 6
    ]>>          | Move to 6
    [            |
      <<+>>-     | Copy it to 4
    ]<<<-        | Move to 3, decrease it
  ]<<-           | Move to 1, decrease it (one multiplication has been done)
  [              |
    >+>+<<-      | Copy the value at 1 to 2 and 3
  ]>             | Move to 2
  [              |
    <+>-         | Put it back in 1
  ]>>            | Go to 4
  [-]            | Zero it
  >[             | Go to 5
    <+>-         | Copy 5 to 4
  ]              |
<<<<]            | Go back to 1

For values >1, we could end here, but for 1:

>>[->+<]<<]

No multiplications will have been done, and we'll have a 1 in position 3. If this is the case, move it to 4. Return to 1.

]+

If the input was 0, put a one in the current position (4, since we never moved)

\$\endgroup\$
1
  • \$\begingroup\$ Thought I'd let you know I made a much shorter answer, almost halving your byte count \$\endgroup\$
    – Jo King
    Nov 24, 2017 at 9:51
0
\$\begingroup\$

Javascript (No body version), 23 bytes

f=(n,t=n?n*f(n-1):1)=>t

Saved 2 bytes with n?n, got the idea from Drew Christensen. This is what I had before

f=(n,t=0**n||n*f(n-1))=>t

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

4, 37 bytes

3.70060101602018002010100100000295014

Try it online!

If you question the input method, please visit first the numerical input and output may be given as a character code meta post.

Pseudo code

g_0 = input()
g_1 = 1
while g_0 != 0:
  g_1 *= g_0
  g_0 -= 1
print(g_1)
\$\endgroup\$
0
\$\begingroup\$

Forth (gforth), 31 bytes

: f 1e 0 ?do i 1+ s>f f* loop ;

Try it online!

Answer will be on the floating point stack as 125! exceeds the maximum double precision integer value (by a lot)

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

Stax, 4 bytes

┤c5ô

Run and debug it online

Unpacked version with 5 bytes:

!x+k*

Explanation

!x+      Compute logical not, then add to itself
             The result is denoted `m`
   k*    reduce with multiplication over the range [1..m]
\$\endgroup\$
0
\$\begingroup\$

Gol><>, 8 bytes

1IFLP*|h

Try it online!

How it works

1IFLP*|h

1         Push 1
 I        Take input (n) as int
  F   |   Repeat n times...
   LP*      Multiply loop counter(L) + 1; L = 0..n-1
       h  Print the top as int and halt

Function form, 8 bytes

Assuming that stack input and stack output are allowed for Gol><> functions.

1$FLP*|B

Try it online!

Takes the stack as input (assuming the stack has only one value), and leaves the factorial as the only content of the stack. $ is used to push 1 to the bottom, and B is the "return" command. Note that B inside an F (for) or W (while) loop acts as a "break" instead.

Using the Gol><> function

The following code uses the function above to output 0! to 125!.

1AG`~FLGN|;
1$FLP*|B

1AG          Register row 1 as function G
   `~        126
     F   |   Repeat from 0 to 125...
               Stack is empty at this point
      L        Push loop counter
       G       Call G on the current stack
        N      Pop and print as number, with newline
          ;  Halt
\$\endgroup\$
0
\$\begingroup\$

dc, 22 bytes

[1q]sg[d2>gd1-d2<f*]sf

Try it online! (requires Javascript)

This is the obvious 12-byte implementation ([d1-d1<f*]sf) with an additional test to short-circuit the calculation for numbers less than 2 (which otherwise subtract too far, yielding a product of zero).

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

Java (JDK 10), 84 bytes

n->{var r=java.math.BigInteger.ONE;for(;n>0;)r=r.multiply(r.valueOf(n--));return r;}

Try it online!

Credits

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save 5 bytes by using Java 9's var and removing the r=null initialisation: n->{var r=java.math.BigInteger.ONE;for(;n>0;)r=r.multiply(r.valueOf(n--));return r;} \$\endgroup\$
    – mgthomas99
    Sep 11, 2018 at 21:45
  • 2
    \$\begingroup\$ @mgthomas99 Indeed! But it's Java 10's var, not Java 9's ;) and it wasn't released at the time I wrote that answer. But I have no issue switching to Java 10. \$\endgroup\$ Sep 12, 2018 at 7:48
0
\$\begingroup\$

Japt, 4 bytes

oÄ ×

Try it


Explanation

o        :Range [0,input) (= empty array when input is 0)
 Ä       :Add 1 to each
   ×     :Reduce by multiplication, with an initial value of 1
\$\endgroup\$
0
\$\begingroup\$

PHP, 40 39 bytes

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

Thanks to @JoKing for saving 1 byte and correcting the input

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ @JoKing changed the answer to reflect 🤓 \$\endgroup\$ Feb 19, 2019 at 12:05
0
\$\begingroup\$

Kotlin, 50 45 bytes

fun f(x:Int):Int=when(x){0->1;else->x*f(x-1)}

Thanks to @jonathan-frech

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to PPCG. I think the 1->1; clause is superfluous. \$\endgroup\$ Feb 19, 2019 at 14:22
0
\$\begingroup\$

Python 3, 32 29 bytes

lambda n:n*f(n-1)if n>0else 1

Try it online! Just a simple recursive solution I made for Generalised multi-dimensional chess knight's moves.

Thanks for the -3 Maanas

\$\endgroup\$
2
  • \$\begingroup\$ Try it online! -3 chars by putting f= in the header part and removing the space between 0 and else \$\endgroup\$
    – PyGamer0
    Jun 16, 2021 at 4:27
  • \$\begingroup\$ oh, I didn't realise that was something you could do with the f= bit as I originally just wrote the function in sublime text. \$\endgroup\$ Jun 16, 2021 at 4:29
0
\$\begingroup\$

Dyalog APL, 1 char

!

! is a primitive function in Dyalog APL: in the monadic case (right argument only) gives the factorial of the right argument

https://tio.run/##SyzI0U2pTMzJT////1Hf1EdtExQNuKAMQxjDFC6CkDP9/x8A

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

Flobnar, 17 bytes

>-::
>1*_
\@<^
&:

Try it online!

Individually developed as part of LYAL on 2022-07-06, and it happens to beat JoKing's 19 bytes.

How it works

\@    Start at @, facing left
&     \ pushes & (decimal input) to the call stack (call it n)
      and keep evaluating left
:
_>1   Horizontal if: if n (:) is 0, evaluate to right (1), otherwise
^

  :
  *   Multiply n (:) with the result of recursive function call
\ <   (& fails and falls through to south)
&:    called with n-1
>-
 1
\$\endgroup\$
0
\$\begingroup\$

bc, 42 bytes

define f(n){if(n)return n*f(n-1)
return 1}

Try it online!

bc (POSIX), 45 bytes

define f(n){
if(n)return(n*f(n-1))
return(1)}

Try it online!

\$\endgroup\$
1
3 4 5 6
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.