Lua

function b()b()end b() --stack overflow

Alternatively,

a={}setmetatable(a,{__index=function()return a.a end})a(a.a) --C stack overflow

Java(123 chars)

public class Overflow {
    static int[][][][][] a = new int[99][99][99][99][99];
    public static void main(String[] args) {}
}

This could probably be trimmed down quite a bit, but I prefer a buffer of ruination.

Technically, this won't SO everybody, but most people don't give the JVM 35GB of RAM.

VBScript, 101 characters

Not the smallest script, but created as a proof of concept

i=2
s="sub[2](b):i=i+1:d=replace(b,i-1,i):execute d:call getref("""&i&""")(d):end sub"
execute s
[2]s

This code creates new named functions on the fly by executing a string that creates a function and giving the new function this string as a parameter. The function creates a new function and calls it. Results in a Microsoft VBScript runtime error: Out of stack space: 'execute' error.

A bunch in the same style:

Python, 30

(lambda x:x(x))(lambda y:y(y))

Javascript, 38

(function(x){x(x)})(function(y){y(y)})

Lua, 44

(function(x) x(x) end)(function(y) y(y) end)

C#: 66 (full program)

(full program, not excerpt like other one, although it's based on it)

class A{static int a{get{return a;}} static void Main(){var x=a;}}

Tcl, 15 chars

interp r {} 1;a

gives

too many nested evaluations (infinite loop?)

the interp r stands for interp recursionlimit (you can abbreviate subcommands). a calls (because not known) unknown, which calls a lot of other stuff.

C#: 106 86 58 46 32

32: Getters can SO your machine easy in C#:

public string a {get{return a;}}

Q/k (16 chars)

Not sure if this is in the spirit of the challenge but I don't think it breaks the rules:

s:{f`};f:{s`};f`

Python, real stack overflow: 38

a=[];eval("[x "+"for x in a "*800+"]")

Error message:

s_push: parser stack overflow
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError

Explanation:

[x for x in a for x in a]

is the same as

y = []
for x in a:
    for x in a:
        y.append(x)

so the above eval produces 800 nested for loops :)

Javascript 24 characters

Browser dependent answer (must have access to apply):

eval.apply(0,Array(999999))

• eval was the shortest global function name that I could find (anyone know of one that is shorter?)
• apply allows us to convert an array into function parameters, the first parameter being the context of the function (this)
• Array(999999) will create an array with the listed length. Not sure what the maximum number of arguments is, but it's less than this, and more than 99999

IE9:

SCRIPT28: Out of stack space 
SCRIPT2343: Stack overflow at line: 20 

Chrome 24:

Uncaught RangeError: Maximum call stack size exceeded 

FireFox 18

RangeError: arguments array passed to Function.prototype.apply is too large

Note — Due to the single threaded nature of javascript, infinite loops end up locking the UI and never throwing an exception.

while(1);
for(;;);

Neither of these qualify.

Update — this shaves off three characters:

eval.apply(0,Array(1e7))

Groovy (27 chars)

a=[:];b=[a:a];a.b=b;print b

And so it goes:

Caught: java.lang.StackOverflowError
    java.lang.StackOverflowError

Python (15 chars)

def f():f()
f()

RuntimeError: maximum recursion depth exceeded

Java - 35

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

Haskell (GHC, no optimization), 25

main=print$sum[1..999999]

sum is lazy in the total. This piles up a bunch of thunks, then tries to evaluate them all at the end, resulting in a stack overflow.

PHP 5.4, 33 characters

for($n=1e5;$n--;)$a=(object)[$a];

This causes a stack overflow when the nested stdClass objects are automatically destroyed:

$ gdb -q php
Reading symbols from /usr/bin/php...(no debugging symbols found)...done.
(gdb) set pagination 0
(gdb) r -nr 'for($n=1e5;$n--;)$a=(object)[$a];'
Starting program: /usr/bin/php -nr 'for($n=1e5;$n--;)$a=(object)[$a];'
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x00000000006debce in zend_objects_store_del_ref_by_handle_ex ()
(gdb) bt
#0  0x00000000006debce in zend_objects_store_del_ref_by_handle_ex ()
#1  0x00000000006dee73 in zend_objects_store_del_ref ()
#2  0x00000000006a91ca in _zval_ptr_dtor ()
#3  0x00000000006c5f78 in zend_hash_destroy ()
#4  0x00000000006d909c in zend_object_std_dtor ()
#5  0x00000000006d9129 in zend_objects_free_object_storage ()
#6  0x00000000006dee53 in zend_objects_store_del_ref_by_handle_ex ()
#7  0x00000000006dee73 in zend_objects_store_del_ref ()
#8  0x00000000006a91ca in _zval_ptr_dtor ()
#9  0x00000000006c5f78 in zend_hash_destroy ()
#10 0x00000000006d909c in zend_object_std_dtor ()
#11 0x00000000006d9129 in zend_objects_free_object_storage ()
[...]
#125694 0x00000000006dee53 in zend_objects_store_del_ref_by_handle_ex ()
#125695 0x00000000006dee73 in zend_objects_store_del_ref ()
#125696 0x00000000006a91ca in _zval_ptr_dtor ()
#125697 0x00000000006c5f78 in zend_hash_destroy ()
#125698 0x00000000006d909c in zend_object_std_dtor ()
#125699 0x00000000006d9129 in zend_objects_free_object_storage ()
#125700 0x00000000006dee53 in zend_objects_store_del_ref_by_handle_ex ()
#125701 0x00000000006dee73 in zend_objects_store_del_ref ()
#125702 0x00000000006a91ca in _zval_ptr_dtor ()
#125703 0x00000000006c4945 in ?? ()
#125704 0x00000000006c6481 in zend_hash_reverse_apply ()
#125705 0x00000000006a94e1 in ?? ()
#125706 0x00000000006b80e7 in ?? ()
#125707 0x0000000000657ae5 in php_request_shutdown ()
#125708 0x0000000000761a18 in ?? ()
#125709 0x000000000042c420 in ?? ()
#125710 0x00007ffff5b6976d in __libc_start_main (main=0x42bf50, argc=3, ubp_av=0x7fffffffe738, init=<optimized out>, fini=<optimized out>, rtld_fini=<optimized out>, stack_end=0x7fffffffe728) at libc-start.c:226
#125711 0x000000000042c4b5 in _start ()

//Java's answer...

public class Test
{
    private Test test = new Test();

    public static void main(String[] args)
    {
        new Test();
    }
}

Postscript, 7

{1}loop

Eg.

$ gsnd
GPL Ghostscript 9.06 (2012-08-08)
Copyright (C) 2012 Artifex Software, Inc.  All rights reserved.
This software comes with NO WARRANTY: see the file PUBLIC for details.
GS>{1}loop
Error: /stackoverflow in 1
Operand stack:
   --nostringval--
Execution stack:
   %interp_exit   .runexec2   --nostringval--   --nostringval--   --nostringval--   2   %stopped_push   --nostringval--   --nostringval--   %loop_continue   --nostringval--   --nostringval--   false   1   %stopped_push   .runexec2   --nostringval--   --nostringval--   --nostringval--   2   %stopped_push   --nostringval--   --nostringval--   %loop_continue
Dictionary stack:
   --dict:1168/1684(ro)(G)--   --dict:0/20(G)--   --dict:77/200(L)--
Current allocation mode is local
Last OS error: No such file or directory
Current file position is 8
GS<1>

Ruby, 12

eval"[]"*9e3

Gives

SystemStackError: stack level too deep

Presumably system-dependent, but you can add orders of magnitude by bumping the last digit up (not recommended).

Edit for explanation: Similarly to some other examples, this creates a string of [][][]...repeated 9000 times, then evaluates it: the rightmost [] is parsed as a function call to the rest, and so on. If it actually got to the beginning, it would throw an ArgumentError because [] is an object with a [] method that requires one argument, but my machine throws an error a little before the stack is over nine thousand.

Java - 115 chars

I think this stays within the spirit of the "no self-calling methods" rule. It doesn't do it explicitly, and it even goes through a Java language construct.

public class S {
    public String toString() {
        return ""+this;
    }
    public static void main(String[] a) {
        new S().toString();
    }
}

FORTH (13)

BEGIN 1 AGAIN

overflows the value stack

C -- 34 characters, no libraries

Though competative with Job's answer,

o(){O();}
O(){o();o();}
main(){o();}

violates the spirt of the challenge by showing how to evade the restriction on constructing a simple recursion. You can save 4 character by removing one call from O, but gcc is smart enough to recongnise that if you use -O3.¹

The trick is quite general and can be done in fortran 77, too (142 characters):

      program o
      i=j()
      stop
      end
      function j()
      j=k()
      end
      function k()
      k=j()
      k=j()
      end

Again, gcc can optimize away a single call in each.

¹ I suppose it inlines one of them and then applys tail recursion elimination. How cool is that!?!.

C, 35 characters

main(){for(;;)*(int*)alloca(1)=0;}

Coq

Compute 70000.

70000 is just syntactic sugar for S (S ( ... (S O) ...)) with 70000 S's. I think it's the type checker that causes the stack overflow.

Here's a warning that is printed before the command is executed:

Warning: Stack overflow or segmentation fault happens when working with large
numbers in nat (observed threshold may vary from 5000 to 70000 depending on
your system limits and on the command executed).

X86 assembly (AT&T), 33 characters

Note that although I'm using the label main as a jump target, this is not a recursive function.

.globl main
main:push $0;jmp main

Clojure, 12 chars

(#(%%)#(%%))

Running in the repl:

user=> (#(%%)#(%%))
StackOverflowError   user/eval404/fn--407 (NO_SOURCE_FILE:1)

Python 2.7 (12 chars)

exec('{'*99)

results in a «s_push: parser stack overflow»

Perl 5, 20 characters

while(1){fork&&wait}

This is a "POSIX program" I happen to have expressed in Perl. Each process creates a child process and waits for it to complete; it will most likely hit a "too many processes" limit, which is the multi-process analogue of a stack overflow. The error itself happens to be ignored, but that's just because there is no automatic "throw" in Perl.

I have not actually tested this program as I don't have a machine I care to fork-bomb handy.

Python (2.7.3), 35 characters

import sys
sys.setrecursionlimit(1)

This operation itself succeeds, but both script and interactive will immediately throw RuntimeError: 'maximum recursion depth exceeded' afterward as a consequence.

Inspired by elssar's answer.