Une question similaire à celle-ci a été posée il y a quelques années , mais celle-ci est encore plus délicate.
Le défi est simple. Ecrire un programme (en langue de votre choix) qui exécute de façon répétée le code sans utiliser de structures de répétition telles que while
, for
, do while
, foreach
ou goto
( Donc , pour tout ce que vous tatillons, vous ne pouvez pas utiliser une boucle ). Cependant, la récursion n’est pas autorisée, dans la fonction qui s’appelle sens (voir la définition ci-dessous) . Cela rendrait ce défi beaucoup trop facile.
Il n'y a aucune restriction sur ce qui doit être exécuté dans la boucle, mais postez une explication avec votre réponse afin que les autres puissent comprendre exactement ce qui est mis en œuvre.
Pour ceux qui peuvent être accrochés sur les définitions, la définition d'une boucle pour cette question est la suivante:
A programming language statement which allows code to be repeatedly executed.
Et la définition de la récursivité pour cette question sera votre définition de fonction récursive standard:
A function that calls itself.
Winner sera la réponse qui aura le plus de votes positifs le 16 juillet à 10 heures, heure de l’Est. Bonne chance!
MISE À JOUR:
Pour calmer la confusion qui est toujours exprimée, ceci peut aider:
Règles comme indiqué ci-dessus:
- Ne pas utiliser de boucles ou goto
- Les fonctions ne peuvent pas s'appeler
- Faites ce que vous voulez dans la "boucle"
Si vous voulez implémenter quelque chose et que les règles ne l'interdisent pas explicitement, allez-y et faites-le. Beaucoup de réponses ont déjà plié les règles.
function A
appelsfunction B
et desfunction B
appelsfunction A
pendant qu'une des fonctions exécute quelque chose. Puisque la fonction ne s'appelle pas elle-même, elle devrait être valide sur la base des critères ^. ^rep(f){f();f();}
- il s'agit d'une instruction (une déclaration de fonction est une instruction dans certaines langues) qui permet l'exécution de code à plusieurs reprises. Est-ce interdit? Vous demandez du code pour implémenter une boucle. Si ce code est syntaxiquement une instruction, vous venez de le refuser. Un autre exemple:f(b) { b(); g(b); }; g(b) { f(b); }
. Je dirais quef
c'est une fonction récursive (en étant mutuellement récursif avecg
). Est-ce interdit?Réponses:
Rubis
Démo
Il s'éclaircit la gorge, imprime "Banana" 3070 fois et ajoute "Orange, tu es content de ne pas avoir dit banane?".
Ceci utilise la fonctionnalité ridicule de définition de méthode juste à temps de Ruby pour définir chaque méthode située alphabétiquement entre les mots "ahem" et "aussi" ("ahem", "ahen", "aheo", "ahep", "aheq", "aher", "ahes", "ahet", "aheu", "ahev" ...) pour imprimer d'abord Banana puis appeler le suivant dans la liste.
la source
String#next
appelé dans lesmethod_missing
fonctions, il s’agit plus ou moins d’ajouter 1 à un nombre, sauf que cela fonctionne avec tous les caractères alphanumériques (et les non-alnums s’ils sont les seuls caractères de la chaîne). Voir ruby-doc.org/core-2.1.2/String.html#method-i-nextb.my_tag
. Il est également utilisé dans les modèles ActiveRecord ouOpenStruct
. Dans 'Wat talk', il dit que le globalmethod_missing
est mauvais, mais que la portée est géniale.Python - 16
ou toute autre langue avec eval.
la source
"print 1;"
), la duplique 9 fois (*9
), puis exécute la chaîne résultante (exec
). Répéter un morceau de code sans faire de boucle.exec
poureval
ou leprint
àecho
.CSharp
J'ai élargi le code de manière plus lisible car il ne s'agit plus de code de golf et j'ai ajouté un compteur d'incrément pour que les gens puissent réellement voir que ce programme fait quelque chose.
(Ne fais jamais ça s'il te plait).
Au démarrage, nous créons une nouvelle instance de la
P
classe qui, lorsque le programme tente de quitter, appelle le GC, qui appelle le finaliseur, qui crée une nouvelle instance de laP
classe, qui, lorsqu'elle tente de nettoyer, en crée une nouvelle,P
qui appelle le finaliseur. .Le programme meurt finalement.
Edit: Inexplicablement, cela ne dure que 45 000 fois environ avant de mourir. Je ne sais pas trop comment le GC a découvert ma boucle infinie délicate, mais c'est ce qui s'est passé. En bref, il semble qu'il ne l'ait pas compris et que le fil ait été tué après environ 2 secondes d'exécution: https://stackoverflow.com/questions/24662454/how-does-a-garbage-collector-avoid-an -infinite-loop-here
Edit2: Si vous pensez que cela ressemble un peu trop à la récursivité, considérez mon autre solution: https://codegolf.stackexchange.com/a/33268/23300
Il utilise la réification des méthodes génériques afin qu’au moment de l’exécution, il génère constamment de nouvelles méthodes et chaque méthode à terme appelle une méthode nouvellement créée. J'évite également d'utiliser
reference
des paramètres de type, car normalement, le moteur d'exécution peut partager le code pour ces méthodes. Avec unvalue
paramètre de type, le moteur d'exécution est obligé de créer une nouvelle méthode.la source
Finalize
, ils sont donc parfois appelésfinalizer
. En vrai C #, vous devriez utiliser leIDisposable
motif.Befunge
Les bons vieux Befunge affichent 0 (à partir d’une pile vide) assez longtemps, à mesure que les lignes s’enroulent
la source
JS
(f=function(){ console.log('hi!'); eval("("+f+")()") })()
Fonction fun!
Une fonction qui crée une autre fonction avec le même corps que lui, puis l'exécute.
Il affichera hi à la fin lorsque la limite de pile est atteinte et que tout s'effondre.
Clause de non-responsabilité: vous ne pourrez rien faire dans votre navigateur si la limite de pile est atteinte.
Et un autre, plus diabolique :function f(){ var tab = window.open(); tab.f = f; tab.f()}()
Il crée une fonction qui ouvre une fenêtre, puis crée une fonction dans cette fenêtre qui est une copie de la fonction, puis l'exécute.
Clause de non-responsabilité: si vous autorisez l'ouverture de fenêtres contextuelles, le seul moyen de terminer ce processus consiste à redémarrer votre ordinateur.la source
f
à la fin de votre deuxième fonction. Ce devrait être}f()
à la fin.Assemblage x86 / DOS
Comment ça fonctionne
la source
Java
Directement de XKCD
C'est un jeu de pêche sans fin entre un parent et un enfant!
La cible de
CHILD
est définie surPARENT
et la cible dePARENT
est leCHILD
. Lorsque lesPARENT
appelsAIM
, il lève l'instance de laBALL
classe et il est attrapé par l'instruction catch. La déclaration catch appelle alorsPARENT.TARGET.AIM
où la cible est leCHILD
. L'CHILD
instance fait la même chose et "renvoie la balle" au parent.la source
TARGET.AIM(B);
dans la méthodeAIM
est un appel récursif. Donc, cela viole la règle "les fonctions ne peuvent pas s'appeler".Bash, 3 personnages
oui retournera à plusieurs reprises «y» à la console
Edit: tout le monde est invité à éditer cette ligne:
(merci à Olivier Dulac)
la source
yes
est une commande bash qui affiche le mot oui jusqu'à ce qu'il soit tué ou que le flux soit fermé. Si vous écrivez à l'écran, il ne s'arrêtera jamais tant que vous ne le tuez pas. C'est une sorte de triche cependant, puisqu'il s'agit d'une commande qui consiste essentiellement en une boucle sur printf.yes
pour garder une autre boucle en cours.yes something | xargs someaction
pas de récursivité (vous pouvez même ajouter -n 1 à xargs pour avoir seulement 1 "quelque chose" par ligne, etc.). L'utilisation de xargs ouvre la voie à des comportements plus complexes (même ceux qui n'ont rien à voir avec la sortie yes)yes
.C, 35 caractères
Le programme s’exécute. Je ne sais pas si cela est considéré comme une récursion ou non.
la source
exec
le nouveau processus remplace le processus d'origine, il n'y a donc pas de pile d'appels qui finira par retourner ou déborder.exec
le processus précédent. Il ne débordera pas non plus.C (avec les fonctions intégrées GCC - semble également fonctionner avec clang)
Explication:
main()
premiers appelsframeloop(NULL)
. Dans ce cas, utilisez la commande__builtin_return_address()
intégrée pour obtenir l'adresse de retour (enmain()
) à laquelleframeloop()
renvoyer. Nous retournons cette adresse.printf()
pour montrer que nous sommes en boucleframeloop()
avec l'adresse de retour pour l'appel précédent. Nous examinons dans la pile l’adresse de retour actuelle et, lorsque nous la trouvons, nous substituons l’adresse de retour précédente.frameloop()
appel. Mais puisque l'adresse de retour a été piratée, nous finissons par revenir au point de retourmain()
du premier appel. Nous nous retrouvons donc dans une boucle.La recherche de l'adresse de retour dans la pile serait bien sûr plus nette, mais j'ai déroulé quelques itérations afin d'éviter toute boucle.
Sortie:
la source
setjmp()
/longjmp()
. Celles-ci ne sont pas dans la norme c, mais dans la bibliothèque standard . Cependant, j'avais envie de munger la pile manuellement aujourd'hui ;-)Haskell
Le code suivant ne contient aucune fonction récursive (même indirectement), aucune primitive en boucle et n'appelle aucune fonction récursive intégrée (utilise uniquement
IO
la sortie et la liaison), mais répète une action donnée indéfiniment:Function
extract
n'appelle rien,yc
appelle justeextract
etmain
appelle justeyc
etputStrLn
et>>
, qui ne sont pas récursifs.Explication: L'astuce réside dans le type de données récursif
Strange
. C'est un type de données récursif qui se consomme lui-même et qui, comme le montre l'exemple, permet une répétition arbitraire. Premièrement, nous pouvons construireextract x
, ce qui exprime essentiellement une auto-applicationx x
dans le calcul lambda non typé. Et cela permet de construire le combinateur Y défini commeλf.(λx.f(xx))(λx.f(xx))
.Mise à jour: comme suggéré, je publie une variante plus proche de la définition de Y dans le calcul lambda non typé:
la source
let
liaison et définiryc f = extract $ C $ f.extract
, puisque lalet
liaison est une fonctionnalité de langage qui permet la récursion (classiquelet x = x in x
). Cela réduit également certains caractères :)yc = extract . C . (.extract)
Y
.C ++
Ce qui suit génère un compte à rebours de 10 à "Blast off!" en utilisant un modèle de métaprogrammation.
Cela peut ressembler à un exemple classique de récursivité, mais ce n’est pas le cas, du moins techniquement, selon votre définition. Le compilateur générera dix fonctions différentes .
countdown<10>
imprime "T moins 10" puis appellecountdown<9>
, et ainsi de suite, pourcountdown<0>
imprimer "Blast off!" et revient ensuite. La récursivité se produit lorsque vous compilez le code, mais l'exécutable ne contient aucune structure en boucle.En C ++ 11, on peut obtenir des effets similaires en utilisant le
constexpr
mot clé, tel que cette fonction factorielle. (Il n'est pas possible d'implémenter l'exemple de compte à rebours de cette façon, car lesconstexpr
fonctions ne peuvent pas avoir d'effets secondaires, mais je pense que cela pourrait être possible dans le prochain C ++ 14.)Encore une fois cela ressemble vraiment récursion, mais le compilateur étendra sur
factorial(10)
dans10*9*8*7*6*5*4*3*2*1
, puis remplacez probablement avec une valeur constante de3628800
, de sorte que l'exécutable ne contient aucune mise en boucle ou un code récursif.la source
3628800
directement sans forme intermédiaire.constexpr
a été spécialement conçu pour rendre obsolètes certains aspects de la métaprogrammation des modèles.&countdown<N-1> != &countdown<N>
.Java
Jouons avec le chargeur de classes Java et définissons-le comme son propre parent:
En fait, cette boucle est si puissante que vous devrez utiliser un
kill -9
bouton pour l'arrêter :-)Il utilise 100,1% du processeur de mon Mac.
Vous pouvez essayer de déplacer le
System.out
à la fin de la fonction principale pour expérimenter un autre comportement amusant.la source
CSharp
Un de plus et tout aussi méchant:
Ce n'est pas une récursion ... c'est une réification des modèles de code. Bien qu'il semble que nous appelions la même méthode, le moteur d'exécution crée constamment de nouvelles méthodes. Nous utilisons le paramètre type de int, car cela l’oblige à créer un tout nouveau type et chaque instance de la méthode doit remplacer une nouvelle méthode. Il ne peut pas partager de code ici. Finalement, nous éliminons la pile d’appels car elle attend indéfiniment le retour de l’int qui a été promis mais jamais livré. De la même manière, nous continuons à écrire le type que nous avons créé pour le garder intéressant. En gros, chaque C que nous appelons est une méthode totalement nouvelle qui a juste le même corps. Ce n'est pas vraiment possible dans un langage comme C ++ ou D qui font leurs templates lors de la compilation. Depuis, C # JIT est super paresseux, il ne crée ce contenu qu’au dernier moment. Ainsi,
la source
Redcode 94 (Core War)
MOV 0, 1
Copie l'instruction à l'adresse zéro pour en adresser une. Parce que dans Core War, toutes les adresses sont relatives à l'adresse actuelle du PC et modulo à la taille du noyau. Il s'agit d'une boucle infinie dans une instruction unique.
Ce programme (guerrier) s’appelle " Imp " et a été publié pour la première fois par AK Dewdney.
la source
SPL 0, 0; MOV 1, -2
effet.Dard
Je suppose que ce serait la manière classique de faire de la récursivité sans aucune fonction récursive réelle. Aucune fonction ci-dessous ne se désigne par son nom, directement ou indirectement.
(Essayez-le à dartpad.dartlang.org )
la source
JS
Pas très original mais petit. 20 caractères.
la source
,1
et cela fonctionnera toujours,setInterval
n'est pas une déclaration, cependant; c'est seulement une fonction. Il est utilisé dans une déclaration d'expression, et si nous ne pouvons pas utiliser des déclarations d'expression, je ne le sais même plus.Signaux en C
Le comportement de ce programme est évidemment très indéfini, mais aujourd’hui, sur mon ordinateur, il continue d’imprimer «Hello, world!».
la source
Emacs Lisp
C’est le moment idéal pour montrer la conception puissante de Lisp où "le code est constitué de données et les données sont le code". Certes, ces exemples sont très inefficaces et cela ne devrait jamais être utilisé dans un contexte réel.
Les macros génèrent du code qui est une version non déroulée de la boucle supposée et ce code généré correspond à ce qui est évalué au moment de l'exécution.
repeat-it: permet de boucler N fois
test de répétition:
repeat-it-with-index:
Cette macro est semblable à la précédente,
repeat-it
mais elle fonctionne exactement comme la macro en boucle courante.do-times
Elle vous permet de spécifier un symbole qui sera lié à l’index de la boucle. Il utilise un symbole de temps d'expansion pour s'assurer que la variable d'index est définie correctement au début de chaque boucle, que vous modifiiez ou non sa valeur pendant le corps de la boucle.test de répétition avec index:
Ce test montre que:
Le corps évalue N fois
la variable d'index est toujours définie correctement au début de chaque itération
changer la valeur d'un symbole nommé "repli" ne gâchera pas l'index
la source
Calcul lambda non typé
la source
Haskell, 24 caractères
ou sous forme condensée, avec 24 caractères
(bien que le texte soit modifié, cela restera en boucle - cela imprimera deux guillemets et une nouvelle ligne à l'infini)
explication: print "abc" est fondamentalement une action d'E / S qui imprime simplement "abc".
repeat est une fonction qui prend une valeur x et retourne une liste infinie composée uniquement de x.
séquence_ est une fonction qui prend une liste d'actions I / O et renvoie une action I / O qui effectue toutes les actions de manière séquentielle.
donc, fondamentalement, ce programme dresse une liste infinie de commandes print "abc" et les exécute à plusieurs reprises. sans boucles ni récursivité.
la source
repeat
que ouia programming language statement which allows code to be repeatedly executed
.fix(print"">>)
, cela n’implique pas non plus de fonctions de répétition nommées explicitement.ASM (x86 + I / O pour Linux)
Peu importe combien vos langages de haut niveau insupportables vont lutter, ce sera toujours une manipulation cachée du pointeur d’instructions. En fin de compte, ce sera une sorte de "goto" (jmp), à moins que vous ne soyez assez ennuyé pour dérouler la boucle au moment de l'exécution.
Vous pouvez tester le code sur Ideone
Vous pouvez également consulter une version plus raffinée de cette idée dans le code DOS de Matteo Italia .
Il commence par la chaîne 0..9 et le remplace par A..J. Aucun saut direct n’est utilisé (disons qu’il n’ya pas eu de "goto"), pas de récurrence non plus.
Le code pourrait probablement être plus petit avec un certain abus de calcul d'adresse, mais travailler sur un compilateur en ligne est gênant, donc je vais le laisser tel quel.
Partie centrale:
Code entier
la source
C préprocesseur
Une petite "technique" que j'ai imaginée lors d'un défi d'obscurcissement. Il n'y a pas de récursion de fonction, mais il y a ... récursion de fichier?
noloop.c:
J'ai écrit / testé cela en utilisant gcc. Il est évident que votre compilateur doit prendre en charge la
__INCLUDE_LEVEL__
macro (ou la__COUNTER__
macro avec quelques modifications) pour que celle-ci soit compilée. Cela devrait être assez évident de savoir comment cela fonctionne, mais pour le plaisir, lancez le préprocesseur sans compiler le code (utilisez le-E
drapeau avec gcc).la source
PHP
En voici un avec PHP. Boucle en incluant le même fichier jusqu'à ce que le compteur atteigne $ max:
La même chose qu'une boucle for:
la source
header("Location: .?x=".$_GET['x']+1);
compté comme récursion?Python
Le code suivant ne contient aucune fonction récursive (directe ou indirecte), aucune primitive en boucle et n'appelle aucune fonction intégrée (à l'exception de
print
):Imprime "Bonjour tout le monde!" un nombre de fois donné.
Explanation: Function
z
implémente le combinateur strict de points Z qui, sans être défini de manière récursive, permet d'exprimer tout algorithme récursif.la source
g
très indirectement récursif.g
appel appelle àg
nouveau? Bien sûr, le truc est l’application automatiqueg(g)
, mais il n’ya pas de récursivité. Souhaitez-vous appelerg
indirectement récursif si vous n'avez pas vug(g)
? C’est le moyen standard de le faire dans des langues qui ne permettent pas de définitions récursives, telles que le lambda calcul.g
comme argumentx
et ensuite appelezx(x)
.code machine z80
Dans un environnement où vous pouvez exécuter à chaque adresse et mapper la ROM partout, mappez 64 Ko de ROM remplie de zéros sur l'espace d'adressage entier.
Ce qu'il fait: rien. À plusieurs reprises.
Comment ça marche: le processeur va commencer à s’exécuter, l’octet
00
est unenop
instruction, il va donc continuer, atteindre l’adresse$ffff
, se boucler$0000
et continuer à exécuternop
s jusqu’à ce que vous le réinitialisiez.Pour le rendre légèrement plus intéressant, remplissez la mémoire avec une autre valeur (veillez à éviter les instructions de flux de contrôle).
la source
Perl-regex
démo
ou essayez comme:
Le
(?!)
jamais correspondre. Le moteur des expressions rationnelles essaie donc de faire correspondre chaque position de largeur zéro dans la chaîne correspondante.Le
(q x x x 10)
est le même que(" " x 10)
- répétez lesspace
dix fois.Edit: modification des "caractères" en position de largeur zéro afin d’être plus précis pour une meilleure compréhension. Voir les réponses à cette question de stackoverflow .
la source
T-SQL -12
la source
GO
est en fait une directive SSMS, raison pour laquelle vous ne pouvez pas la mettre dans des objets scriptés T-SQL, comme par exemple une procédure stockée.C #
Imprime tous les entiers de uint.MaxValue à 0.
la source
JS (dans le navigateur)
Que dis-tu de ça?
Imprime l'heure actuelle et recharge la page.
la source
[Exception... "The operation is insecure." code: "18" nsresult: "0x80530012 (SecurityError)" location: "<unknown>"]