En tant que programmeur, vous connaissez certainement l’erreur d’un débordement de pile due à une récursion évidente. Mais il existe certainement de nombreux moyens étranges et inhabituels pour que votre langue préférée crache cette erreur.

Objectifs:

1. Doit provoquer un débordement de pile clairement visible sur la sortie d'erreur.
2. Non autorisé à utiliser une récursivité évidente.

Exemples de programmes non valides:

// Invalid, direct obvious recursion.
methodA(){ methodA(); }

// Invalid, indirect, but obvious recursion.
methodA(){ methodB(); }
methodB(){ methodA(); }

Les moyens les plus créatifs sont les meilleurs car il s’agit d’un concours de popularité . Par exemple, évitez les réponses évidentes ennuyeuses comme celle-ci:

throw new StackOverflowError(); // Valid, but very boring and downvote-deserving.

Même si j'ai accepté une réponse maintenant, ajouter d'autres réponses est toujours correct :)

Python

import sys
sys.setrecursionlimit(1)

Cela entraînera l'échec immédiat de l'interprète:

$ cat test.py
import sys
sys.setrecursionlimit(1)
$ python test.py
Exception RuntimeError: 'maximum recursion depth exceeded' in <function _remove at 0x10e947b18> ignored
Exception RuntimeError: 'maximum recursion depth exceeded' in <function _remove at 0x10e8f6050> ignored
$ 

Au lieu d'utiliser la récursivité, la pile est réduite afin qu'elle déborde immédiatement.

Python

import webbrowser
webbrowser.open("http://stackoverflow.com/")

C / Linux 32bit

void g(void *p){
        void *a[1];
        a[2]=p-5;
}
void f(){
        void *a[1];
        g(a[2]);
}
main(){
        f();
        return 0;
}

Fonctionne en écrasant l'adresse de retour, gretourne donc au point mainavant d'appeler f. Cela fonctionnera pour toute plate-forme où les adresses de retour sont sur la pile, mais peuvent nécessiter des ajustements.

Bien sûr, écrire en dehors d'un tableau est un comportement indéfini , et vous n'avez aucune garantie que cela provoquera un débordement de pile au lieu de peindre votre moustache en bleu. Les détails des indicateurs de plate-forme, de compilateur et de compilation peuvent faire toute la différence.

JavaScript / DOM

with (document.body) {
    addEventListener('DOMSubtreeModified', function() {
        appendChild(firstChild);
    }, false);

    title = 'Kill me!';
}

Si vous voulez tuer votre navigateur, essayez-le dans la console.

Java

J'ai vu quelque chose comme ça quelque part ici:

Edit: Trouvé à l'endroit où je l'ai vu: la réponse de Joe K au programme le plus court qui génère une erreur StackOverflow

public class A {
    String val;
    public String toString() {
        return val + this;
    }

    public static void main(String[] args) {
        System.out.println(new A());
    }
}

Cela peut dérouter certains débutants en Java. Il cache simplement l'appel récursif. val + thisdevient val + this.toString()parce que valest une chaîne.

Voir le courir ici: http://ideone.com/Z0sXiD

C

Assez facile:

int main()
{
    int large[10000000] = {0};
    return 0;
}

Dépassement de pile non récursif en C

Appel incompatibilité de convention.

typedef void __stdcall (* ptr) (int);

void __cdecl hello (int x) { }

void main () {
  ptr goodbye = (ptr)&hello;
  while (1) 
    goodbye(0);
}

Compiler avec gcc -O0.

__cdeclfonctions attendent l'appelant pour nettoyer la pile, et __stdcallattend l'appelé à le faire, en appelant par le pointeur de fonction typecast, le nettoyage ne se fait jamais - mainpousse le paramètre sur la pile pour chaque appel , mais rien pops et , finalement , la la pile se remplit.

JavaScript

window.toString = String.toLocaleString;
+this;

J'étais frustré par le fait que java 7 et java 8 sont immunisés contre mon code diabolique dans ma réponse précédente . J'ai donc décidé qu'un patch pour cela était nécessaire.

Succès! J'ai fait printStackTrace()jeter un StackOverflowError. printStackTrace()est couramment utilisé pour le débogage et la journalisation et personne ne peut raisonnablement penser que cela pourrait être dangereux. Il n’est pas difficile de voir que ce code pourrait être utilisé pour créer de graves problèmes de sécurité:

public class StillMoreEvilThanMyPreviousOne {
    public static void main(String[] args) {
        try {
            evilMethod();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void evilMethod() throws Exception {
        throw new EvilException();
    }

    public static class EvilException extends Exception {
        @Override
        public Throwable getCause() {
            return new EvilException();
        }
    }
}

Certaines personnes peuvent penser qu'il s'agit d'une récursion évidente. Ce n'est pas. Le EvilExceptionconstructeur n'appelle pas la getCause()méthode pour que cette exception puisse être levée en toute sécurité après tout. L'appel de la getCause()méthode n'entraînera pas non StackOverflowErrorplus. La récursivité fait partie du printStackTrace()comportement normalement insoupçonné de JDK et de toute bibliothèque tierce utilisée pour le débogage et la journalisation utilisés pour inspecter l'exception. De plus, il est probable que le lieu où l'exception est levée est très éloigné de celui où il est traité.

Quoi qu'il en soit, voici un code qui jette un StackOverflowErroret ne contient aucun appel de méthode récursif après tout. La StackOverflowErrorpasse en dehors de la mainméthode, dans JDK UncaughtExceptionHandler:

public class StillMoreEvilThanMyPreviousOneVersion2 {
    public static void main(String[] args) {
        evilMethod();
    }

    private static void evilMethod() {
        throw new EvilException();
    }

    public static class EvilException extends RuntimeException {
        @Override
        public Throwable getCause() {
            return new EvilException();
        }
    }
}

Exception: java.lang.StackOverflowError thrown from the UncaughtExceptionHandler in thread "main"

Assemblage Linux x86 NASM

section .data
    helloStr:     db 'Hello world!',10 ; Define our string
    helloStrLen:  equ $-helloStr       ; Define the length of our string

section .text
    global _start

    doExit:
        mov eax,1 ; Exit is syscall 1
        mov ebx,0 ; Exit status for success
        int 80h   ; Execute syscall

    printHello:
        mov eax,4           ; Write syscall is No. 4
        mov ebx,1           ; File descriptor 1, stdout
        mov ecx,helloStr    ; Our hello string
        mov edx,helloStrLen ; The length of our hello string
        int 80h             ; execute the syscall

    _start:
        call printHello ; Print "Hello World!" once
        call doExit     ; Exit afterwards

Divulgacher:

Oubliant de revenir à printHello, nous sautons à nouveau dans _start.

C ++ au moment de la compilation

template <unsigned N>
struct S : S<N-1> {};

template <>
struct S<0> {};

template
struct S<-1>;

$ g ++ -c test.cc -ftemplate-depth = 40000
g ++: erreur interne du compilateur: erreur de segmentation (programme cc1plus)
S'il vous plaît soumettre un rapport de bogue complet,
avec source prétraitée, le cas échéant.
Voir pour les instructions.

Il n'y a pas de récursivité ce fichier source, aucune des classes n'a elle-même une classe de base, même indirectement. (En C ++, dans une classe de modèle comme celle-ci, S<1>il S<2>s'agit de classes complètement distinctes.) L'erreur de segmentation est due au dépassement de capacité de la pile après la récursivité dans le compilateur.

Bash (alerte de danger)

while true
do 
  mkdir x
  cd x
done

À proprement parler, cela n'entraînera pas directement un débordement de pile, mais générera ce que l'on pourrait appeler une " situation de génération persistante de pile-over-flow ": lorsque vous l'exécutez jusqu'à ce que votre disque soit plein, et que vous souhaitiez supprimer le désordre avec "rm -rf x ", celui-là est touché.

Cela ne se produit pas sur tous les systèmes, cependant. Certains sont plus robustes que d'autres.

Gros danger AVERTISSEMENT:

certains systèmes gèrent cela très mal et vous aurez peut-être du mal à nettoyer (parce que "rm -rf" lui-même rencontrera un problème de récusion). Vous devrez peut-être écrire un script similaire pour le nettoyage.

Mieux vaut essayer cela dans une machine à gratter si vous n’en êtes pas sûr.

PS: la même chose s'applique, bien sûr, si programmé ou fait dans un script batch.
PPS: il peut être intéressant d’obtenir un commentaire de votre part, sur le comportement de votre système particulier ...

Java

Une belle de Java Puzzlers . Qu'est-ce que ça imprime?

public class Reluctant {
    private Reluctant internalInstance = new Reluctant();

    public Reluctant() throws Exception {
        throw new Exception("I'm not coming out");
    }

    public static void main(String[] args) {
        try {
            Reluctant b = new Reluctant();
            System.out.println("Surprise!");
        } catch (Exception ex) {
            System.out.println("I told you so");
        }
    }
}

En fait, il échoue avec une erreur StackOverflowError.

L'exception dans le constructeur est juste un hareng rouge. Voici ce que dit le livre à ce sujet:

Lorsque vous appelez un constructeur, les initialiseurs de variables d'instance sont exécutés avant le corps du constructeur . Dans ce cas, l'initialiseur de la variable internalInstanceappelle le constructeur de manière récursive. Ce constructeur, à son tour, initialise son propre internalInstancechamp en invoquant à nouveau le constructeur Reluctant et ainsi de suite, à l'infini. Ces invocations récursives provoquent StackOverflowErroravant que le corps du constructeur ait une chance de s'exécuter. Parce que StackOverflowErrorest un sous-type de Errorplutôt que de Exception, la clause catch mainne l’attrape pas.

Latex

\end\end

La pile d'entrée déborde parce qu'elle \endse développe de manière répétée dans une boucle infinie, comme expliqué ici .

TeX échoue avec un TeX capacity exceeded, sorry [input stack size=5000]ou similaire.

BF

Peut-être que la pile débordera éventuellement, cela dépend de la longueur de la pile de l'interprète ...

+[>+]

C #, au moment de la compilation

Le compilateur Microsoft C # peut détruire sa pile de différentes façons. chaque fois que vous voyez une erreur "expression est trop complexe à compiler" du compilateur C #, c'est certainement parce que la pile a fondu.

L'analyseur est une descente récursive, ainsi toute structure de langage suffisamment profondément imbriquée fera sauter la pile:

 class C { class C { class C { ....

L'analyseur d'expression est assez intelligent pour éliminer les récursions sur le côté sur lequel on rentre généralement. Habituellement:

x = 1 + 1 + 1 + 1 + .... + 1;

qui construit un arbre d'analyse extrêmement profond, ne fera pas sauter la pile. Mais si vous forcez la récursion à se produire de l'autre côté:

x = 1 + (1 + (1 + (1 + ....+ (1 + 1))))))))))))))))))))))))))))))))))))))))))...;

alors la pile peut être soufflée.

Ceux-ci ont la propriété inélégante que le programme est très grand. Il est également possible de faire entrer l'analyseur sémantique dans des récursions sans limite avec un petit programme car il n'est pas assez intelligent pour supprimer certains cycles impairs dans le système de types. (Roslyn pourrait améliorer cela.)

public interface IN<in U> {}
public interface IC<X> : IN<IN<IC<IC<X>>>> {}
...
IC<double> bar = whatever;
IN<IC<string>> foo = bar;  // Is this assignment legal? 

Je décris pourquoi cette analyse entre ici dans une récursion infinie:

http://blogs.msdn.com/b/ericlippert/archive/2008/05/07/covariance-and-contravariance-part-twelve-to-infinity-but-not-beyond.aspx

et pour de nombreux autres exemples intéressants, vous devriez lire cet article:

http://research.microsoft.com/en-us/um/people/akenn/generics/FOOL2007.pdf

Sur Internet (utilisé par un milliard de personnes / jour)

Redirects, HTTP status code: 301

Par exemple, sur le site Web de support de Dell (pas d'infraction, désolé Dell):

Si vous supprimez le TAG de support de l'URL, les redirections infinies sont effectuées . Dans l'URL suivante, ###### est un tag de support.

http://www.dell.com/support/drivers/uk/en/ukdhs1/ServiceTag/######?s=BSD&~ck=mn

Je crois que cela équivaut à un débordement de pile.

PHP

Un stackoverflow réalisé avec des éléments en boucle uniquement.

$a = array(&$a);
while (1) {
    foreach ($a as &$tmp) {
        $tmp = array($tmp, &$a);
    }
}

Explication (survolez pour voir le spoiler):

Le programme commettra une erreur de segmentation lorsque l’interprète essaiera de récupérer le $tmptableau (lors de la réaffectation).$tmp ici). Tout simplement parce que le tableau est trop profond (auto-référencement) et que le garbage collector aboutit à une récursivité.

Java

J'ai fait exactement le contraire - un programme qui devrait évidemment générer une erreur de débordement de pile, mais ne le fait pas.

public class Evil {
    public static void main(String[] args) {
        recurse();
    }

    private static void recurse() {
        try {
            recurse();
        } finally {
            recurse();
        }
    }
}

Astuce: le programme s'exécute dans le temps O (2 ⁿ ), et n est la taille de la pile (généralement 1024).

De Java Puzzlers # 45:

Supposons que notre machine puisse exécuter 10 ¹⁰ appels par seconde et générer 10 ¹⁰ exceptions par seconde, ce qui est assez généreux par rapport aux normes actuelles. Selon ces hypothèses, le programme prendra fin dans environ 1,7 × 10 ²⁹¹ ans. Pour mettre cela en perspective, la durée de vie de notre soleil est estimée à 10 ¹⁰ ans, alors il est fort à parier qu'aucun d' entre nous sera sur place pour voir ce programme fin. Bien que ce ne soit pas une boucle infinie, cela pourrait tout aussi bien l'être.

C #

Premier post, alors s'il vous plaît, allez-y doucement sur moi.

class Program
{
    static void Main()
    {
        new System.Diagnostics.StackTrace().GetFrame(0).GetMethod().Invoke(null, null);
    }
}

Cela crée simplement une trace de pile, récupère le cadre supérieur (qui sera notre dernier appel Main()), récupère la méthode et l'appelle.

Java

• En Java 5, printStackTrace() entre une boucle infinie.
• En Java 6, printStackTrace()jetteStackOverflowError .
• En Java 7 et 8, cela a été corrigé.

Ce qui est fou, c'est que dans Java 5 et 6, cela ne provient pas du code utilisateur, cela se passe dans le code de JDK. Personne ne soupçonne raisonnablement qu'il printStackTrace()peut être dangereux d'exécuter.

public class Bad {
    public static void main(String[] args) {
        try {
            evilMethod();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void evilMethod() throws Exception {
        Exception a = new Exception();
        Exception b = new Exception(a);
        a.initCause(b);
        throw a;
    }
}

JavaScript: Mutation de fonction itérative non récursive

var f = function() {
    console.log(arguments.length);
};

while (true) {
    f = f.bind(null, 1);
    f();
}

Il n'y a pas de récursion ici du tout. fsera de façon répétée avec de plus en plus d’arguments jusqu’à ce qu’elle puisse déborder de la pile en un seul appel de fonction. La console.logpartie est optionnelle si vous voulez voir combien d'arguments sont nécessaires pour le faire. Cela garantit également que les moteurs intelligents JS ne l'optimiseront pas.

Version Code-golf en CoffeeScript, 28 caractères:

f=->
do f=f.bind f,1 while 1

C # avec un échec épique

using System.Xml.Serialization;

[XmlRoot]
public class P
{
    public P X { get { return new P(); } set { } }
    static void Main()
    {
        new XmlSerializer(typeof(P)).Serialize(System.Console.Out, new P());
    }
}

La façon dont cela échoue est épique, cela m'a complètement bouleversé:

Ce n'est qu'une image d'une série d'images étranges et apparemment infinies.

Cela doit être la chose la plus étrange jamais. Quelqu'un peut-il expliquer? Apparemment, le nombre croissant d'espaces utilisés pour l'indentation fait apparaître ces blocs blancs. Cela se produit sur une entreprise Win7 Enterprise x64 avec .NET 4.5.

Je n'en ai pas encore vu la fin. Si vous remplacez System.Console.Outpar System.IO.Stream.Null, il mourra assez vite.

L'explication est assez simple. Je crée une classe qui n'a qu'une seule propriété et renvoie toujours une nouvelle instance de son type contenant. C'est donc une hiérarchie d'objet infiniment profonde. Maintenant, nous avons besoin de quelque chose qui essaie de lire cela. C'est là que j'utilise le XmlSerializer, ce qui ne fait que cela. Et apparemment, il utilise la récursivité.

frapper

_(){ _;};_

Alors que beaucoup pourraient reconnaître que la récursion est évidente , elle semble jolie. Non?

Lors de l'exécution, vous êtes assuré de voir:

Segmentation fault (core dumped)

Haskell

(triste mais vrai jusqu'au moins ghc-7.6, bien qu'avec O1ou plus cela optimisera le problème)

main = print $ sum [1 .. 100000000]

Petite conversation

Cela crée une nouvelle méthode à la volée, qui
  crée une nouvelle méthode à la volée, qui
    crée une nouvelle méthode à la volée, qui
      ...
    ...
  ...
puis y est transférée.

Un peu de piquant supplémentaire provient de la contrainte de mémoire de pile ET de mémoire de pile en même temps, en créant à la fois un nom de méthode de plus en plus long et un nombre énorme en tant que destinataire, au moment où nous tombons dans le trou ... (mais la récursion nous frappe en premier )

compiler en entier:

downTheRabbitHole
    |name deeperName nextLevel|

    nextLevel := self * 2.
    name := thisContext selector.
    deeperName := (name , '_') asSymbol.
    Class withoutUpdatingChangesDo:[
        nextLevel class 
            compile:deeperName , (thisContext method source copyFrom:name size+1).
    ].
    Transcript show:self; showCR:' - and down the rabbit hole...'.
    "/ self halt. "/ enable for debugging
    nextLevel perform:deeperName.

puis sautez, en évaluant "2 downTheRabbitHole"...
... au bout d'un moment, vous vous retrouverez dans un débogueur, affichant une exception RecursionException.

Ensuite, vous devez nettoyer tout le désordre (SmallInteger et LargeInteger ont maintenant beaucoup de code du pays des merveilles):

{SmallInteger . LargeInteger } do:[:eachInfectedClass |
    (eachInfectedClass methodDictionary keys 
        select:[:nm| nm startsWith:'downTheRabbitHole_'])
            do:[:each| eachInfectedClass removeSelector:each]

ou bien passez quelque temps dans le navigateur, supprimant le pays des merveilles d'Alice.

Voici quelques-uns de la tête de la trace:

2 - and down the rabbit hole...
4 - and down the rabbit hole...
8 - and down the rabbit hole...
16 - and down the rabbit hole...
[...]
576460752303423488 - and down the rabbit hole...
1152921504606846976 - and down the rabbit hole...
2305843009213693952 - and down the rabbit hole...
[...]
1267650600228229401496703205376 - and down the rabbit hole...
2535301200456458802993406410752 - and down the rabbit hole...
5070602400912917605986812821504 - and down the rabbit hole...
[...]
162259276829213363391578010288128 - and down the rabbit hole...
324518553658426726783156020576256 - and down the rabbit hole...
[...]
and so on...

PS: le "withoutUpdatingChangesFile:" a été ajouté pour éviter de devoir nettoyer le fichier journal des modifications persistant de Smalltalk.

PPS: merci pour le défi: penser à quelque chose de nouveau et d'innovant était amusant!

PPPS: J'aime noter que certains dialectes / versions Smalltalk copient les trames de pile débordantes dans le tas - de sorte que celles-ci risquent de se trouver dans une situation de mémoire insuffisante.

C #

Vraiment gros struct, pas de récursivité, C # pur, pas de code dangereux.

public struct Wyern
{
    double a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
}
public struct Godzilla
{
    Wyern a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
}
public struct Cyclops
{
    Godzilla a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
}
public struct Titan
{
    Cyclops a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
}
class Program
{
    static void Main(string[] args)
    {
        // An unhandled exception of type 'System.StackOverflowException' occurred in ConsoleApplication1.exe
        var A=new Titan();
        // 26×26×26×26×8 = 3655808 bytes            
        Console.WriteLine("Size={0}", Marshal.SizeOf(A));
    }
}

comme un kicker, il bloque les fenêtres de débogage en indiquant que {Cannot evaluate expression because the current thread is in a stack overflow state.}

Et la version générique (merci pour la suggestion NPSF3000)

public struct Wyern<T>
    where T: struct
{
    T a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;        
}


class Program
{
    static void Main(string[] args)
    {
        // An unhandled exception of type 'System.StackOverflowException' occurred in ConsoleApplication1.exe
        var A=new Wyern<Wyern<Wyern<Wyern<int>>>>();
    }
}

C #

Mauvaise implémentation de l' ==opérateur de remplacement :

public class MyClass
{
    public int A { get; set; }

    public static bool operator ==(MyClass obj1, MyClass obj2)
    {
        if (obj1 == null)
        {
            return obj2 == null;
        }
        else
        {
            return obj1.Equals(obj2);
        }
    }

    public static bool operator !=(MyClass obj1, MyClass obj2)
    {
        return !(obj1 == obj2);
    }

    public override bool Equals(object obj)
    {
        MyClass other = obj as MyClass;
        if (other == null)
        {
            return false;
        }
        else
        {
            return A == other.A;
        }
    }
}

On pourrait dire qu’il est évident que l’ operator==appel se fait de lui-même en utilisant l’ ==opérateur, mais vous ne pensez généralement pas de cette façon ==, il est donc facile de tomber dans ce piège.

Début de réponse en utilisant SnakeYAML

class A
{

    public static void main(String[] a)
    {
         new org.yaml.snakeyaml.Yaml().dump(new java.awt.Point());
    }
}

Edit: non-golfé

Il appartient au lecteur de savoir comment cela fonctionne: P (astuce: stackoverflow.com)

À propos: la récursivité est faite dynamiquement par SnakeYAML (vous remarquerez si vous savez comment il détecte les champs qu'il sérialise et regarde ensuite dans Pointle code source)

Edit: racontant comment ça marche:

SnakeYAML recherche une paire de méthodes getXXXet setXXXporte le même nom XXXet le type de retour du getter est identique au paramètre de setter; et étonnamment la Pointclasse a Point getLocation()et void setLocation(Point P)qui se retourne; SnakeYAML ne le remarque pas et revient sur cette bizarrerie et StackOverflows. Découvert celui-là en travaillant avec eux à l'intérieur d'un HashMapet en demandant à stackoverflow.com dessus.

C #

getter de propriété implémenté à tort

class C
{
   public int P { get { return P; } }
}

static void Main()
{
   int p = new C().P;
}