views:

17860

answers:

132

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

+107  A: 

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

Chris Jester-Young
mov eax? Did you miss something?
Mladen Jankovic
Yes, it's the stupidest typo I made today. :-P
Chris Jester-Young
Counting the bytes after "compiling" (or assembling) is not code-golf.
lbrandy
The question says "[...] what's the shortest code to cause a stack overflow?" It doesn't specify source code, interpreted code, machine code, object code or managed code...
Anders Sandvig
For the record, Shin's golf server allows you to send object code to be judged, although it will count all your ELF headers too. Hmm....
Chris Jester-Young
See, e.g., http://golf.shinh.org/p.rb?FizzBuzz#x86 for some examples of this. (I honestly don't know how people can make 99-byte ELF binaries, though.) :-P
Chris Jester-Young
@lbrandy: There are enough people who can write object code directly. I can't do it for x86 but for a certain microprocessor I can. I'd count such code.
Joey
A: 

C++:

int overflow(int n)
{
    return overflow(1);
}
Niyaz
A good compiler can tail-call optimise that one! :-P
Chris Jester-Young
+61  A: 

C#:

public int Foo { get { return Foo; } }
aku
I love this answer, well done! Still waiting for more entries before I select a best answer. :-)
Chris Jester-Young
I doubt it will compile...
Daren Thomas
lol, I did this once by accident, but it wasn't as obivous. I blame intellisense.
sieben
oh, it compiles alright, set this one in a juniors lap and watch them debug for a day looking for it, the website project, will just shut down, 503, no warning, no debug, up, down.
DevelopingChris
Thats a good one to mess with the interns
Adam Lerman
Yes, I'll admit to also doing this, once, by accident.
Si
@sieben: Same happened to me. It took me some time to notice this obvious fault XD
Michael Barth
Easy to do accidentally if you do camel case member variable, Pascal case property, as people frequently do in C#. Of course in VB.NET this code couldn't compile.
RichardOD
:::Tests it::: C# debugger made it really obvious where the problem was.
Brian
I started naming private variables _foo years ago because intellisense tends to cause this if your backing private field is just a lower case version of the property. Automatic variables in C# 3 eliminate this drudgery altogether.
Brian Reiter
I'll even admit to doing it more than once. I blame the Illuminati.
Even Mien
+9  A: 

Python:

so=lambda:so();so()

Alternatively:

def so():so()
so()

And if Python optimized tail calls...:

o=lambda:map(o,o());o()
Cody Brocious
Lucky for you, Python doesn't do tail-call optimisation; otherwise, it'd be disqualified like two other answers so far. :-P
Chris Jester-Young
+1  A: 

PIC18:

overflow

    PUSH   
    CALL   overflow
TK
Very nice, similar in spirit to my answer. How many bytes of object code does it create?
Chris Jester-Young
To be honest I'm not really too sure!
TK
A: 
int main(){
    int a = 20;
    return main();
}
Vulcan Eager
Like Niyaz's answer, this can also be tail-call optimised too!
Chris Jester-Young
This is invalid code, according to C++98 3.6.1.3 "The function main shall not be used within a program". </language_nazi>
Motti
A: 

JavaScript:

function i(){ i(); }
i();


C++ Using a function-pointer:

int main(){
   int (*f)() = &main;
   f();
}
Huppie
@danb, I did try that but Rhino didn't want to compile it.
Huppie
new function i(){i()}(); works. still not shorter of course...
asksol
As I commented in the comment to Vulcan Eager's post the C++ version is invalid, according to C++98 3.6.1.3 "The function main shall not be used within a program". </language_nazi>
Motti
@Motti: Shame on Microsoft for compiling it just fine without errors in VS8 ;-)
Huppie
@Huppie - i'd venture to guess that this is a no-diagnostic-required error, much as is stack overflows to begin with. !(code compiling -> code correct).
Aaron
+24  A: 

In english:

recursion = n. See recursion.
Vinko Vrsalovic
Any sensible human brain will tail-call optimise the interpretation of this one too, and not blow up. :-P
Chris Jester-Young
Chris, sensible human brains are becoming a rarity these days.
Jason Z
rarity...you mean they exist?
Adam Lerman
Google recursion
CodeFusionMobile
+1  A: 
/* In C/C++ (second attempt) */

int main(){
    int a = main() + 1;
    return a;
}
Vulcan Eager
Much better! I have my own little contribution coming up, too. :-P
Chris Jester-Young
It seems that this can be optimised too. with gcc -O3, it just runs and runs.
Andrew Johnson
Nice, Andrew; it did get optimised to a jump too!
Chris Jester-Young
haha in C++ you cannot call main nor take its address :p
Johannes Schaub - litb
@litb - you say this like it's a benefit.
Chris Lutz
+16  A: 

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

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

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

Chris Jester-Young
Doesn't compile for me: "undefined reference to `main'" :P
Andrew Johnson
I don't understand: why call o() 2x?
Dinah
@Dinah: One of the constraints of my contest was that tail-call optimisation doesn't count as recursion; it's just an iterative loop. If you only wrote o() once, that can be tail-call optimised into something like this (by a competent compiler): "o: jmp o". With 2 calls of o, the compiler has to use something like: "o: call o; jmp o". It's the recursive "call" instruction that makes the stack overflow.
Chris Jester-Young
You're correct -- I didn't pay attention to that part. Thank you for the clarification.
Dinah
A: 

C#, done in 20 characters (exclusing whitespace):

int s(){
    return s();
}
GateKiller
Isn't this one of a (small) number of circumstances where the .NET JIT compiler can tail-call optimise? :-P
Chris Jester-Young
I have no idea, but it crashed my development web server :)
GateKiller
+2  A: 

CIL/MSIL:

loop: ldc.i4.0
br loop

Object code:

16 2B FD
Cody Brocious
Hmm, will the .NET verifier accept that? For JVM, you have to specify the maximum stack usage, and the verifier will enforce it, so code like the above (iconst_0; goto loop) will get rejected.
Chris Jester-Young
+153  A: 

You could also try this in C#.net

throw new StackOverflowException();
GateKiller
That's not a real stack overflow!! However, I'll upvote you for originality. :-P
Chris Jester-Young
Nope, but it's the quickest way because the program doesn't have to follow the stack to error, it just simply throws an exception. Genius.
GateKiller
Nice, that's the best defence I've heard today. :-P
Chris Jester-Young
It's performance optimization! I like it :)
aku
I'll second the originality.
Jason Z
Tricky...but ok...
Adam Lerman
Nice, you got an up vote
Eric Haskins
The pedant in me says it doesn't cause any stack to overflow, just throws an exception. That's like saying the quickest way to be attacked by sharks is to stand in the sea and scream "Shark attack!". Despite this, I will up-vote it. :)
Bernard
Well - is there a difference? Can you catch it and continue? Or is it exactly like a stackoverflow in c#? In that case, it somehow is a stackoverflow, since it is indistinguishable from one... However - upvote for all the reasons above
Mo
If a stack overflows in the woods with nobody around to catch, does it throw an exception?
James M.
I wouldn't say the 'shortest' since it's not like you can compile a one-liner like that. It _does_ throw a stack overflow quickly though I guess.
DMan
+21  A: 

How about the following in BASIC:

10 GOSUB 10

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

stusmith
good guess - that'll do it!
Ferruccio
Not really a stack overflow since BASIC is a stackless language. Even VB (which does have a stack) wouldn't overflow on this since it's just jumping, not creating a stack frame.
Daniel Spiewak
That's a `GOSUB`, not a `GOTO`. Since it `RETURN`s to where it was called from, surely it's using a stack?
Tom
Yeah, I agree. I had *many* stack overflows in BASIC in the 80s.
nickd
I ran this one in yabasic just for the fun of it, and it nearly took down my computer. Thank god malloc eventually failed, but I was paging like no tomorrow.
Adam Rosenfield
Oops sorry Adam... reminds me of a time at uni when someone accidentally wrote a program that recursively forked: took down an entire Silicon Graphics server.
stusmith
Just tested it on my VZ200 emulator?OUT OF MEMORY ERROR IN 10
johnc
+121  A: 

Nemerle:

This crashes the compiler with a StackOverflowException:

def o(){[o()]}
Cody Brocious
Bonus! Meta stack overflow!
Chris Jester-Young
Definite bonus points for that.
Wedge
+2  A: 

Ruby:

def s() s() end; s()
dr_bonzo
You call yourself a ruby programmer...? You can do better: def s;s;end;s
Mike Stone
+23  A: 

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

Chris Jester-Young
+2  A: 

Lisp

(defun x() (x)) (x)
Ozgur Ozcitak
With some compiler flags, this can also be tail-call optimised. :-)
Chris Jester-Young
In current implementations of Common Lisp, you will have to explicitly declaim or declare TCO away. Scheme even requires TCO. To make this surely overflow, don't tail recurse: (defun x () (1+ (x))) (x).
Svante
+2  A: 
a{return a*a;};

Compile with:

gcc -D"a=main()" so.c

Expands to:

main() {
    return main()*main();
}
Andrew Johnson
Eh, with Perl golf at least, command-line options count towards the character count. :-P
Chris Jester-Young
OK 26 chars, included command-line option, for a completely compilable and runnable program.
Andrew Johnson
Okay, fine, I'll let you have this one, since you wanted a version with main. :-)
Chris Jester-Young
+1  A: 

c# again:

class Foo { public Foo() {new Foo(); } }
aku
Another excellent one, keep up the good work!
Chris Jester-Young
Would changing the class into a struct not use even more stack space since a struct is value type?
VVS
+8  A: 

perl in 12 chars:

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

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

i(){ i;};i
asksol
Yay, Perl golf entry!
Chris Jester-Young
mobrule
+1  A: 

Complete Delphi program.

program Project1;
{$APPTYPE CONSOLE}
uses SysUtils;

begin
  raise EStackOverflow.Create('Stack Overflow');
end.
JosephStyons
Oi, this is only funny once, and GateKiller had that answer already. :-P
Chris Jester-Young
A: 

Clarion:

Poke(0)
Sean Cameron
Is there any publicly available documentation on how Clarion works?
Chris Jester-Young
www.softvelocity.com has a fair amount of information, and the Clarion public newsgroup (comp.lang.clarion) has a wealth of information and an active community (although the newsgroup on news.softvelocity.com is the primary group and doesn't seem to be typically be synchronized with other servers).
Sean Cameron
+3  A: 

Java (embarassing):

public class SO 
{ 
  private void killme()
  {
    killme();
  }

  public static void main(String[] args) 
  { 
    new SO().killme(); 
  } 
}

EDIT Of course it can be considerably shortened:

class SO
{
  public static void main(String[] a)
  {
    main(null);
  }
}
Manrico Corazzi
+1  A: 

so.c in 15 characters:

main(){main();}

Result:

[email protected]:~$ gcc so.c -o so
[email protected]:~$ ./so
Segmentation fault (core dumped)

Edit: Okay, it gives warnings with -Wall and does not cause a stack overflow with -O2. But it works!

Antti Sykäri
Blech! That's undefined, because you have an implicit int return, with no actual return value. If you declared main as void (for some reason), then tail call optimisation can apply. So, nope. :-P
Chris Jester-Young
A: 

I tried to do it in Erlang:

c(N)->c(N+1)+c(N-1).
c(0).

The double invocation of itself makes the memory usage go up O(n^2) rather than O(n).

However the Erlang interpreter doesn't appear to manage to crash.

Alnitak
Does c(N)->c(N+1)+c(N+1) work?
Chris Jester-Young
A: 

JavaSript:

Huppies answer to one line:

(function i(){ i(); })()

Same amount of characters, but no new line :)

Leo Lännenmäki
This is kind of clever, because lack of TCO is a known 'feature' of many JavaScript engines.
TrayMan
A: 

recursion is old hat. here is mutual recursion. kick off by calling either function.

a()
{
    b();
}
b()
{
    a();
}

PS: but you were asking for shortest way.. not most creative way!

kinjal
Which language is this? If it's a dynamic language, then tail-call optimisation can apply; if it's C, and you're relying on implicit int, the lack of a return value is undefined behaviour. Using "return a()" and "return b()" would also be subject to tail call optimisation. :-P
Chris Jester-Young
+1  A: 

Java (complete content of X.java):

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

Considering all the syntactic sugar, I am wondering if any shorter can be done in Java. Anyone?

EDIT: Oops, I missed there is already almost identical solution posted.

EDIT 2: I would say, that this one is (character wise) the shortest possible

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

EDIT 3: Thanks to Anders for pointing out null is not optimal argument, so it's shorter to do:

class X{public static void main(String[]a){main(a);}}
Michal
class X{public static void main(String[]a){main("");}} is shorter... ;)
Anders Sandvig
@Anders: "" instanceof String[] => false
Chris Jester-Young
Nope, I've done shorter - see my answer.
Draemon
A: 

On the cell spus, there are no stack overflows, so theres no need for recursion, we can just wipe the stack pointer.

asm("andi $1, $1, 0" );

+4  A: 
Anders Sandvig
It's 3 bytes in 32-bit mode. Nice answer, considering it'll fill the stack much faster than my answer!
Chris Jester-Young
According to http://www.penguin.cz/~literakl/intel/j.html#JMP, jmp is 3 bytes with 8, 16 or 32 bit relative destination address. The pusha is also 1 bytes, which makes a total of 4
Anders Sandvig
There are three types of jmp, short, near, and far. Short jmp (using 0xEB opcode) is two bytes. Destination must be between -128 and 127 bytes away from the next instruction. :-)
Chris Jester-Young
Maybe you're right. I'm too lazy to dig out my assembler and verify... ;)
Anders Sandvig
A: 

PHP - recursion just for fun. I imagine needing a PHP interpreter takes it out of the running, but hey - it'll make the crash.

function a() { a(); } a();
JWHEAT
+1  A: 

There was a perl one already, but this is a couple characters shorter (9 vs 12) - and it doesn't recurse :)

s//*_=0/e

shelfoo
Nice! That's clever. But it doesn't work in 5.10: $> perl -e's//*_=0/e' perl(30740) malloc: *** error for object 0x301070: double free *** set a breakpoint in malloc_error_break to debug
asksol
Same error here on my Perl 5.8.8. :-(
Chris Jester-Young
+3  A: 

GWBASIC output...

OK
10 i=0
20 print i;
30 i=i+1
40 gosub 20
run
 0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21
 22  23  24  25  26  27  28  29  30  31  32  33
Out of memory in 30
Ok

Not much stack depth there :-)

Tim Ring
A: 
//lang = C++... it's joke, of course
//Pay attention how 
void StackOverflow(){printf("StackOverflow!");}
int main()
{
    StackOverflow(); //called StackOverflow, right?
}
bgee
*rimshot* - He'll be here all week, try the veal.
Bernard
+1  A: 

F#

People keep asking "What is F# useful for?"

let rec f n =
    f (n)

performance optimized version (will fail faster :) )

let rec f n =
    f (f(n))
aku
Doesn't appear to work, fails with 'error FS0030: Value restriction' for me.
kronoz
Use their latest CTP, works for me :) also try f(f(n))
aku
hm, it might have been fixed in the 1.9.6.0 -> 1.9.6.2 release I guess then, will go check it out :-)
kronoz
The first one is tail recursive, the second one will work though
Graphics Noob
+1  A: 

I have a list of these at Infinite Loop on E2 - see just the ones indicated as "Stack Overflow" in the title.

I think the shortest there is

[dx]dx

in dc. There may be a shorter solution in False.

EDIT: Apparently this doesn't work... At least on GNU dc. Maybe it was on a BSD version.

Jesse Millikan
It doesn't work. dc consumes 100% CPU but not stack overflow in dc (GNU bc 1.06.94) 1.3.94 occured. dc -e '[dx+]dx' makes Segmentation fault.
Hynek -Pichi- Vychodil
Hmm... I was sure it worked on some version. It may only be on some BSD version.
Jesse Millikan
A: 

Ruby:

def i()i()end;i()

(17 chars)

+3  A: 

In Lua:

function f()return 1+f()end f()

You've got to do something to the result of the recursive call, or else tail call optimization will allow it to loop forever. Weak for code golf, but nice to have!

I guess that and the lengthy keywords mean Lua won't be winning the code golf anytime soon.

Evan DeMond
Ah. You beat my (unpublished) score. I used f()*f() to avoid the tail call.
Jon Ericson
The f()*f() isn't a bad idea, however: apparently (this isn't about Lua anymore BTW) GCC can tail-call optimise 1+f() too, on the premise that f() isn't expected to return, or something. See the comments on #62221 for more details. :-P
Chris Jester-Young
+3  A: 

batch program called call.cmd;

call call.cmd

******  B A T C H   R E C U R S I O N  exceeds STACK limits ******
Recursion Count=1240, Stack Usage=90 percent
******       B A T C H   PROCESSING IS   A B O R T E D      ******
tomdemuyt
A: 

Perl in 10 chars

sub x{&x}x

Eventually uses up all available memory.

davidnicol
A: 

MS-DOS batch:

copy CON so.bat
so.bat
^Z
so.bat
davidnicol
Wait, you have to say "Call so.bat". Running a batch file without call is like using exec, if I remember right. :-P
Chris Jester-Young
+5  A: 

Java

Slightly shorter version of the Java solution.

class X{public static void main(String[]a){main(a);}}
Misha
Or (same number of characters): public static void main(String...a){main();}
Michael Myers
Or for the TDD guys (same number of chars): public class ${@org.junit.Test public void $(){$();}}
mhaller
Still not the shortest though (see my answer)
Draemon
+3  A: 

In Scheme, this will cause the interpreter to run out of memory:

(define (x)
  ((x)))

(x)
Kyle Cronin
+1  A: 

Shell script solution in 10 characters including newlines:

Well, technically not stack overflow but logically so, if you consider spawning a new process as constructing a new stack frame.

#!sh
./so

Result:

[email protected]:~$ ./so
[disconnected]

Whoops. Note: don't try this at home

Antti Sykäri
+2  A: 

In Whitespace, I think:

It probably won't show up. :/

Robert S.
Browsers won't show tabs very well to begin with, and Markdown just completely obliterates it. I'll paste in what I can see (editing privileges for the win!) in my next comment.
Chris Jester-Young
SP SP SP TAB NL NLSP SP SP TAB SP SP SP SP TAB TAB NLTAB SP SP SP NLSP TAB SP TAB SP SP SP SP TAB TAB NL NL NL
Chris Jester-Young
+8  A: 

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;
}
bk1e
You can also just do "ulimit -s16" to set the stack really small. Any smaller than about 16 and the program doesn't even run (insufficient args apparently!).
Andrew Johnson
A portable stack overflow... awesome!
alex
A: 

C# with 27 non-whitespace characters - includes the call.

Action a = null;
a = () => a();
a();
David B
+6  A: 
xor esp, esp
ret
that's not really a stack overflow, but it's nice eitherwy :D
botismarius
Stack underflow for the win!
Chris Jester-Young
+1  A: 

PowerShell

$f={&$f};&$f

"The script failed due to call depth overflow. The call depth reached 1001 and the maximum is 1000."

x0n
i like it! Depth overflow!
RCIX
+227  A: 

Read this line, and do what it says twice.

jrudolph
Raymond Smullyan?
Konrad Rudolph
Argh! I have to sleep! HALP! :-(
Bernard
I'm getting "Gödel, Escher, Bach"-vibes.
JesperE
Dude. You just crashed my ...
Dan Esparza
lather, rinse, repeat
Mikeage
I pronounce you GOD Over Djinn
Brehtt
Can I wish for five more wishes so I can get out of this loop?
Nosredna
recursion: see recursion
Mark
Or just "repeat".
Alex Feinman
It's quite fortunate that I'm total. Sure, I am not able to compute every computable function, but my termination checker complained, so I did not have a SO.
fishlips
Where was I? Am I still in same place?
THEn
BRAIN OVERFLOW occurs
Bragboy
Done. -- Regards, Chuck.
takeshin
A: 

bash: Only one process

\#!/bin/bash
of() { of; }
of
+3  A: 

Ruby, shorter than the other ones so far:

def a;a;end;a

(13 chars)

A: 

Pretty much any shell:

sh $0

(5 characters, only works if run from file)

sh $0 # system crash (stop it with kill -9 -1 in another shell as the same user)
BCS
+7  A: 

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

ahha...nice one.
public static
Here in New Zealand we have Burger Wisconsin, where they use big but thin patties. I'm sure you can stack more than 4 of those if you want to; it'll be a very expensive burger though!
Chris Jester-Young
Maybe: http://www.alafista.com/2010/05/10/lotteria-tower-cheese-burger-with-10-patties/ Maybe not: http://cheaplightning.blogspot.com/2010/06/lotteria-10-patty-burger-bloody-history.html
BCS
Mmm... In-n-Out. http://en.wikipedia.org/wiki/In-n-out#Menu
banzaimonkey
+12  A: 

Groovy:

main()

$ groovy stack.groovy:

Caught: java.lang.StackOverflowError
    at stack.main(stack.groovy)
    at stack.run(stack.groovy:1)
 ...
broady
Voted up because it's pretty interesting. Exposes a rather annoying weakness in the Groovy compiler though (such tail-calls can be inlined at compile-time).
Daniel Spiewak
are you sure it's a tail call? that falling off the end of the program doesn't invoke the interpreter shell?
Aaron
A: 

Five bytes in 16-bit asm which will cause a stack overflow.

push cs
push $-1
ret
Jonas Gulle
+1  A: 

In assembly language (x86 processors, 16 or 32 bit mode):


call $

which will generate:

  • in 32 bit mode: 0xe8;0xfb;0xff;0xff;0xff

  • in 16 bit mode: 0xe8;0xfd;0xff

in C/C++:


int main( ) {
  return main( );
}
botismarius
+29  A: 

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.

Dennis Munsie
Aaaahh bless, a Z80...
Tim Ring
+1 because I actually *did* that once… >.<
Ben Blank
I remember a blank eprom would be all 0xffs which are rst 7 (= call 0x0038) instructions. That would be useful for debugging your hardware with an oscilloscope. The address bus would cycle through the 64K space as the stack overflowed repeatedly, interspersed with reads of 0xff from 0x0038.
Bill Forster
+11  A: 

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)');
Travis Wilson
Hehehe, very neat! Mmmm, eval....
Chris Jester-Young
+2  A: 

Haskell:

let x = x
print x
mattiast
That's not a stack overflow. `let f x = f x >> x in f $ return()`
jleedev
+2  A: 

Well, nobody's mentioned Coldfusion yet, so...

<cfinclude template="#ListLast(CGI.SCRIPT_NAME, "/\")#">

That oughta do it.

Joshua Carmody
A: 

VB.Net

Function StackOverflow() As Integer
    Return StackOverflow()
End Function
Kibbee
Under certain conditions, I'm given to understand that the .NET JIT compiler can tail-call optimise that one!
Chris Jester-Young
+1  A: 

TCL:

proc a {} a

I don't have a tclsh interpreter that can do tail recursion, but this might fool such a thing:

proc a {} "a;a"
Joseph Bui
+3  A: 

Forth:

: a 1 recurse ; a

Inside the gforth interpreter:

: a 1 recurse ; a 
*the terminal*:1: Return stack overflow
: a 1 recurse ; a
                ^
Backtrace:

On a Power Mac G4 at the Open Firmware prompt, this just hangs the machine. :)

Pi
A: 

Oops, I dunno, I haver never written code that causes a Stack Overflow ;)

+25  A: 

Another PHP Example:

<?
require(__FILE__);
disq
You could even be shorted by skipping the parenthesis (but including space in place of the first).
alex
A: 

For Fun I had to look up the Motorolla HC11 Assembly:

              org           $100
Loop    nop
          jsr            Loop
PersistenceOfVision
Hmm, does the HC11 not allow you to jsr straight away? Why is the nop necessary?
Chris Jester-Young
Your right. I was simply being lazy ;-) Existed too long in the higher level languages. Time to get back to the low low level stuff.
PersistenceOfVision
A: 

Prolog

p:-p.

= 5 characters

then start it and query p

i think that is quite small and runs out of stack in prolog.

a query of just a variable in swi prolog produces:

?- X. % ... 1,000,000 ............ 10,000,000 years later % % >> 42 << (last release gives the question)

and here is another bash fork bomb: :(){ :|:& };:

WaldWolf
It doesn't run out of stack, at least in SWI-Prolog. It's tail recursion. What does run out of stack is: "assert(p :- (p, q)), assert(q). p."
Kaarel
+2  A: 

as a local variable in a C function:

int x[100000000000];
Hex Encode the number to shorten this...
st0le
A: 

Not very short, but effective! (JavaScript)

setTimeout(1, function() {while(1) a=1;});
Thevs
+3  A: 

C#

class _{static void Main(){Main();}}

Note that mine is a compilable program, not just a single function. I also removed excess whitespace.

For flair, I made the class name as small as I could.

Jay Bazuzi
You could even rename Main if you were willing to require a special command-line option to the compiler.
Joe White
+186  A: 

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

Patrick
Wow. Very impressive. You might just win the prize this time. :-P
Chris Jester-Young
And it hangs Firefox to boot. Nice :)
owenmarshall
Hmm … but is this really a stack overflow or just an infinite loop? My JS interpreter did *not* overflow, it just went on vacation, so to speak.
Konrad Rudolph
It's not an infinite loop, because the 1 instruction pushes a 1 onto the stack. Eventually, your Befunge interpreter will run out of stack space, but it'll take a while. :)
Patrick
definitely the best one
Jean
Safari does fine :)
Teifion
You.. crashed my browser and.. sent my CPU fan into overdrive.
Sam152
Good link, thanks.
Liran Orevi
Safari asked me if I wanted to stop the script :).
Mk12
Amazing! My computer or browser (Opera) didn't crash but both processors were running on 100% and the fan speed was at 3.
Secko
Here's a Befunge program that overflows faster: `"` It loads 79 copies of the number 32 every two times it wraps around, rather than 2 copies of the number 1.
KirarinSnow
+2  A: 

Unless there's a language where the empty program causes a stack overflow, the following should be the shortest possible.

Befunge:

:

Duplicates the top stack value over and over again.

edit: Patrick's is better. Filling the stack with 1s is better than filling the stack with 0s, since the interpreter could optimize pushing 0s onto an empty stack as a no-op.

clahey
A: 

I think it's cheating I've never played before ;) but here goes

8086 assembler:

org Int3VectorAdrress ;is that cheating?

int 3

1 byte - or 5 characters that generate code, what say you?

Despatcher
Hahaha, nice try. I think to get away with this, you'd have to set the int 3 vector address to something suitable first, and that'd cost you some code bytes too. :-P
Chris Jester-Young
+3  A: 

If you consider a call frame to be a process, and the stack to be your Unix machine, you could consider a fork bomb to be a parallel program to create a stack overflow condition. Try this 13-character bash number. No saving to a file is necessary.

:(){ :|:& };:
Sure that's not a bunch of emoticons? ;)
RCIX
A: 

Ruby, albeit not that short:

class Overflow
    def initialize
     Overflow.new
    end
end

Overflow.new
RFelix
+35  A: 

TeX:

\def\a{\a.}\a

Results in:

! TeX capacity exceeded, sorry [input stack size=5000].
\a ->\a
        .
\a ->\a
        .
\a ->\a
        .
\a ->\a
        .
\a ->\a
        .
\a ->\a
        .
...
 \a

Pi
A: 

I think this will work in Java (untried):

enum A{B.values()}
enum B{A.values()}

Should overflow in static initialization before it even gets the chance to fail due to a lack of main(String[]).

Daniel Spiewak
does not compile
finnw
+1  A: 

won't be the shortest but I had to try something... C#

string[] f = new string[0]; Main(f);

bit shorter

static void Main(){Main();}
+10  A: 
Person JeffAtwood;
Person JoelSpolsky;
JeffAtwood.TalkTo(JoelSpolsky);

Here's hoping for no tail recursion!

Ryan Fox
Hehe, funny. Related to conversations, the idea of the "echo chamber effect" is quite interesting, too. Not quite stack overflow-inducing, but still.
Chris Jester-Young
Wouldn't this be a null pointer exception? Sorry, I know it's a joke.
jamesh
+13  A: 

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

call s
Blinky
A: 

In C#, this would create a stackoverflow...

static void Main()
{
    Main();
}
A: 

why not

mov sp,0

(stack grows down)

mike511
A: 

In a PostScript file called so.ps will cause execstackoverflow

%!PS
/increase {1 add} def
1 increase
(so.ps) run
Mark Nold
I think you meant to say this instead: /recurse {1 recurse} def recurse
Chris Jester-Young
+3  A: 

In Irssi (terminal based IRC client, not "really" a programming language), $L means the current command line. So you can cause a stack overflow ("hit maximum recursion limit") with:

/eval $L
Wouter Coekaerts
+38  A: 

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

so
Konrad Rudolph
Did you just invent this language just for the purpose of this question? :-P
Chris Jester-Young
Yea … unfortunately, I wrote it (well, the HTML page took longer than the “interpreter”) before seeing the Befunge solution. Can't beat that. ;-)
Konrad Rudolph
But, in my defense, even the language's name produces a stack overflow. Oh well.
Konrad Rudolph
The recursive acronym in your language's name hasn't escaped my notice; I appreciated that. :-)
Chris Jester-Young
If you're making a specialized language for generating overflows with a minimal of code, obviously you would want (1) empty input produces stack overflowing code (probably a small binary that runs the native code generated from the assembly code entry) or (2) all input programs produce said binary.
Jared Updike
Hmmm, not Turing complete. I don't know if you could call it a language just yet...
Adam Davis
The Jon Skeet answer cannot exist twice...
furtelwart
guerda: Please explain.
Konrad Rudolph
+1 for effort\originality. I like it!
Stuart Branham
+1, although I hesitated when I discovered the language is case-insensitive.
avakar
I got a job once at a place where I'm sure this was what powered their server backend.
Rich Bradshaw
+1  A: 

Here's another Ruby answer, this one uses lambdas:

(a=lambda{a.call}).call
RFelix
I like this one! :D
The Wicked Flea
Took only a split second to get "... 22730 levels..." in the "stack level too deep" error I get.
The Wicked Flea
+5  A: 

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)
Chris Jester-Young
+1  A: 

Another one in JavaScript:

(function() { arguments.callee() })()
Leo Lännenmäki
Nice, I like this one because, like my Y combinator version, it doesn't require you to give a name to the function. Good stuff!
Chris Jester-Young
`(function(){arguments.callee()})()`
eyelidlessness
function x(){x()}x() -> 20; function x()x();x() -> 19, only works in Firefox; Nice try tough ;P (jk)
Vincent
+1  A: 

Vb6


Public Property Let x(ByVal y As Long)
  x = y
End Property

Private Sub Class_Initialize()
  x = 0
End Sub
Javier
Nice. Similar theme to one of aku's solutions (except there it was a property getter, and here it's a property setter). +1!
Chris Jester-Young
ewwwwwwwwwwwwww
Charlie Somerville
+1  A: 

Short solution in K&R C, could be compiled:

main(){main()}

14 bytes

squadette
+6  A: 

Here's another interesting one from Scheme:

((lambda (x) (x x)) (lambda (x) (x x)))
Adam Rosenfield
Very nice, and there's a good symmetry to it too. Also, to use the (lambda (x) (x x)) formulation: ((Y (lambda (x) (x x))) #f) is a lot of fun too!
Chris Jester-Young
Oh, that's pretty. It works in Ruby, too, although not as pretty as in Scheme: lambda { |x| x.call x }.call lambda { |x| x.call x }
Wayne Conrad
+1  A: 

http://www.google.com/search?q=google.com

Ramin
A: 

Actionscript 3: All done with arrays...

var i=[];
i[i.push(i)]=i;
trace(i);

Maybe not the smallest but I think it's cute. Especially the push method returning the new array length!

defmeta
If you replace `trace(i);` with `console.log(i);` it's also valid JavaScript code in Chrome or Firefox with Firebug.
Na7coldwater
+1  A: 

In response to the Y combinator comment, i might as well through in the Y-combinator in the SKI calculus:

S (K (S I I)) (S (S (K S) K) (K (S I I)))

There aren't any SKI interpreters that i know of but i once wrote a graphical one in about an hour in actionscript. I would be willing to post if there is interest (though i never got the layout working very efficiently)

read all about it here: http://en.wikipedia.org/wiki/SKI_combinator_calculus

A: 

In x86 assembly, place a divide by 0 instruction at the location in memory of the interrupt handler for divide by 0!

I believe [this submission](#67749) uses the same concepts, but nice try anyway. :-)
Chris Jester-Young
+2  A: 

Groovy (5B):

run()
matyr
A: 

in perl:

`$0`

As a matter of fact, this will work with any shell that supports the backquote-command syntax and stores its own name in $0

dsm
Or, perhaps, "do $0"? *goes and tries*
Chris Jester-Young
I was going to leave your answer be, however, you've edited it enough times that I should speak. :-P What some posters have mentioned is that this is more a process-table overflow, than a stack overflow as such. Some people have posted fork bombs in this thread too, which may interest you. :-)
Chris Jester-Young
+1  A: 

False:

[1][1]#

(False is a stack language: # is a while loop that takes 2 closures, a conditional and a body. The body is the one that causes the overflow).

Aardappel
+1  A: 

CMD overflow in one line

echo @call b.cmd > b.cmd & b
A: 

Prolog

This program crashes both SWI-Prolog and Sicstus Prolog when consulted.

p :- p, q.
:- p.
Kaarel
A: 
Redmond.Microsoft.Core.Windows.Start()
Oscar Cabrero
+84  A: 

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.

Adam Davis
Very nice. :-) I can't accept two answers, so I've just +1'd your answer, and hope everyone else does the same and bump it up. :-P
Chris Jester-Young
Ah, I figured that the smallest and fastest might beat out the the smallest, but such is life. Thanks anyway!
Adam Davis
Sweet. I started out on Z-80 assembler, and it's nice to know there's still low-level awesomeness in the world!
Mark Harrison
@Adam: Indeed, I prefer smallest and fastest...gun in the west. :-P (I just realised that I hadn't responded to your comment for over a year, so I had to say something cheeky. :-P)
Chris Jester-Young
@Chris - lol! ` `
Adam Davis
A: 

Tail call optimization can be sabotaged by not tail calling. In Common Lisp:

(defun f () (1+ (f)))
Svante
+1  A: 

In Haskell

fix (1+)

This tries to find the fix point of the (1+) function (λ n → n + 1) . The implementation of fix is

fix f = (let x = f(x) in x)

So

fix (1+)

becomes

(1+) ((1+) ((1+) ...))

Note that

fix (+1)

just loops.

Jonas Kölker
A: 

Meta problem in D:

class C(int i) { C!(i+1) c; }
C!(1) c;

compile time stack overflow

BCS
A: 
_asm t: call t;
Tolgahan Albayrak
+1  A: 

A better lua solution:

function c()c()end;

Stick this into SciTE or an interactive command prompt and then call it. Boom!

RCIX
+9  A: 

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

Greg
Or Eine (Eine is not Emacs), or Zwei (Zwei was Eine initially). :-P
Chris Jester-Young
Or YAML, or WINE, or XNA, or any of the rest at http://en.wikipedia.org/wiki/Recursive_acronym
TM
Drei (Drei is Really Emacs Incognito), Fier (Fier is Emacs Reinvented) - ok so I just made those up :-)
Ferruccio
A: 

OCaml

let rec f l = f [email protected];;

This one is a little different. There's only one stack frame on the stack (since it's tail recursive), but it's input keeps growing until it overflows the stack. Just call f with a non empty list like so (at the interpreter prompt):

# f [0];;
Stack overflow during evaluation (looping recursion?).
Graphics Noob
A: 

Even though it doesn't really have a stack...

brainf*ck 5 char

+[>+]
Graphics Noob
A: 

Z80 assembly language...

.org 1000
loop: call loop

this generates 3 bytes of code at location 1000....

1000 CD 00 10

Tim Ring
+2  A: 

C#

class Program
{
    class StackOverflowExceptionOverflow : System.Exception
    {
        public StackOverflowExceptionOverflow()
        {
            throw new StackOverflowExceptionOverflow();
        }
    }

    static void Main(string[] args)
    {
        throw new StackOverflowExceptionOverflow();
    }
}

I realize this is not the shortest (and even code golfed it would not come close to be anywhere near short), but I simply could not resist throwing an exception that while being thrown throws a stackoverflowexception, before it is able to terminate the runtime itself ^^

dionadar
A: 

ruby (again):

def a(x);x.gsub(/./){a$0};end;a"x"

There are plenty of ruby solutions already but I thought I'd throw in a regexp for good measure.

finnw
+2  A: 

PostScript, 7 characters

{/}loop

When run in GhostScript, throws this exception:

GS>{/}loop
Error: /stackoverflow in --execute--
Operand stack:
   --nostringval--
Execution stack:
   %interp_exit   .runexec2   --nostringval--   --nostringval--   --nostringval--   2   %stopped_push   --nostringval--   --nostringval--   %loop_continue   1753   2   3   %oparray_pop   --nostringval--   --nostringval--   false   1   %stopped_push   .runexec2   --nostringval--   --nostringval--   --nostringval--   2   %stopped_push   --nostringval--   --nostringval--   %loop_continue
Dictionary stack:
   --dict:1150/1684(ro)(G)--   --dict:0/20(G)--   --dict:70/200(L)--
Current allocation mode is local
Last OS error: 11
Current file position is 8

Here's the recursive version without using variables (51 chars):

[{/[aload 8 1 roll]cvx exec}aload 8 1 roll]cvx exec
KirarinSnow
A: 

Another Windows Batch file:

:a
@call :a
Carlos Gutiérrez
A: 
main(){
   main();
}

Plain and nice C. Feels quite Intuitive to me.

N 1.1
A: 

GNU make:

Create a file called "Makefile" with the following contents:

a:
    make

Then run make:

$ make

Note that a tab character must be used to offset the word "make". This file is 9 characters, including the 2 end-of-line characters and the 1 tab character.

I suppose you could do a similar thing with bash, but it's probably too easy to be interesting:

Create a filename "b" and mark it as executable (chmod +x b):

b ## ties the winning entry with only one character (does not require end-of-line)

Now execute the file with

$ ( PATH=$PATH:. ; b )

It's hard to say whether this approach technically results in stack overflow, but it does build a stack which will grow until the machine runs out of resources. The cool thing about doing it with GNU make is that you can watch it output status information as it builds and destroys the stack (assuming you hit ^C at some point before the crash occurs).

nobar
+1  A: 

Java:

class X{static{new X();}{new X();}}

Actually causes a stack overflow initializing the X class. Before main() is called, the JVM must load the class, and when it does so it triggers any anonymous static code blocks:

static {
  new X();
}

Which as you can see, instantiates X using the default constructor. The JVM will call anonymous code blocks even before the constructor:

{
  new X();
}

Which is the recursive part.

Draemon
+4  A: 

Fortran, 13 and 20 chars

real n(0)
n(1)=0
end

or

call main
end

The second case is compiler-dependent; for GNU Fortran, it will need to be compiled with -fno-underscoring.

(Both counts include required newlines)

FX
+29  A: 

Hoot overflow!

//              v___v
let rec f o = f(o);(o)
//             ['---']
//             -"---"-
Juliet
+1 for the lulz
eyelidlessness
A: 

Haskell:

main = print $ x 1 where x y = x y + 1
jkramer
A: 

Dyalog APL

fib←{
    ⍵∊0 1:⍵
    +/∇¨⍵-1 2
}
wash
A: 
int main(void) { return main(); }
Daniel Băluţă
Fail, your answer can be tail-call optimised. :-P (Compiler turns that effectively into `goto _main`, where `_main` is the global symbol corresponding to your main function.)
Chris Jester-Young
A: 

PHP is a recursive acronym

Cyclone
A: 

Python:

import sys  
sys.setrecursionlimit(sys.maxint)  
def so():  
    so()  
so()
Artur Gaspar
why sys.maxint, just set it to 1, crash it quicker...and save chars.
st0le
If i setrecursionlimit(1), it will raise a RuntimeError, not crash.
Artur Gaspar
+1  A: 

Java: 35 characters

I think it's too late, but I will still post my idea:

class A{{new A();}static{new A();}}

Using the static initializer and instance initializer features.

Here is the output on my computer (notice it showed two error messages):

Exception in thread "main" java.lang.StackOverflowError
    at A.<init>(A.java:1)
        ......
    at A.<init>(A.java:1)
Could not find the main class: A. Program will exit.

See also: http://download.oracle.com/docs/cd/E17409_01/javase/tutorial/java/javaOO/initial.html

SHiNKiROU
Although your answer is still longer than the winning answer :-), it's still a pretty neat approach, so +1 to you!
Chris Jester-Young
At last, I realized someone else did it first. It's on about the middle pages where it's very hard to find.
SHiNKiROU
+1  A: 

.

THEn
What language is that? GolfScript? :-)
Chris Jester-Young
A: 

JavaScript (17 Bytes)

eval(t="eval(t)")

VB Script (25 Bytes)

t="Execute(t)":Execute(t)
st0le
A: 

Ruby (1.9.2) — 13

Two shortest (as far as i know) ways:

def f;f end;f # simple function
(a=->{a[]})[] # anonymous function (lambda) syntax
Nakilon
As stated in the rules, functions (like your `f`) that use only tail calls don't count as recursion.
Chris Jester-Young
+1  A: 

C++ Compiler Error Message

template<int n>struct f{f<n+1>a;};f<0>::a;

output:

$ g++ test.cpp;
test.cpp:1: error: template instantiation depth exceeds maximum of 500 (use -ftemplate-depth-NN to increase the maximum) instantiating ‘struct f<500>’
test.cpp:1:   instantiated from ‘f<499>’
test.cpp:1:   instantiated from ‘f<498>’
......

Even if the compiler went through the template, there will be the next error: missing main.

SHiNKiROU