导致堆栈溢出的最短代码是什么?

为了纪念 Stack Overflow 的公开发布,最短的引起堆栈溢出的代码是什么? 欢迎使用任何语言。

埃塔: 只是为了弄清楚这个问题,因为我是一个偶尔的 Scheme 用户: 尾部调用“递归”实际上是迭代,任何解决方案,可以转换成一个迭代解决方案相对一个体面的编译器将不会计算在内。翻译: 小宝宝 P- 小宝宝 P- 小宝宝 P- 小宝宝 P- 小宝宝 P- 小宝宝 P- 小宝宝 P- 小宝宝 P- 小宝宝 P- 小宝宝 P- 小宝宝 P- 小宝宝

ETA2: 我现在已经选择了一个“最佳答案”; 请参阅 这篇文章的基本原理。感谢所有贡献的人! : -)

36855 次浏览

我目前最好的(在 x86汇编中)是:

push eax
jmp short $-1

这会产生3字节的目标代码(50 EB FD)。对于16位代码,这也是可能的:

call $

这也导致3个字节(E8 FD FF)。

C + + :

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

C # :

public int Foo { get { return Foo; } }

Python :

so=lambda:so();so()

或者:

def so():so()
so()

如果 Python 优化了 tail 调用... ..:

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

图18:

溢出

    PUSH
CALL   overflow
int main(){
int a = 20;
return main();
}

JavaScript:

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


C + + 使用函数指针:

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

英语:

recursion = n. See recursion.
/* In C/C++ (second attempt) */


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

下面是我的 C 语言贡献,有18个字符:

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

这是一个 很多更难尾部呼叫优化! :-P

C # ,以20个字符完成(不包括空格) :

int s(){
return s();
}

CIL/MSIL :

loop: ldc.i4.0
br loop

目标代码:

16 2B FD

您也可以在 C # . net 中尝试这种方法

throw new StackOverflowException();

下面用 BASIC 语言怎么样:

10 GOSUB 10

(我恐怕没有 BASIC 解释器,所以这只是猜测)。

内梅尔 :

这个带有 StackOverflow 异常的 使编译器崩溃:

def o(){[o()]}

露比:

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

我非常喜欢 Cody 的回答,下面是我在 C + + 中的类似贡献:

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


typedef Overflow<0>::type Kaboom;

无论如何都不是一个代码高尔夫条目,但仍然,任何元堆栈溢出! :-P

口齿不清

(defun x() (x)) (x)
a{return a*a;};

编制:

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

扩展到:

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

再说一遍:

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

12个字符的 perl:

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

Bash 使用10个字符(函数中的空格很重要) :

i(){ i;};i

完成 Delphi 程序。

program Project1;
{$APPTYPE CONSOLE}
uses SysUtils;


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

号角:

Poke(0)

Java (尴尬) :

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


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

剪辑 当然,它可以大大缩短:

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

15个字符中的 so.c:

main(){main();}

结果:

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

编辑 : 好的,它使用-Wall 提供警告,并且不会使用-O2导致堆栈溢出!

我曾在 Erlang 尝试过:

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

双重调用本身使内存使用量上升到 O(n^2)而不是 O(n)

然而,Erlang 解释器似乎并没有崩溃。

JavaScript:

嬉皮士回答了一句话:

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

字符数相同,但没有新行:)

递归已经过时了。这里是相互递归。通过调用任一函数开始。

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

附注: 但是你要求的是最短的方式... 而不是最有创意的方式!

Java (X.Java 的完整内容) :

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

考虑到所有的语法糖,我想知道是否有任何更短的可以在 Java 中完成。有人吗?

编辑: 哎呀,我错过了已经有几乎相同的解决方案张贴。

编辑2: 我想说,这是(字符智慧)最短的可能

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

编辑3: 感谢 Anders 指出 null 不是最优参数,所以它更简短:

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

在单元 spus 上,没有堆栈溢出,因此不需要递归,我们只需擦除堆栈指针。

(“ andi $1,$1,0”) ;

3字节:

标签:
普夏
Jmp 标签

更新

根据 (旧的?) Intel (?)文档,这也是3个字节:

标签:
Call label

PHP -递归只是为了好玩。我猜想需要一个 PHP 解释器会使它无法运行,但是,嘿,它会导致崩溃。

function a() { a(); } a();

已经有一个 perl,但是这个字符短了几个字符(9 vs 12)——而且它不递归:)

S//* _ = 0/e

GWBASIC 输出..。

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

堆栈深度不大: -)

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

F #

人们一直在问“ F # 有什么用?”

let rec f n =
f (n)

性能优化版本(将更快失败:)

let rec f n =
f (f(n))

我有一个在 E2上的 无限循环的这些列表-只看标题中指示为“堆栈溢出”的那些。

我觉得是最短的

[dx]dx

华盛顿。可能有一个较短的解决方案在 假的

编辑: 显然这不工作... 至少在 GNU DC。也许它是在一个 BSD 版本。

露比:

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

(17个字符)

在 Lua:

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

您必须对递归调用的结果做些什么,否则尾部调用优化将允许它永远循环下去。对高尔夫代码来说很弱,但是拥有它很好!

我想那个和冗长的关键字意味着 Lua 短期内不会赢得代码高尔夫。

批处理程序 Call.cmd;

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

10个字符中的 Perl

sub x{&x}x

最终会耗尽所有可用的内存。

MS-DOS 批次:

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

爪哇咖啡

Java 解决方案的稍短版本。

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

在 Scheme 中,这将导致解释器耗尽内存:

(define (x)
((x)))


(x)

十个字中的 Shell 脚本解决方案,包括换行:

技术上来说不是堆栈溢出,但逻辑上是这样的,如果你认为生成一个新进程就是构造一个新的堆栈框架。

#!sh
./so

结果:

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

注意: 别在家尝试

在 Whitespace,我认为:

它可能不会出现。 :/

C -它不是最短的,但是没有递归。它也不可移植: 它在 Solaris 上崩溃,但是一些 alloca ()实现可能在这里返回一个错误(或者调用 malloc ())。对 printf ()的调用是必需的。

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

带有27个非空格字符的 C #-包括调用。

Action a = null;
a = () => a();
a();
xor esp, esp
ret

PowerShell

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

“由于调用深度溢出,脚本失败。调用深度达到1001,最大值为1000。”

读这一行,然后做它说的 两次

Bash: 只有一个进程

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

鲁比,目前为止比其他的短:

def a;a;end;a

(13个字符)

几乎所有的贝壳:

sh $0

(5个字符,仅在从文件运行时有效)

试着在一个汉堡包上放超过4个肉饼。

时髦:

main()

$groovy stack.groovy:

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

16位空间中的5个字节会导致堆栈溢出。

push cs
push $-1
ret

在汇编语言中(x86处理器,16或32位模式) :


call $

它将产生:

  • 在32位模式下: 0xe8; 0xfb; 0xff; 0xff; 0xff

  • 在16位模式下: 0xe8; 0xfd; 0xff

在 C/C + + 中:


int main( ) {
return main( );
}

Z-80汇编程序——在内存位置0x0000:

rst 00

一个字节——0xC7——将当前 PC 推入堆栈并跳转到地址0x0000的无休止循环。

Javascript

为了减少一些字符,并让我们自己被踢出更多的软件商店,让我们这样做:

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

哈斯克尔:

let x = x
print x

还没人提到 ColdFusion 呢,所以..。

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

应该可以了。

VB.Net

Function StackOverflow() As Integer
Return StackOverflow()
End Function

TCL:

proc a {} a

我没有一个 tclsh 解释器可以执行尾递归,但这可能会欺骗这样的东西:

proc a {} "a;a"

第四:

: a 1 recurse ; a

gforth解释器内部:

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

在 PowerMacG4的 OpenFirmware 提示符下,这只是挂起了机器。 :)

另一个 PHP 示例:

<?
require(__FILE__);

为了找乐子,我不得不查一下摩托罗拉 HC11装配线:

              org           $100
Loop    nop
jsr            Loop

Prolog

医生: ——医生。

= 5个字符

然后启动它并查询 p

我认为这是相当小,并运行了堆栈在序言。

只在 swi prolog 中查询一个变量就会产生:

?-X. 100万年后 % % > > 42 < < (最后一个版本提出了这个问题)

这是另一个 bash 叉子炸弹: : (){ : | : & }:

作为 C 函数中的局部变量:

int x[100000000000];

不是很短,但是很有效! (JavaScript)

setTimeout(1, function() {while(1) a=1;});

C #

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

注意,我的程序是一个可编译的程序,而不仅仅是一个函数。我还删除了多余的空格。

为了显示才华,我尽可能把班名缩小。

所有这些答案,没有 Befunge? 我敢打赌,这是所有答案中最短的一个:

1

不是开玩笑,你自己试试: http://www.quirkster.com/iano/js/befunge.html

编辑: 我想我需要解释一下这个。操作数1将一个1推送到 Befunge 的内部堆栈上,由于缺少其他操作数,根据该语言的规则将其放入一个循环中。

使用所提供的解释器,您最终——我的意思是 最终——会遇到代表 Befunge 堆栈的 Javascript 数组变得太大以至于浏览器无法重新分配的情况。如果您有一个简单的 Befunge 解释器,其堆栈较小且有界——就像下面大多数语言的情况一样——这个程序会更快地导致更明显的溢出。

除非存在空程序导致堆栈溢出的语言,否则下面的代码应该是最短的。

贝丰奇:

:

反复复制顶部堆栈值。

编辑: 帕特里克的更好。用1填充堆栈比用0填充堆栈要好,因为解释器可以优化将0作为 no-op 推入空堆栈。

我认为这是作弊,我以前从来没有玩过;)但是现在开始

8086汇编程序:

Org Int3VectorAddress; 这是作弊吗?

第三项

1字节或5个字符生成代码,你怎么说?

如果你认为一个调用框架是一个进程,而堆栈是你的 Unix 机器,你可以考虑一个分叉炸弹是一个 平行程序来创建一个堆栈溢出条件。试试这个13个字符的 bash 号码。不需要保存到文件。

:(){ :|:& };:

鲁比,尽管不是那么短:

class Overflow
def initialize
Overflow.new
end
end


Overflow.new

特克斯:

\def~{~.}~

结果:

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

乳胶:

\end\end

结果:

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

我认为这在 Java 中是可行的(未经尝试) :

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

在静态初始化中应该在由于缺少 main (String [])而导致失败之前溢出。

不会是最短的,但我必须尝试一些东西... C #

String [] f = new string [0] ;

短一点

static void Main(){Main();}
Person JeffAtwood;
Person JoelSpolsky;
JeffAtwood.TalkTo(JoelSpolsky);

这里希望没有尾部递归!

使用名为“ s.bat”的 Window 批处理文件:

call s

C # 中,这将创建一个堆栈溢出..。

static void Main()
{
Main();
}

为什么不呢

mov sp,0

(栈生长下来)

在一个名为 so.ps 的 PostScript文件中,将导致 Execstackoverflow

%!PS
/increase {1 add} def
1 increase
(so.ps) run

在 Irssi (基于终端的 IRC 客户端,而不是“真正”的编程语言)中,$L 表示当前的命令行。因此,可以使用以下命令导致堆栈溢出(“达到最大递归限制”) :

/eval $L

每个任务都需要正确的工具。满足 溢出语言,优化产生堆栈溢出:

so

这是 Ruby 的另一个答案,它使用了 lambdas:

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

在这篇文章之后,我选择了“最佳答案”。但首先,我想感谢一些非常原创的贡献:

  1. Aku 的人。每种方法都探索一种导致堆栈溢出的新的原始方法。我将在下一篇文章中探讨这个想法。:-)
  2. Cody 给了 Nemerle 编译器一个堆栈溢出。
  3. 而且(有点不情愿地) ,Gate刽子手的一个关于抛出堆栈溢出异常。 :-P

尽管我很喜欢上面的内容,但挑战在于高尔夫代码,为了公平起见,我必须对最短的代码—— Befunge 条目——给出“最佳答案”; 我不相信任何人能够打败它(尽管 Konrad 肯定已经尝试过了) ,所以恭喜 Patrick!

看到大量的按递归进行堆栈溢出的解决方案,我很惊讶没有人(到目前为止)提出 Y 组合器(参见 Dick Gabriel 的文章 Y 的原因作为入门)。我有一个使用 Y 组合子的递归解决方案,以及 aku 的 f (f (x))方法。:-)

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

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

K & R C 的简短解决方案可以汇编如下:

main(){main()}

14字节

下面是 Scheme 中另一个有趣的例子:

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

Actionscript 3: 使用数组完成所有操作... ..。

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

也许不是最小的,但我觉得很可爱。特别是推方法返回新的数组长度!

作为对 Y 组合器注释的回应,我不妨在 SKI 演算中使用 Y 组合器:

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

据我所知没有任何 SKI 解释器,但是我曾经用 actionscript 在一个小时内写了一个图形解释器。如果有兴趣,我愿意发布(虽然我从来没有得到的布局工作效率很高)

请点击这里阅读: Http://en.wikipedia.org/wiki/ski_combinator_calculus

在 x86汇编中,在 interrupt handler 的内存中放置“除以0”指令,以便“除以0”!

Groovy (5B) :

run()

在 perl 中:

`$0`

事实上,这将适用于任何支持 backquote-command 语法并将自己的名称存储在 $0中的 shell

错:

[1][1] #

(False 是一种堆栈语言: # 是一个 while 循环,它包含2个闭包,一个条件和一个主体。身体是导致溢出的原因)。

CMD 在一行中溢出

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

Prolog

当查阅 SWI-Prolog 和 Sicstus Prolog 时,该程序会崩溃。

p :- p, q.
:- p.
Redmond.Microsoft.Core.Windows.Start()

PIC18

TK 给出的 PIC18答案产生以下指令(二进制) :

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

但是,CALL 本身将执行堆栈溢出:

CALL $
1110 1100 0000 0000
0000 0000 0000 0000

更小更快的 PIC18

但是 RCALL (相对调用)更小(不是全局内存,所以不需要额外的2字节) :

RCALL $
1101 1000 0000 0000

所以 PIC18上最小的是一条单指令,16位(两个字节)。每个循环需要两个指令周期。在4个每个指令周期数周期你有8个时钟周期。PIC18有一个31级的堆栈,因此在第32个循环之后,它将在256个时钟周期内溢出堆栈。在64兆赫,你会 在4微秒和2字节内溢出堆栈

PIC16F5x (更小更快)

然而,PIC16F5x 系列使用12位指令:

CALL $
1001 0000 0000

同样,每个循环两个指令周期,每个指令4个时钟,所以每个循环8个时钟周期。

然而,PIC16F5x 有一个两级堆栈,所以在第三个循环中它会溢出,共有24条指令。在20兆赫时,它将 溢出时间为1.2微秒和1.5字节

英特尔4004

英特尔4004有一个8位调用子例程指令:

CALL $
0101 0000

对于好奇,对应一个“ P”。使用3级堆栈,总共需要24个时钟周期。(除非你的4004超频了——拜托,你知道你想这么做的。)

这和 befunge 的答案一样小,但是比当前解释器中运行的 befunge 代码快得多。

尾部调用优化可能会因为没有尾部调用而受到破坏:

(defun f () (1+ (f)))

在哈斯克尔

fix (1+)

这将尝试查找(1 +)函数(λ n → n + 1)的修复点

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

那么

fix (1+)

变成了

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

请注意

fix (+1)

只是循环。

D 中的元问题:

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

编译时堆栈溢出

_asm t: call t;

一个更好的 Lua 解决方案:

function c()c()end;

把这个插入 SciTE 或者一个交互式命令提示符,然后调用它!

请告诉我“ GNU”的首字母缩写是什么意思。

奥卡姆

let rec f l = f l@l;;

这个有点不一样。堆栈上只有一个堆栈帧(因为它是尾递归的) ,但是它的输入一直在增长,直到溢出堆栈为止。使用非空列表调用 f,如下所示(在解释器提示符下) :

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

虽然它没有一个真正的堆栈..。

我靠,五个字母

+[>+]

Z80汇编语言。

.org 1000
loop: call loop

这会在1000位置生成3个字节的代码... ..。

1000 CD 0010

C #

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


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

我意识到这并不是最短的(甚至代码也不会接近短) ,但是我就是忍不住抛出一个异常,当被抛出时会抛出一个 stackoverflow 异常,在它能够终止运行时本身之前 ^ ^

Ruby (又一次) :

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

现在已经有很多 Ruby 解决方案,但是我认为我应该附加一个 regexp 来进行更好的测试。

PostScript,7个字符

{/}loop

当在 GhostScript 中运行时,抛出以下异常:

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

下面是不使用变量(51个字符)的递归版本:

[{/[aload 8 1 roll]cvx exec}aload 8 1 roll]cvx exec

另一个 Windows 批处理文件:

:a
@call :a
main(){
main();
}

简单明了的 C 对我来说很直观。

GNU make:

创建一个名为“ Makefile”的文件,其内容如下:

a:
make

那就赶紧跑:

$ make

请注意,必须使用制表符来抵消单词“ make”。该文件为9个字符,包括2个行尾字符和1个制表符。

我想你也可以对 bash 做类似的事情,但是它可能太容易变得有趣了:

创建一个文件名“ b”并将其标记为可执行文件(chmod + x b) :

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

现在使用

$ ( PATH=$PATH:. ; b )

很难说这种方法在技术上是否会导致堆栈溢出,但它确实构建了一个堆栈,这个堆栈会不断增长,直到机器耗尽资源。使用 GNU make 做这件事的好处是,您可以看到它在构建和销毁堆栈时输出状态信息(假设您在崩溃发生之前的某个时刻命中 ^ C)。

Java:

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

实际上会导致初始化 X 类的堆栈溢出。在调用 main ()之前,JVM 必须加载这个类,并且当它这样做时,它会触发任何匿名静态代码块:

static {
new X();
}

正如你所看到的使用缺省构造函数实例化 x。JVM 甚至会在构造函数之前调用匿名代码块:

{
new X();
}

这就是递归部分。

Fortran,13和20个字符

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

或者

call main
end

第二种情况是依赖于编译器的; 对于 GNUFortran,它将需要使用 -fno-underscoring进行编译。

(两项计算均包括所需的换行)

胡特溢出!

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

哈斯克尔:

main = print $ x 1 where x y = x y + 1

Dyalog APL

fib←{
⍵∊0 1:⍵
+/∇¨⍵-1 2
}
int main(void) { return main(); }

PHP 是一个递归缩写

巨蟒:

import sys
sys.setrecursionlimit(sys.maxint)
def so():
so()
so()

Java: 35个字符

我认为已经太晚了,但我还是会发布我的想法:

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

使用静态初始值设定项和实例初始值设定项特性。

下面是我计算机上的输出(注意,它显示了两条错误消息) :

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.

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

JavaScript (17字节)

eval(t="eval(t)")

VB 脚本(25字节)

t="Execute(t)":Execute(t)

编译器错误信息

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

产出:

$ 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>’
......

即使编译器遍历了模板,也会出现下一个错误: 缺少 main