What's the shortest code to cause a stack over

问题:

To commemorate the public launch of Stack Overflow, what's the shortest code to cause a stack overflow? Any language welcome.

ETA: Just to be clear on this question, seeing as I'm an occasional Scheme user: tail-call "recursion" is really iteration, and any solution which can be converted to an iterative solution relatively trivially by a decent compiler won't be counted. :-P

ETA2: I've now selected a “best answer”; see this post for rationale. Thanks to everyone who contributed! :-)

回答1:

All these answers and no Befunge? I'd wager a fair amount it's shortest solution of them all:

1

Not kidding. Try it yourself: http://www.quirkster.com/iano/js/befunge.html

EDIT: I guess I need to explain this one. The 1 operand pushes a 1 onto Befunge's internal stack and the lack of anything else puts it in a loop under the rules of the language.

Using the interpreter provided, you will eventually--and I mean eventually--hit a point where the Javascript array that represents the Befunge stack becomes too large for the browser to reallocate. If you had a simple Befunge interpreter with a smaller and bounded stack--as is the case with most of the languages below--this program would cause a more noticeable overflow faster.

回答2:

Read this line, and do what it says twice.

回答3:

You could also try this in C#.net

throw new StackOverflowException();

回答4:

Nemerle:

This crashes the compiler with a StackOverflowException:

def o(){[o()]}

回答5:

My current best (in x86 assembly) is:

push eax
jmp short $-1

which results in 3 bytes of object code (50 EB FD). For 16-bit code, this is also possible:

call $

which also results in 3 bytes (E8 FD FF).

回答6:

PIC18

The PIC18 answer given by TK results in the following instructions (binary):

overflow
   PUSH
   0000 0000 0000 0101
   CALL overflow
   1110 1100 0000 0000
   0000 0000 0000 0000

However, CALL alone will perform a stack overflow:

CALL $
1110 1100 0000 0000
0000 0000 0000 0000

Smaller, faster PIC18

But RCALL (relative call) is smaller still (not global memory, so no need for the extra 2 bytes):

RCALL $
1101 1000 0000 0000

So the smallest on the PIC18 is a single instruction, 16 bits (two bytes). This would take 2 instruction cycles per loop. At 4 clock cycles per instruction cycle you've got 8 clock cycles. The PIC18 has a 31 level stack, so after the 32nd loop it will overflow the stack, in 256 clock cycles. At 64MHz, you would overflow the stack in 4 micro seconds and 2 bytes.

PIC16F5x (even smaller and faster)

However, the PIC16F5x series uses 12 bit instructions:

CALL $
1001 0000 0000

Again, two instruction cycles per loop, 4 clocks per instruction so 8 clock cycles per loop.

However, the PIC16F5x has a two level stack, so on the third loop it would overflow, in 24 instructions. At 20MHz, it would overflow in 1.2 micro seconds and 1.5 bytes.

Intel 4004

The Intel 4004 has an 8 bit call subroutine instruction:

CALL $
0101 0000

For the curious that corresponds to an ascii 'P'. With a 3 level stack that takes 24 clock cycles for a total of 32.4 micro seconds and one byte. (Unless you overclock your 4004 - come on, you know you want to.)

Which is as small as the befunge answer, but much, much faster than the befunge code running in current interpreters.

回答7:

C#:

public int Foo { get { return Foo; } }

回答8:

Hoot overflow!

//              v___v
let rec f o = f(o);(o)
//             ['---']
//             -"---"-

回答9:

Every task needs the right tool. Meet the SO Overflow language, optimized to produce stack overflows:

so

回答10:

TeX:

\def~{~.}~

Results in:

! TeX capacity exceeded, sorry [input stack size=5000].
~->~
    .
~->~
    .
~->~
    .
~->~
    .
~->~
    .
~->~
    .
...
<*> \def~{~.}~

LaTeX:

\end\end

Results in:

! TeX capacity exceeded, sorry [input stack size=5000].
\end #1->\csname end#1
                      \endcsname \@checkend {#1}\expandafter \endgroup \if@e...
<*> \end\end

回答11:

Z-80 assembler -- at memory location 0x0000:

rst 00

one byte -- 0xC7 -- endless loop of pushing the current PC to the stack and jumping to address 0x0000.

回答12:

In english:

recursion = n. See recursion.

回答13:

Another PHP Example:

<?
require(__FILE__);

回答14:

How about the following in BASIC:

10 GOSUB 10

(I don't have a BASIC interpreter I'm afraid so that's a guess).

回答15:

I loved Cody's answer heaps, so here is my similar contribution, in C++:

template <int i>
class Overflow {
    typedef typename Overflow<i + 1>::type type;
};

typedef Overflow<0>::type Kaboom;

Not a code golf entry by any means, but still, anything for a meta stack overflow! :-P

回答16:

Here's my C contribution, weighing in at 18 characters:

void o(){o();o();}

This is a lot harder to tail-call optimise! :-P

回答17:

Using a Window's batch file named "s.bat":

call s

回答18:

Javascript

To trim a few more characters, and to get ourselves kicked out of more software shops, let's go with:

eval(i='eval(i)');

回答19:

Groovy:

main()

$ groovy stack.groovy:

Caught: java.lang.StackOverflowError
    at stack.main(stack.groovy)
    at stack.run(stack.groovy:1)
 ...

回答20:

Please tell me what the acronym "GNU" stands for.

回答21:

Person JeffAtwood;
Person JoelSpolsky;
JeffAtwood.TalkTo(JoelSpolsky);

Here's hoping for no tail recursion!

回答22:

C - It's not the shortest, but it's recursion-free. It's also not portable: it crashes on Solaris, but some alloca() implementations might return an error here (or call malloc()). The call to printf() is necessary.

#include <stdio.h>
#include <alloca.h>
#include <sys/resource.h>
int main(int argc, char *argv[]) {
    struct rlimit rl = {0};
    getrlimit(RLIMIT_STACK, &rl);
    (void) alloca(rl.rlim_cur);
    printf("Goodbye, world\n");
    return 0;
}

回答23:

perl in 12 chars:

$_=sub{&$_};&$_

bash in 10 chars (the space in the function is important):

i(){ i;};i

回答24:

try and put more than 4 patties on a single burger. stack overflow.

回答25:

Python:

so=lambda:so();so()

Alternatively:

def so():so()
so()

And if Python optimized tail calls...:

o=lambda:map(o,o());o()

回答26:

I'm selecting the “best answer” after this post. But first, I'd like to acknowledge some very original contributions:

1. aku's ones. Each one explores a new and original way of causing stack overflow. The idea of doing f(x) ⇒ f(f(x)) is one I'll explore in my next entry, below. :-)
2. Cody's one that gave the Nemerle compiler a stack overflow.
3. And (a bit grudgingly), GateKiller's one about throwing a stack overflow exception. :-P

Much as I love the above, the challenge is about doing code golf, and to be fair to respondents, I have to award “best answer” to the shortest code, which is the Befunge entry; I don't believe anybody will be able to beat that (although Konrad has certainly tried), so congrats Patrick!

Seeing the large number of stack-overflow-by-recursion solutions, I'm surprised that nobody has (as of current writing) brought up the Y combinator (see Dick Gabriel's essay, The Why of Y, for a primer). I have a recursive solution that uses the Y combinator, as well as aku's f(f(x)) approach. :-)

((Y (lambda (f) (lambda (x) (f (f x))))) #f)

回答27:

Here's another interesting one from Scheme:

((lambda (x) (x x)) (lambda (x) (x x)))

回答28:

Java

Slightly shorter version of the Java solution.

class X{public static void main(String[]a){main(a);}}

回答29:

xor esp, esp
ret

回答30:

3 bytes:

label:
  pusha
  jmp label

Update

According to the (old?) Intel(?) documentation, this is also 3 bytes:

label:
  call label