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

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

Read this line, and do what it says twice.

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.

You could also try this in C#.net

throw new StackOverflowException();

Nemerle:

This crashes the compiler with a StackOverflowException:

def o(){[o()]}

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

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

C#:

public int Foo { get { return Foo; } }

Hoot overflow!

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

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

so

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

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.

In english:

recursion = n. See recursion.

Another PHP Example:

<?
require(__FILE__);

How about the following in BASIC:

10 GOSUB 10

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

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

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

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

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

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

call s

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

Groovy:

main()

$ groovy stack.groovy:

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

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

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

Here's hoping for no tail recursion!

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

Python:

so=lambda:so();so()

Alternatively:

def so():so()
so()

And if Python optimized tail calls...:

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

perl in 12 chars:

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

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

i(){ i;};i

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

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)

Here's another interesting one from Scheme:

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

Java

Slightly shorter version of the Java solution.

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

xor esp, esp
ret

3 bytes:

label:
pusha
jmp label

Update

According to http://www.penguin.cz/~literakl/intel/c.html#CALL">the (old?) Intel(?) documentation, this is also 3 bytes:

label:
call label

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

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.

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

as a local variable in a C function:

int x[100000000000];

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

Ruby:

def s() s() end; s()

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

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      ******

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

(define (x)
  ((x)))

(x)

Ruby, shorter than the other ones so far:

def a;a;end;a

(13 chars)

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.

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.

:(){ :|:& };:

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

PIC18:

> overflow >> PUSH
>> CALL overflow

CIL/MSIL:

loop: ldc.i4.0
br loop

Object code:

16 2B FD

Lisp

(defun x() (x)) (x)

a{return a*a;};

Compile with:

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

Expands to:

main() {
    return main()*main();
}

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

In Whitespace, I think:

It probably won't show up. :/

Haskell:

let x = x
print x

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

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

That oughta do it.

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.

Groovy (5B):

run()

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 ^^

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

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.

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

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.

/* In C/C++ (second attempt) */

int main(){
    int a = main() + 1;
    return a;
}

c# again:

class Foo { public Foo() {new Foo(); } }

Complete Delphi program.

program Project1;
{$APPTYPE CONSOLE}
uses SysUtils;

begin
  raise EStackOverflow.Create('Stack Overflow');
end.

so.c in 15 characters:

main(){main();}

Result:

antti@blah:~$ gcc so.c -o so
antti@blah:~$ ./so
Segmentation fault (core dumped)

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

JavaSript:

Huppies answer to one line:

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

Same amount of characters, but no new line :)

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

There was a perl one already, but this is a couple characters shorter (9 vs 12) - and it doesn't recurse :) >s//*_=0/e

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.

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:

antti@blah:~$ ./so
[disconnected]

Whoops. Note: don't try this at home

PowerShell

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

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

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( );
}

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"

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();}

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

(a=lambda{a.call}).call

Another one in JavaScript:

(function() { arguments.callee() })()

Vb6

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




Private Sub Class_Initialize()
x = 0
End Sub
Private Sub Class_Initialize()
x = 0
End Sub

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

main(){main()}

14 bytes

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

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

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

CMD overflow in one line

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

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.

A better lua solution:

function c()c()end;

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

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

http://en.wikipedia.org/wiki/Php">PHP</a> is a recursive acronym

.

C++:

int overflow(int n)
{
    return overflow(1);
}

int main(){
    int a = 20;
    return main();
}

JavaScript:

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

---

C++ Using a function-pointer:

int main(){
   int (*f)() = &main;
   f();
}

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

int s(){
    return s();
}

Clarion:

Poke(0)

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.

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!

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" );

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();

//lang = C++... it's joke, of course
//Pay attention how 
void StackOverflow(){printf("StackOverflow!");}
int main()
{
    StackOverflow(); //called StackOverflow, right?
}

Perl in 10 chars

sub x{&x}x

Eventually uses up all available memory.

MS-DOS batch:

copy CON so.bat
so.bat
^Z
so.bat

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

Action a = null;
a = () => a();
a();

bash: Only one process

\#!/bin/bash
of() { of; }
of

Pretty much any shell:

sh $0

(5 characters, only works if run from file)

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

push cs
push $-1
ret