1828

38
+3  Q:

## Code Golf: Factorials

Since the palindrome code golf was a big hit, here is one that doesn't rely on built in functions.

What is the shortest (in characters) way to write a factorial function?

+3  A:

My attempt, using C#:

``````int f(int v){return v<2?1:v*f(v-1);}
``````

38 Characters, counting whitespace.

For those who don't understand the ? operator, it works like this:

``````  (Condition) ? (Return this if true) : (Return this if false)
``````

So, in my case, it collapses this:

``````if (v<2)
{
return 1;
}
else
{
return v*f(v-1);
}
``````
Interestingly, that's the same as my attempts in both C and C++!
Imagine that :), For what its worth, I have posted another one that is definitely not compatible with C/C++ :D
You can shorten the code by doing: {return v?v*f(v-1):1;}
Downvoted for explaining ternary operation
what the fuck is up with the question mark??!?
Kevin, Why? Obviously gogo wanted to know :D
You should change the int output to decimal, you'll get more reliable output. Of course, this extends the code by 4 chars...
@Jonathan Leffler: You can't implicitly convert an int (v) to bool for the condition, so that wouldn't work, changing v < 2 to v > 1 and switching the outputs around would however make it more readable.
+11  A:

``````\n->product[1..n]
``````

17 characters, 20 with reasonable whitespace. As a named function:

``````fac n = product [1..n]
``````

22 characters. Without using `product`:

``````fac n = foldr (*) 1 [1..n]
``````

26 characters

These (largely equivalent) implementations have no stack overflow or integer overflow errors. Compiled with ghc, this calculates and prints all 35661 digits of 10000! in 0.11s and all 456575 digits of 100000! in 11.145s on my two year old laptop. Of course, there are doubtless faster algorithms, but that's not bad performance for a naive solution.

So what is product[1..0]?
It's 1 because [1..0] is the empty list
Yup, this is definitely one that favors functional languages. Even the naive approach in Haskell is still shorter than most of the other responses here: `fac 1=1; fac n=n*fac(n-1)`.
A:

I tried to get creative with using a lambda instead of a regular function to make it smaller.

However, you can't recurse on an anonymous type, so I get this:

``````Func<int,int>f=null;f=v=>v<2?1:v*f(v-1);
``````

41 characters.

nice, switching around your condition to v>1?v*f(v-1):1 reads a little easier and changing your output to decimal would make it more useful for higher factorials...although still only good to about 27, but better than the 13 that int reliably works for.
A:

40 in python without trying too hard.

``````def f(n):return (1 if n<2 else n*f(n-1))
``````

EDIT: Make that 38 . I guess I didn't need the extra parens above..

+20  A:

It's only 2 characters in APL, where most math functions are intrinsic:

``````?!
``````

Explanation: The question mark operator requests user input, and the monadic exclamation point applies the factorial function. Since the result isn't assigned to any variable or used in further calculations, it gets printed.

APL isn't as popular as it used to be, but one of my customers still has some production APL applications.

You haven't actually written a factorial function though, innit?
Can you provide an explanation for this?
'!' works in J, too, though requesting user input isn't as succinct as '?' (which is taken for random): '_".}:1!:1<3'. If you don't want to use '!', '*/@(1+i.)' does the same in J -- I imagine '*/⍳' works in APL, but I don't have an APL interpreter to test it on.
Hardly making the brain tick... ;)
Kind of lame... you didn't really do anything.
... __doesn't rely on built in functions__ ...
+1  A:

34 in python:

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

34 in C:

``````int f(int n){return n?n*f(n-1):1;}
``````
Nice job on the C one, its lack of a native boolean type actually is handy for once.
Does it work in C#? I suppose so but I'm not sure
Nope, you would need to do (bool)n, otherwise it complains about invalid cast.
Or in my case, use a conditional expression (n<2).
+3  A:

Ruby, 19 characters + the length of the number to be computed (in this case, 1 character for the variable `n`)

``````(1..n).inject(1,&:*)
``````
+1  A:

Java:

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

Identical to C.

+6  A:

9 bytes of i386 machine-code. Input is EAX, output is EAX.

``````#AT&T syntax
mov %eax, %ebx
again:
dec %ebx
.byte 0x74, 4    #jz (short) done
mul %ebx
.byte 0xEB, -7   #jmp (short) again
done:
``````

PS: Anyone know why `as` won't genetrate short jumps for me?

fails on input = 0
+5  A:

66 characters of Windows `cmd.exe` batch language (Win2K or later only):

``````set r=1
for /l %%i in (1,1,%1) do call set/a r=%%r%%*%%i
echo %r%
``````

The recursive version was shaping up to be much larger.

A:

22 characters of Standard ML:

``````fun f 0=1|f n=n*f(n-1)
``````
This isn't tail recursive. Does this run out of stack space, or are there Standard ML compilers which will rewrite it with an accumulator?
Question: How many solutions here *are* tail-recursive? (Answer: Not many.)
My function doesn't use large integers, so f(13) raises an (integer) Overflow exception, nowhere near a stack overflow. SML/NJ supposedly uses the heap instead of a call stack, so you can probably run out of heap if you change "0" to "(0:LargeInt.int)" and compute something like f(1000000).
IIRC, your function will work with arbitrary precision as-is because it depends upon the call site unless you evaluate your function alone interactively.
A:

OCaml:

``````let rec f n = if n=0 then 1 else n*f(n-1);;
``````
You can save 5 characters with:let rec f= function 0->1|n->n*f(n-1);;
+1  A:

Perl, 32 characters

``````sub f{\$_[0]?\$_[0]*f(\$_[0]-1):1;}
``````
+25  A:

Probably the longest entry here, but brainf*ck is special in any case... :)

So, here goes my entry at 93 characters:

``````,>++++++[<-------->-]<[->+>+<<]>>->>+<<<[>[<[->[-<<+>>>+<]>[-<+>]<<]<[->+<]>>-]<.>>>-]>>>[.-]
``````

Commented and indented:

``````,
>++++++ Put 6 in next cell
[<-------->-] Subtract 8 six times to subtract 48
<
[->+>+<<]  Move (0) to (1) and (2)
>>-  Decrement one from (2) as we want to multiply n * n minus 1
>>+  Store 1 in (4) to allow distinguishing 0 separately
<<< Go to (1)
[   A makeshift if(\$_ != 0)
>[   While (2)
<[   While(1)
- Subtract one from (1) for multiplication by repeated addition
>[-<<+>>>+<] Add (2) to (0) and (3)
>[-<+>] Move data from (3) to (2)
<<
]
<[->+<] Copy (0) to (1) for next round of multiplication
>>- Decrement (2) to go to n minus 2 and so on
]
<.>>>-  Print output from (1) and make (4) = 0 to stop the if
]
>>>[.-]  If we're at (4) (and it is nonzero) we have a 0 as input; so print 1 and stop;
``````

EDIT: Seeing the other language codes do not include input code and just take the number as an argument, I too removed the input part and assumed the number was contained as argument in (0). Now it's reduced to 71 characters:

``````[->+>+<<]>>->>+<<<[>[<[->[-<<+>>>+<]>[-<+>]<<]<[->+<]>>-]<.>>>-]>>>[.-]
``````

The outputting algorithm is non trivial so I decided not to remove it.

+1 for commented brainf*ck code - I never understood BF so clearly until now (where 'clearly' is relatively defined vs. what I used to know about it)
+3  A:

30 characters in Python, an improvement of 8 over the other python.

``````f=lambda n:n<2and 1or n*f(n-1)
``````
29: f=lambda n:n and n*f(n-1)or 1
A:
``````def f(n): return reduce(lambda x,y: x*y,range(1,n+1))
``````
Might want to specify that this is Python.
A:

28 characters in C:

``````F(n){return n>1?n*F(n-1):1;}
``````

Note that this uses the old-style default-int convention.

You can trim two characters off that: replace "n>1" with "n". You recurse one more time, and lose the questionable ability to handle negative input, but it's two whole characters off.
+2  A:

## Perl 6:

19 characters.

``````sub f(\$n){[*]1..\$n}
``````

16 characters

``````sub f{[*]1..\$^n}
``````

If you wanted to call it like `'5!'`
30 characters.

``````sub postfix:<!>(\$n){[*]1..\$n}
``````

Or for an anonymous code block
11 characters.

``````{[*]1..\$^n}

say {[*]1..\$^n}(5) # 120
``````
Rakudo now supports the postfix:<!> variant http://perlgeek.de/blog-en/perl-6/custom-operators-in-rakudo.writeback
+1  A:

### Language: dc, Char count:23

23 chars version:

``````dc -e'?d[1-dsa*lad1<b]dsbxszp' <<<1000
``````

Edit: More readable (24 chars) version by Hudson

``````dc -e'?[q]sQ[d1=Qd1-lFx*]dsFxp' <<<1000
``````

I should mention that dc is arbitrary precision calculator.

I find this more readable since F only requires the one argument on the stack: '?[q]sQ[d1=Qd1-lFx*]dsFxp'. Don't forget to mention that dc supports arbitrary precision, so it doesn't matter how big the input is.
I'm not familiar with this sort of recursion what you used. I should learn to use it. Thanks for advice.
The '[q]sQ' create a macro named Q that emulates an early return; q will break out of two levels of function calls. I use that idiom in most of my dc scripts.
+2  A:

### Language: Golfscript, Char count: 10

My first script in golfscript at all:

`````` ,{1+}%{*}*
``````
+8  A:

Not the shortest, but certainly the least appropriate technique: C++ templates to compute factorial as part of the type signature of the class:

``````#include <iostream>

template <int N>
struct Factorial
{
enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0>
{
enum { value = 1 };
};

int main()
{
std::cout << "4!=" << Factorial<4>::value << std::endl;
}
``````

This will fail to produce valid answers for even moderate values of N.

Hah! I read the output as 4 != 24, which is true, of course. xD
Wow, really good!
This one is even more interesting. It uses templates to determine the primality of 13: http://homepage.mac.com/sigfpe/Computing/peano.html
We have it easy now that most compilers accept ints as template parameters instead of having to that successor stuff!
A:

### New python record: 28 chars

``````f=lambda x:+(x<2)or x*f(x-1)
``````
+1  A:

25 characters in groovy: def f(n){n<=2?n:n*f(n-1)}

+1  A:

F#:

``````let f n = [1..n] |> Seq.fold ( * ) 1
``````

With spaces: 36 chars. Spaces removed, 30 chars.

Seq.fold ( * ) 1 [1..n]
You can also use Seq.reduce instead of Seq.fold, but it works out to the exact same number of characters.
A:

Someone posted `dc`. I'm going to post `bc, paste & seq`:

20 characters

``````seq \$n|paste -sd*|bc
``````
A:

Scala:

``````def f(n:Int)=(1/:(1 to n))(_*_)
``````
A:

C#:

Slightly longer than the previous poster, but more useful as it is not as limited as with an int output, can resolve up to 28! instead of only 13!

Also, v > 1 is easier on the eye than v < 2

``````decimal f(int v) { return v > 1 ? v * f(v - 1) : 1; }
``````
+1  A:

In the J programming language, factorial is built-in, so:

``````fact=:!
``````

but that's boring, so let's do it manually:

``````fact=:*/@:(1+i.)
``````

I guess this little-known language looks pretty unreadable, but here's the equivalent Haskell definition:

``````fact = foldr1 (*) . \n -> [1..n]
``````
A:

R5RS w/ blatant whitespace abuse:

``````(define(f x)(if(= x 0)1(* x(f(- x 1)))))
``````
A:

Smalltalk-80

``````f||self=0 ifTrue:[^1].^self*f self-1.
``````
A:

The most brief version in AS3 at 37 characters:

``````function f(i){return i<1?1:i*f(i-1);}
``````

Which is the stripped down version of the more readable:

``````function factorial(i:Number):Number{return (i<1) ? 1 : i * factorial(i-1);}
``````
A:

Skipping the obvious `n!` in Mathematica, we can do it recursively, like so:

``````If[#1<=#2,#1,#0[#1,2#2]#0[#1-#2,2#2]]&[#,1]&
``````

for a total of 44 characters. This is a more efficient algorithm than the freshman year recursion example, which weights in at a mere 28 characters.

``````If[#1<1,1,#1#0[#1-1]]&[#,0]&
``````

Of course, a list-based solution is even shorter (15 characters).

``````[email protected]@[email protected]#&
``````

When golfing in Mathematica, you can save a lot of strokes by (ab)using its very terse syntax for pure functions and function application.

A:

## Clojure - 36 chars

I'm learning Clojure right now (a dialect of Lisp), so I thought I'd do one in that.

``````(defn ![n](apply *(range 1(inc n))))
``````

To be called like so: `(! n)`

`*` throws errors for ranges and lazy seqs, which is why apply was added.

Two characters can be shaved off by binding an anonymous function to `!`:

``````(def ! #(apply *(range 1(inc %))))
``````
A:

## C# 41:

``````Func<int,int> f=null;f=x=>x<2?1:x*f(x-1);
``````

## C# 49, decimal

``````Func<decimal,decimal> f=null;f=x=>x<2?1:x*f(x-1);
``````

C# int formatted:

``````Func<int,int> f = null;
f = (x) => (x < 2) ? 1 : x * f(x-1);
``````
+3  A:

66 bytes of ARM assembly (thumb2). Not as short as many, but produces a bignum result. I'm sure that a few more bytes could be saved with some care.

``````// uint32_t factorial(uint32_t n, uint32_t *result, uint32_t length);
//
// stores n! in the buffer result as a little-endian bignum.  length is
// size of the buffer in (32-bit) words.  It is the caller's responsibility
// to allocate and free the result buffer.  If the buffer is not large
// enough to contain n!, 0 is returned.  On successful exit, the return
// value is the number of (32-bit) words of the buffer that were used to
// store the result.

_factorial:
push   {r4-r7}
tst     r2,     r2
beq     Lerror
movs    r3,     #1
str     r3,    [r1]
tst     r0,     r0
beq     Ldone
Lloop:
eors    r6,     r6
movs    r7,     r3
Lmultiply:
movs    r5,     r6
eors    r6,     r6
ldr     r4,    [r1]
umlal   r5, r6, r0, r4
str     r5,    [r1], #4
subs    r7,     \$1
bne     Lmultiply
tst     r6,     r6
beq     LnoOverflow
cmp     r3,     r2
bhi     Lerror
str     r6,    [r1], #4
LnoOverflow:
sub     r1, r1, r3, lsl #2
subs    r0,     \$1
bne     Lloop
Ldone:
mov     r0,     r3
Lexit:
pop    {r4-r7}
bx      lr
Lerror:
eors    r0,     r0
b       Lexit
``````
A:

# Lua

## 45 chars

Since Lua wasn't on here already.

``````function f(i)return i>0 and i*f(i-1)or 1 end
``````
A:

# PHP - 59 chars

``````function f(\$n){return array_reduce(range(1,\$n),'bcmul',1);}
``````
A:

# Repent - 3 chars

Repent is a esoteric stack based language of my own, use this interpreter (language reference). Put the arguments in the "command line args" textbox.

``````1.∏
``````

Explanation:

``````1 `Push a one to the stack`
. `Make a list from the argument to 1 (e.g. [6,5,4,3,2,1])`
∏ `N-Ary-Product - multiply all the values in the list together`
``````