views:

1828

answers:

38

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);
}
FlySwat
Interestingly, that's the same as my attempts in both C and C++!
1800 INFORMATION
Imagine that :), For what its worth, I have posted another one that is definitely not compatible with C/C++ :D
FlySwat
You can shorten the code by doing: {return v?v*f(v-1):1;}
Jonathan Leffler
Downvoted for explaining ternary operation
Kevin
what the fuck is up with the question mark??!?
Shawn Simon
Kevin, Why? Obviously gogo wanted to know :D
FlySwat
You should change the int output to decimal, you'll get more reliable output. Of course, this extends the code by 4 chars...
BenAlabaster
@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.
BenAlabaster
(Reader.KnowsTernaryOperation) ? DownVote() : UpVote()
Martin
+11  A: 

Haskell:

\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.

Peter Burns
So what is product[1..0]?
tvanfosson
It's 1 because [1..0] is the empty list
Peter Burns
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)`.
Daniel Pryden
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.

FlySwat
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.
BenAlabaster
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..

Eugene M
+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.

Ken Paul
You haven't actually written a factorial function though, innit?
Menkboy
Can you provide an explanation for this?
Claudiu
'!' 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.
ephemient
Hardly making the brain tick... ;)
Ray Booysen
Kind of lame... you didn't really do anything.
Ed Swangren
... __doesn't rely on built in functions__ ...
Callum Rogers
+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;}
Federico Ramponi
Nice job on the C one, its lack of a native boolean type actually is handy for once.
FlySwat
Does it work in C#? I suppose so but I'm not sure
Federico Ramponi
Nope, you would need to do (bool)n, otherwise it complains about invalid cast.
FlySwat
Or in my case, use a conditional expression (n<2).
FlySwat
+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,&:*)
Peter Burns
26 chars = length of your max haskell impl
Alan
steenslag
+1  A: 

Java:

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

Identical to C.

Skip Head
+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?

Menkboy
fails on input = 0
I. J. Kennedy
+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.

bk1e
A: 

22 characters of Standard ML:

fun f 0=1|f n=n*f(n-1)
bk1e
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?
Peter Burns
Question: How many solutions here *are* tail-recursive? (Answer: Not many.)
ephemient
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).
bk1e
IIRC, your function will work with arbitrary precision as-is because it depends upon the call site unless you evaluate your function alone interactively.
Jon Harrop
A: 

OCaml:

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

Perl, 32 characters

sub f{$_[0]?$_[0]*f($_[0]-1):1;}
Matthew Scharley
+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.

sundar
+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)
David
+3  A: 

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

f=lambda n:n<2and 1or n*f(n-1)
Claudiu
29: f=lambda n:n and n*f(n-1)or 1
recursive
A: 
def f(n): return reduce(lambda x,y: x*y,range(1,n+1))
esiegel
Might want to specify that this is Python.
ephemient
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.

Adam Rosenfield
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.
David Thornley
+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
Brad Gilbert
Rakudo now supports the postfix:<!> variant http://perlgeek.de/blog-en/perl-6/custom-operators-in-rakudo.writeback
Brad Gilbert
+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.

Hynek -Pichi- Vychodil
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.
Hudson
I'm not familiar with this sort of recursion what you used. I should learn to use it. Thanks for advice.
Hynek -Pichi- Vychodil
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.
Hudson
+2  A: 

Language: Golfscript, Char count: 10

My first script in golfscript at all:

 ,{1+}%{*}*
Hynek -Pichi- Vychodil
+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.

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

New python record: 28 chars

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

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

Ray Tayek
+1  A: 

F#:

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

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

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

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

20 characters

seq $n|paste -sd*|bc
Johannes Schaub - litb
A: 

Scala:

def f(n:Int)=(1/:(1 to n))(_*_)
Germá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; }
BenAlabaster
+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]
Uros Dimitrijevic
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.
Stafford Rootbeer
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);}
JStriedl
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.

Pillsy
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 %))))
nilamo
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);
Dykam
+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
    adds    r3,     $1
    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
Stephen Canon
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
Mark Rushakoff
A: 

PHP - 59 chars

function f($n){return array_reduce(range(1,$n),'bcmul',1);}
Alix Axel
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`
Callum Rogers