Una pregunta similar a esta se hizo hace un par de años , pero esta es aún más complicada.
El desafío es simple. Escribir un programa (en el idioma de su elección) que ejecuta repetidamente el código sin necesidad de utilizar ninguna estructura de repetición, como while
, for
, do while
, foreach
o goto
( Así que por todo lo que nitpickers, no se puede utilizar un bucle ). Sin embargo, la recursión no está permitida, en la función que se llama a sí misma sentido (véase la definición a continuación) . Eso haría este desafío demasiado fácil.
No hay restricciones sobre lo que debe ejecutarse en el ciclo, pero publique una explicación con su respuesta para que otros puedan entender exactamente lo que se está implementando.
Para aquellos que pueden estar colgados en las definiciones, la definición de un bucle para esta pregunta es:
A programming language statement which allows code to be repeatedly executed.
Y la definición de recursión para esta pregunta será su definición de función recursiva estándar:
A function that calls itself.
El ganador será la respuesta que tenga más votos positivos el 16 de julio a las 10 a.m., hora del este. ¡Buena suerte!
ACTUALIZAR:
Para calmar la confusión que aún se expresa, esto puede ayudar:
Reglas como se indicó anteriormente:
- No uses bucles o goto
- Las funciones no pueden llamarse a sí mismas
- Haz lo que quieras en el 'bucle'
Si desea implementar algo y las reglas no lo rechazan explícitamente, continúe y hágalo. Muchas respuestas ya han torcido las reglas.
function A
llamadasfunction B
yfunction B
llamadasfunction A
mientras 1 de las funciones realiza algo. Como la función no se llama a sí misma, debería ser válida según los criterios ^. ^rep(f){f();f();}
esta es una declaración (una declaración de función es una declaración en algunos idiomas) que permite ejecutar código repetidamente. ¿Está prohibido? Pide código para implementar un bucle. Si ese código es sintácticamente una declaración, simplemente lo ha rechazado. Otro ejemplo:f(b) { b(); g(b); }; g(b) { f(b); }
. Yo diría quef
es una función recursiva (al ser recursiva mutuamente cong
). ¿Está prohibido?Respuestas:
Rubí
Manifestación
Se aclara la garganta, imprime "Plátano" 3070 veces y también pone "Naranja, ¿te alegra que no haya dicho plátano?".
Utiliza la ridícula funcionalidad de definición de método justo a tiempo de Ruby para definir cada método que se encuentra alfabéticamente entre las palabras 'ahem' y 'también' ("ahem", "ahen", "aheo", "ahep", "aheq", "aher", "ahes", "ahet", "aheu", "ahev" ...) para imprimir primero Banana y luego llamar al siguiente en la lista.
fuente
String#next
que se llama enmethod_missing
funciones más o menos como agregar 1 a un número, excepto que funciona con todos los caracteres alfanuméricos (y no alnums si son los únicos caracteres en la cadena). Ver ruby-doc.org/core-2.1.2/String.html#method-i-nextb.my_tag
. También se usa en modelos ActiveRecord oOpenStruct
. En 'Wat talk', dice que globalmethod_missing
es malo, pero el alcance es impresionante.Python - 16
o cualquier otro idioma con eval.
fuente
"print 1;"
), la duplica 9 veces (*9
), luego ejecuta la cadena resultante (exec
). Repetir un fragmento de código sin hacer un bucle.exec
toeval
o elprint
toecho
.CSharp
He expandido el código de una manera más legible, ya que esto ya no es un código de golf y he agregado un contador de incrementos para que la gente pueda ver que este programa hace algo.
(No hagas esto nunca por favor).
Al inicio, creamos una nueva instancia de la
P
clase, que cuando el programa intenta salir llama al GC que llama al finalizador que crea una nueva instancia de laP
clase, que cuando intenta limpiar crea una nuevaP
que llama al finalizador. .El programa finalmente muere.
Editar: Inexplicablemente, esto solo se ejecuta alrededor de 45k veces antes de morir. No sé cómo el GC descubrió mi complicado bucle infinito, pero lo hizo. El resumen es que parece que no lo resolvió y que el hilo simplemente se cortó después de aproximadamente 2 segundos de ejecución: https://stackoverflow.com/questions/24662454/how-does-a-garbage-collector-avoid-an -infinite-loop-here
Edit2: si crees que esto es demasiado parecido a la recursión, considera mi otra solución: https://codegolf.stackexchange.com/a/33268/23300
Utiliza la reificación de métodos genéricos para que en tiempo de ejecución genere constantemente nuevos métodos y cada método en término llama a un método nuevo. También evito usar
reference
parámetros de tipo, ya que normalmente el tiempo de ejecución puede compartir el código para esos métodos. Con unvalue
parámetro de tipo, el tiempo de ejecución se ve obligado a crear un nuevo método.fuente
Finalize
por lo que a veces se les llamafinalizer
. En C # real, debe usar elIDisposable
patrón.Befunge
El viejo Befunge sale 0 (de una pila vacía) casi para siempre, a medida que las líneas se envuelven.
fuente
JS
(f=function(){ console.log('hi!'); eval("("+f+")()") })()
Fun fun!
Una función que crea otra función con el mismo cuerpo que ella misma y luego la ejecuta.
Mostrará hola al final cuando se alcance el límite de la pila y todo se derrumbe.
Descargo de responsabilidad: no podrá hacer nada en su navegador hasta que se alcance el límite de pila.
Y otro, más malvado :function f(){ var tab = window.open(); tab.f = f; tab.f()}()
Crea una función que abre una ventana, luego crea una función dentro de esa ventana que es una copia de la función y luego la ejecuta.
Descargo de responsabilidad: si va a permitir la apertura de ventanas emergentes, la única forma de terminar esto será reiniciando su computadorafuente
f
al final de tu segunda función. Debería ser}f()
al final.Ensamblaje x86 / DOS
Cómo funciona
fuente
Java
Directamente desde XKCD
¡Es un juego interminable de captura entre padres e hijos!
El objetivo de
CHILD
se establece enPARENT
y el objetivo dePARENT
esCHILD
. Cuando lasPARENT
llamadasAIM
, arroja la instancia de laBALL
clase y es capturada por la instrucción catch. La instrucción catch luego llama aPARENT.TARGET.AIM
donde está el objetivoCHILD
. LaCHILD
instancia hace lo mismo y "devuelve la pelota" al padre.fuente
TARGET.AIM(B);
en métodoAIM
es una llamada recursiva. Esto viola la regla "las funciones no pueden llamarse a sí mismas".Bash, 3 personajes
yes repetidamente devolverá 'y' a la consola
Editar: se alienta a todos a editar esta línea:
(gracias a Olivier Dulac)
fuente
yes
es un comando bash que imprime la palabra yes hasta que se elimina o la secuencia se cierra. Si está escribiendo en la pantalla, nunca se detendrá hasta que lo mate. Sin embargo, es una especie de trampa, ya que es un comando que básicamente consiste en un bucle sobre printf.yes
para mantener en funcionamiento algún otro ciclo.yes something | xargs someaction
:: sin recursión (incluso puedes agregar -n 1 a xargs para tener solo 1 "algo" por línea, etc.). El uso de xargs abre el camino para comportamientos más complejos (incluso aquellos que no tienen nada que ver con el resultado sí)yes
.C, 35 caracteres
El programa se ejecuta solo. No estoy seguro de si esto se considera recurrencia o no.
fuente
exec
hace que el nuevo proceso reemplace al original, por lo que no hay una pila de llamadas que eventualmente regrese o se desborde.exec
reemplaza el proceso anterior. Tampoco se desbordará.C (con GCC incorporado - también parece funcionar con el sonido metálico)
Explicación:
main()
primeras llamadasframeloop(NULL)
. En este caso, use el__builtin_return_address()
incorporado para obtener la dirección de retorno (inmain()
) a la queframeloop()
volverá. Le devolvemos esta dirección.printf()
para mostrar que estamos girandoframeloop()
con la dirección de retorno de la llamada anterior. Buscamos en la pila la dirección de retorno actual y, cuando la encontramos, sustituimos la dirección de retorno anterior.frameloop()
llamada. Pero dado que la dirección de devolución fue pirateada arriba, terminamos regresando al punto enmain()
el que debería regresar la primera llamada. Así terminamos en un bucle.La búsqueda de la dirección de retorno en la pila sería, por supuesto, más limpia como un bucle, pero desenrollé algunas iteraciones en aras de que no haya ningún bucle.
Salida:
fuente
setjmp()
/longjmp()
. Estos no están en el estándar c, pero están en la biblioteca estándar . Sin embargo, tuve ganas de mezclar la pila manualmente hoy ;-)Haskell
El siguiente código no contiene ninguna función recursiva (incluso indirectamente), no tiene primitiva de bucle y no llama a ninguna función recursiva incorporada (solo usa
IO
la salida y el enlace), pero repite una acción dada de manera indefinida:La función
extract
no llama a nada,yc
solo llamaextract
ymain
llama soloyc
yputStrLn
y>>
, que no son recursivas.Explicación: El truco está en el tipo de datos recursivo
Strange
. Es un tipo de datos recursivo que se consume a sí mismo, lo que, como se muestra en el ejemplo, permite la repetición arbitraria. Primero, podemos construirextract x
, que esencialmente expresa la auto aplicaciónx x
en el cálculo lambda sin tipo. Y esto permite construir el combinador Y definido comoλf.(λx.f(xx))(λx.f(xx))
.Actualización: como se sugiere, estoy publicando una variante que está más cerca de la definición de Y en el cálculo lambda sin tipo:
fuente
let
enlace y definirloyc f = extract $ C $ f.extract
, yalet
que podría decirse que es una característica del lenguaje que permite la recursividad (la clásicalet x = x in x
). Esto también reduce algunos caracteres :)yc = extract . C . (.extract)
Y
.C ++
Lo siguiente genera una cuenta regresiva de 10 a "¡Despegue!" usando metaprogramación de plantilla.
Puede parecer un ejemplo clásico de recursión, pero en realidad no lo es, al menos técnicamente, según su definición. El compilador generará diez funciones diferentes .
countdown<10>
imprime "T menos 10" y luego llamacountdown<9>
, y así sucesivamente hastacountdown<0>
, que imprime "¡Despegue!" y luego regresa La recursión ocurre cuando compila el código, pero el ejecutable no contiene ninguna estructura de bucle.En C ++ 11 se pueden lograr efectos similares usando la
constexpr
palabra clave, como esta función factorial. (No es posible implementar el ejemplo de cuenta regresiva de esta manera, ya que lasconstexpr
funciones no pueden tener efectos secundarios, pero creo que podría ser posible en el próximo C ++ 14).De nuevo, esto realmente se parece a la recursividad, pero el compilador se expandirá a cabo
factorial(10)
en10*9*8*7*6*5*4*3*2*1
, y luego, probablemente, reemplazarlo con un valor constante de3628800
, por lo que el ejecutable no contendrá ningún bucle o código recursivo.fuente
3628800
directamente sin un forma intermediaconstexpr
fue diseñado específicamente para hacer que (algunos aspectos de) la metaprogramación de plantillas sea obsoleta, por lo que definitivamente vale la pena mencionarlo en una publicación sobre el tema.&countdown<N-1> != &countdown<N>
.Java
Juguemos con el cargador de clases Java y configúrelo como su propio padre:
Este bucle es realmente tan fuerte que tendrá que usar un
kill -9
para detenerlo :-)Utiliza el 100,1% de la CPU de mi Mac.
Puede intentar mover
System.out
al final de la función principal para experimentar un comportamiento divertido alternativo.fuente
CSharp
Uno más e igualmente malvado ::
Esto no es recursividad ... esta es la reificación de plantillas de código. Si bien parece que estamos llamando al mismo método, el tiempo de ejecución crea constantemente nuevos métodos. Usamos el parámetro tipo de int, ya que esto realmente lo obliga a crear un tipo completamente nuevo y cada instancia del método tiene que crear un nuevo método. No puede compartir código aquí. Eventualmente, matamos la pila de llamadas mientras espera infinitamente el regreso de int que prometimos pero que nunca cumplimos. De manera similar, seguimos escribiendo el tipo que creamos para mantenerlo interesante. Básicamente, cada C que llamamos es un método totalmente nuevo que solo tiene el mismo cuerpo. Esto no es realmente posible en un lenguaje como C ++ o D que hace sus plantillas en tiempo de compilación. Como C # JIT es súper vago, solo crea estas cosas en el último momento posible. Así,
fuente
Redcode 94 (Core War)
MOV 0, 1
Copia la instrucción en la dirección cero a la dirección uno. Debido a que en Core War todas las direcciones son relativas a la dirección actual de la PC y modulan el tamaño del núcleo, este es un bucle infinito en una sola instrucción sin salto.
Este programa (guerrero) se llama " Imp " y fue publicado por primera vez por AK Dewdney.
fuente
SPL 0, 0; MOV 1, -2
verdad.Dardo
Supongo que esta sería la forma clásica de hacer recursividad sin ninguna función recursiva real. Ninguna función a continuación se refiere a sí misma por su nombre, directa o indirectamente.
(Pruébelo en dartpad.dartlang.org )
fuente
JS
No muy original pero pequeño. 20 caracteres
fuente
,1
y aún funcionará,setInterval
no es una declaración; Es solo una función. Se usa dentro de una declaración de expresión, y si no podemos usar declaraciones de expresión, entonces ni siquiera lo sé.Señales en C
El comportamiento de este programa obviamente es muy indefinido, pero hoy, en mi computadora, sigue imprimiendo "¡Hola, mundo!".
fuente
Emacs Lisp
Este es un buen momento para mostrar el poderoso diseño de Lisp donde "el código es datos y los datos son código". Por supuesto, estos ejemplos son muy ineficientes y esto nunca debe usarse en un contexto real.
Las macros generan código que es una versión desenrollada del supuesto bucle y ese código generado es lo que se evalúa en tiempo de ejecución.
Repetirlo: le permite recorrer N veces
prueba de repetición:
repetir-con-índice:
Esta macro es similar,
repeat-it
pero en realidad funciona igual que la macro de bucle común,do-times
le permite especificar un símbolo que estará vinculado al índice del bucle. Utiliza un símbolo de tiempo de expansión para garantizar que la variable de índice esté configurada correctamente al comienzo de cada ciclo, independientemente de si modifica o no su valor durante el cuerpo del ciclo.prueba de repetir con índice:
Esta prueba muestra que:
El cuerpo evalúa N veces
la variable de índice siempre se establece correctamente al comienzo de cada iteración
cambiar el valor de un símbolo llamado "reserva" no alterará el índice
fuente
Cálculo lambda sin tipo
fuente
Haskell, 24 personajes
o en forma condensada, con 24 caracteres
(aunque se cambia el texto, esto seguirá en bucle; esto imprimirá dos comillas y una nueva línea infinitamente)
explicación: print "abc" es básicamente una acción de E / S que simplemente imprime "abc".
repetir es una función que toma un valor x y devuelve una lista infinita hecha de solo x.
secuencia_ es una función que toma una lista de acciones de E / S y devuelve una acción de E / S que realiza todas las acciones secuencialmente.
así que, básicamente, este programa hace una lista infinita de comandos de impresión "abc" y los ejecuta repetidamente. sin bucles ni recursividad.
fuente
repeat
que seríaa programming language statement which allows code to be repeatedly executed
.fix(print"">>)
, esto tampoco implica funciones de repetición explícitamente nombradas.ASM (x86 + E / S para Linux)
No importa cuánto batallarán sus insignificantes lenguajes de alto nivel, seguirá siendo solo una manipulación oculta del puntero de instrucción. Al final, será una especie de "goto" (jmp), a menos que esté lo suficientemente aburrido como para desenrollar el bucle en tiempo de ejecución.
Puedes probar el código en Ideone
También puede consultar una versión más refinada de esta idea en el código DOS de Matteo Italia .
Comienza con una cadena de 0..9 y la reemplaza con A..J, no se utilizan saltos directos (así que digamos que no ocurrió "goto"), tampoco recurrencia.
El código probablemente podría ser más pequeño con algún cálculo de abuso de dirección, pero trabajar en el compilador en línea es molesto, así que lo dejaré como está.
Parte central:
Código completo
fuente
C preprocesador
Una pequeña "técnica" que se me ocurrió durante un desafío de ofuscación. No hay recursión de funciones, pero hay ... ¿recursividad de archivos?
noloop.c:
Escribí / probé esto usando gcc. Obviamente, su compilador debe admitir la
__INCLUDE_LEVEL__
macro (o, alternativamente, la__COUNTER__
macro con algunos ajustes) para que esto se compile. Debería ser bastante obvio cómo funciona esto, pero por diversión, ejecute el preprocesador sin compilar el código (use el-E
indicador con gcc).fuente
PHP
Aquí hay uno con PHP. Incluye bucles al incluir el mismo archivo hasta que el contador alcance $ max:
Lo mismo que un bucle for:
fuente
header("Location: .?x=".$_GET['x']+1);
cuenta como recursividad?Pitón
El siguiente código no contiene ninguna función recursiva (directa o indirecta), no tiene primitiva de bucle y no llama a ninguna función incorporada (excepto
print
):Imprime "¡Hola mundo!" un número dado de veces
Explicación: La función
z
implementa el estricto combinador de punto fijo Z , que (aunque no está definido recursivamente) permite expresar cualquier algoritmo recursivo.fuente
g
mucho indirectamente recursivo.g
llama eso que llama deg
nuevo? Por supuesto que el truco es la autoaplicacióng(g)
, pero no hay recurrencia involucrada. ¿Realmente llamaríasg
indirectamente recursivo si no lo has vistog(g)
? Esta es la forma estándar de hacerlo en idiomas que no permiten definiciones recursivas, como el cálculo lambda.g
como argumentox
y luego llamax(x)
.código máquina z80
En un entorno donde puede ejecutar en cada dirección y asignar ROM en cualquier lugar, asigne 64kb de ROM llenos de ceros a todo el espacio de direcciones.
Lo que hace: nada. Repetidamente.
Cómo funciona: el procesador comenzará a ejecutarse, el byte
00
es unanop
instrucción, por lo que simplemente continuará, alcanzará la dirección$ffff
, se ajustará$0000
y continuará ejecutandonop
s hasta que lo reinicie.Para hacerlo un poco más interesante, llene la memoria con algún otro valor (tenga cuidado de evitar las instrucciones de control de flujo).
fuente
Perl-regex
manifestación
o pruébalo como:
El
(?!)
nunca coincide. Entonces, el motor de expresiones regulares intenta hacer coincidir cada posición de ancho cero en la cadena coincidente.El
(q x x x 10)
es el mismo que(" " x 10)
- repita lasspace
diez veces.Editar: cambió los "caracteres" a posiciones de ancho cero para ser más precisos para una mejor comprensión. Vea las respuestas a esta pregunta de stackoverflow .
fuente
T-SQL -12
fuente
GO
es en realidad una directiva SSMS, por lo que no puede colocarla en objetos con script T-SQL, como por ejemplo un procedimiento almacenado.C#
Imprime todos los enteros desde uint.MaxValue a 0.
fuente
JS (en navegador)
¿Qué tal esto?
Imprime la hora actual y vuelve a cargar la página.
fuente
[Exception... "The operation is insecure." code: "18" nsresult: "0x80530012 (SecurityError)" location: "<unknown>"]