What's the shortest code to cause a stack overflow? [closed]

Question

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! :-)

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

Answer 2

Read this line, and do what it says twice.

Answer 3

You could also try this in C#.net

throw new StackOverflowException();

Answer 4

Nemerle:

This crashes the compiler with a StackOverflowException:

def o(){[o()]}

Answer 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).

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

Answer 7

C#:

public int Foo { get { return Foo; } }

Answer 8

Hoot overflow!

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

Answer 9

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

so

Answer 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

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

Answer 12

In english:

recursion = n. See recursion.

Answer 13

Another PHP Example:

<?
require(__FILE__);

Answer 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).

Answer 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

Answer 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

Answer 17

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

call s

Answer 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)');

Answer 19

Groovy:

main()

$ groovy stack.groovy:

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

Answer 20

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

Answer 21

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

Here's hoping for no tail recursion!

Answer 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;
}

Answer 23

perl in 12 chars:

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

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

i(){ i;};i

Answer 24

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

Answer 25

Python:

so=lambda:so();so()

Alternatively:

def so():so()
so()

And if Python optimized tail calls...:

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

Answer 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)

Answer 27

Here's another interesting one from Scheme:

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

Answer 28

Java

Slightly shorter version of the Java solution.

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

Answer 29

xor esp, esp
ret

Answer 30

3 bytes:

label:
  pusha
  jmp label

Update

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

label:
  call label