Uma pergunta semelhante a essa foi feita há alguns anos , mas essa é ainda mais complicada.
O desafio é simples. Escreva um programa (no idioma de sua escolha) que repetidamente executa o código sem o uso de estruturas de repetição, como while
, for
, do while
, foreach
ou goto
( Então para todos os nitpickers, você não pode usar um loop ). No entanto, a recursão não é permitida, na função que se chama de sentido (veja a definição abaixo) . Isso tornaria esse desafio fácil demais.
Não há restrições sobre o que precisa ser executado no loop, mas poste uma explicação com sua resposta para que outras pessoas possam entender exatamente o que está sendo implementado.
Para aqueles que podem ficar de fora das definições, a definição de um loop para esta pergunta é:
A programming language statement which allows code to be repeatedly executed.
E a definição de recursão para esta pergunta será sua definição de função recursiva padrão:
A function that calls itself.
O vencedor será a resposta que mais votou no dia 16 de julho às 10h, horário do leste. Boa sorte!
ATUALIZAR:
Para acalmar a confusão que ainda está sendo expressa, isso pode ajudar:
Regras conforme indicado acima:
- Não use loops ou vá para
- Funções não podem se chamar
- Faça o que quiser no 'loop'
Se você deseja implementar algo e as regras não o proíbem explicitamente, vá em frente e faça-o. Muitas respostas já dobraram as regras.
fonte
function A
chamadasfunction B
efunction B
chamadasfunction A
enquanto 1 das funções executa alguma coisa. Desde que a função não chamar a si mesma que deveria ser válido com base nos critérios ^ ^.rep(f){f();f();}
- esta é uma declaração (uma declaração de função é uma declaração em alguns idiomas) que permite executar código repetidamente. É proibido? Você pede código para implementar um loop. Se esse código é sintaticamente uma instrução, você simplesmente não o permitiu. Outro exemplo:f(b) { b(); g(b); }; g(b) { f(b); }
. Eu diria quef
é uma função recursiva (sendo mutuamente recursiva comg
). É proibido?Respostas:
Rubi
Demo
Limpa a garganta, imprime "Banana" 3070 vezes e também coloca "Laranja, que bom que eu não disse banana?".
Isso usa a ridícula funcionalidade de definição de método just-in-time do Ruby para definir todos os métodos que estão alfabeticamente entre as palavras 'ahem' e 'also' ("ahem", "ahen", "aheo", "ahep", "aheq", "aher", "ahes", "ahet", "aheu", "ahev" ...) para imprimir primeiro Banana e depois chamar o próximo na lista.
fonte
String#next
que é chamado demethod_missing
funções mais ou menos como adicionar 1 a um número, exceto que funciona com todos os caracteres alfanuméricos (e não alnums, se forem os únicos caracteres da string). Veja ruby-doc.org/core-2.1.2/String.html#method-i-nextb.my_tag
. Também é usado em modelos ActiveRecord ouOpenStruct
. Em 'Wat talk', ele diz que globalmethod_missing
é ruim, mas o escopo é impressionante.Python - 16
ou qualquer outro idioma com avaliação.
fonte
"print 1;"
), duplica-a 9 vezes (*9
) e depois executa a string resultante (exec
). Repetir um pedaço de código sem realmente fazer loop.exec
queeval
ou oprint
queecho
.CSharp
Expandi o código para uma forma mais legível, pois isso não é mais um código de golfe e adicionei um contador de incremento para que as pessoas possam realmente ver que esse programa faz alguma coisa.
(Nunca faça isso por favor).
No início, criamos uma nova instância da
P
classe, que quando o programa tenta sair chama o GC, que chama o finalizador, que cria uma nova instância daP
classe, e quando tenta limpar, cria uma novaP
que chama o finalizador. .O programa acaba morrendo.
Edit: Inexplicavelmente, isso é executado apenas cerca de 45k vezes antes de morrer. Não sei bem como o GC descobriu meu complicado laço infinito, mas conseguiu. O curto é que parece que não entendi e o encadeamento foi morto após cerca de 2 segundos de execução: https://stackoverflow.com/questions/24662454/how-does-a-garbage-collector-avoid-an -infinite-loop-here
Edit2: Se você acha que isso é muito parecido com recursão, considere minha outra solução: https://codegolf.stackexchange.com/a/33268/23300
Ele usa a reificação de métodos genéricos para que, em tempo de execução, gere constantemente novos métodos e cada método no termo chame um método recém-criado. Também evito usar
reference
parâmetros de tipo, pois normalmente o tempo de execução pode compartilhar o código desses métodos. Com umvalue
parâmetro de tipo, o tempo de execução é forçado a criar um novo método.fonte
Finalize
por vezes, são chamadosfinalizer
. Em C # real, você deve usar oIDisposable
padrão.Befunge
O bom e velho Befunge produz 0 (de uma pilha vazia) praticamente para sempre, à medida que as linhas se espalham.
fonte
JS
(f=function(){ console.log('hi!'); eval("("+f+")()") })()
Função divertida!
Uma função que cria outra função com o mesmo corpo que ela mesma e a executa.
Ele será exibido hi no final quando o limite da pilha for atingido e a coisa toda entrar em colapso.
Isenção de responsabilidade: você não poderá fazer nada no seu navegador até que o limite da pilha seja atingido.
E outro, mais mal :function f(){ var tab = window.open(); tab.f = f; tab.f()}()
Ele cria uma função que abre uma janela, depois cria uma função nessa janela que é cópia da função e, em seguida, executa-a.
Isenção de responsabilidade: se você permitir a abertura de pop-ups, a única maneira de concluir isso será reiniciar o computadorfonte
f
no final da sua segunda função. Deve estar}f()
no final.montagem x86 / DOS
Como funciona
fonte
Java
Direto do XKCD
É um jogo interminável de captura entre pai e filho!
O destino de
CHILD
é definido comoPARENT
e o destino dePARENT
é oCHILD
. Quando asPARENT
chamadasAIM
, ele lança a instância daBALL
classe e é capturado pela instrução catch. A instrução catch chama entãoPARENT.TARGET.AIM
onde está o destinoCHILD
. ACHILD
instância faz o mesmo e "joga a bola de volta" para o pai.fonte
TARGET.AIM(B);
no métodoAIM
é uma chamada recursiva. Portanto, isso viola a regra "funções não podem se chamar".Bash, 3 caracteres
yes retornará repetidamente 'y' ao console
Editar: todos são incentivados a editar esta linha:
(graças a Olivier Dulac)
fonte
yes
é um comando bash que imprime a palavra sim até que ela seja morta ou o fluxo se torne fechado. Se estiver escrevendo na tela, nunca irá parar até que você a mate. É meio trapaceiro, já que é um comando que consiste basicamente em um loop sobre printf.yes
para manter algum outro loop.yes something | xargs someaction
sem recursão (você pode até adicionar -n 1 ao xargs para ter apenas 1 "algo" por linha, etc). Utilizando xargs abre o caminho para comportamentos mais complexos (mesmo os que não têm absolutamente nada a ver com a saída sim)yes
.C, 35 caracteres
O programa se executa. Não tenho certeza se isso é considerado recursão ou não.
fonte
exec
faz com que o novo processo substitua o original, então não há pilha de chamadas que retornará ou excederá.exec
substitui o processo anterior. Também não transbordará.C (com built-in GCC - também parece funcionar com clang)
Explicação:
main()
primeiras chamadasframeloop(NULL)
. Nesse caso, use o__builtin_return_address()
builtin para obter o endereço de retorno (inmain()
) ao qualframeloop()
retornará. Retornamos este endereço.printf()
para mostrar que estamos dando laçosframeloop()
com o endereço de retorno da chamada anterior. Examinamos na pilha o endereço de retorno atual e, quando o encontramos, substituímos o endereço de retorno anterior.frameloop()
chamada. Mas como o endereço de retorno foi hackeado acima, acabamos retornando ao ponto emmain()
que a primeira chamada deve retornar. Assim, acabamos em um loop.A busca pelo endereço de retorno na pilha seria, obviamente, mais limpa como um loop, mas desenrolei algumas iterações para não causar loop algum.
Resultado:
fonte
setjmp()
/longjmp()
. Eles não estão no padrão c, mas estão na biblioteca padrão . Eu me senti como munging a pilha hoje manualmente embora ;-)Haskell
O código a seguir não contém nenhuma função recursiva (mesmo que indiretamente), nem primitivo em loop e não chama nenhuma função recursiva
IO
interna (usa apenas a saída e a ligação de), mas repete uma determinada ação indefinidamente:A função
extract
não chama nada,yc
chama apenasextract
emain
chama apenasyc
eputStrLn
e>>
, que não são recursivos.Explicação: O truque está no tipo de dados recursivo
Strange
. É um tipo de dados recursivo que se consome, o que, como mostrado no exemplo, permite repetições arbitrárias. Primeiro, podemos construirextract x
, que expressa essencialmente a autoaplicaçãox x
no cálculo lambda não tipado. E isso permite construir o combinador Y definido comoλf.(λx.f(xx))(λx.f(xx))
.Atualização: Como sugerido, estou postando uma variante mais próxima da definição de Y no cálculo lambda sem tipo:
fonte
let
ligação e definiryc f = extract $ C $ f.extract
, já que alet
ligação pode ser um recurso de linguagem que permite recursão (o clássicolet x = x in x
). Isso também reduz alguns caracteres :)yc = extract . C . (.extract)
Y
.C ++
O seguinte gera uma contagem regressiva de 10 a "Decolar!" usando metaprogramação de modelo.
Pode parecer um exemplo clássico de recursão, mas na verdade não depende, pelo menos tecnicamente, da sua definição. O compilador irá gerar dez funções diferentes .
countdown<10>
imprime "T menos 10" e, em seguidacountdown<9>
, chama e assim por diante atécountdown<0>
, que imprime "Decolar!" e depois retorna. A recursão ocorre quando você compila o código, mas o executável não contém nenhuma estrutura de loop.No C ++ 11, é possível obter efeitos semelhantes usando a
constexpr
palavra - chave, como esta função fatorial. (Não é possível implementar o exemplo da contagem regressiva dessa maneira, pois asconstexpr
funções não podem ter efeitos colaterais, mas acho que pode ser possível no próximo C ++ 14.)Novamente, isto realmente se parece recursão, mas o compilador irá expandir para fora
factorial(10)
para10*9*8*7*6*5*4*3*2*1
, em seguida, provavelmente substituí-lo por um valor constante de3628800
, assim que o executável não irá conter qualquer looping ou código recursiva.fonte
3628800
diretamente sem um forma intermediária.constexpr
foi projetado especificamente para tornar obsoletos (alguns aspectos da) metaprogramação de modelos, então parece definitivamente vale a pena mencionar em um post sobre o assunto.&countdown<N-1> != &countdown<N>
.Java
Vamos jogar com o carregador de classes Java e configurá-lo como seu próprio pai:
Esse loop é realmente tão forte que você terá que usar um
kill -9
para pará-lo :-)Ele usa 100,1% da CPU do meu Mac.
Você pode tentar mover o
System.out
final da função principal para experimentar um comportamento engraçado alternativo.fonte
CSharp
Mais um e igualmente perverso ::
Isso não é recursão ... é reificação de modelos de código. Enquanto parece que estamos chamando o mesmo método, o tempo de execução está constantemente criando novos métodos. Usamos o parâmetro type de int, pois isso o obriga a criar um novo tipo inteiro e cada instância do método precisa lançar um novo método. Não pode codificar compartilhamento aqui. Eventualmente, eliminamos a pilha de chamadas, pois ela espera infinitamente pelo retorno de int que prometemos, mas nunca entregamos. De maneira semelhante, continuamos escrevendo o tipo que criamos para mantê-lo interessante. Basicamente, cada C que chamamos é um método totalmente novo que apenas tem o mesmo corpo. Isso não é realmente possível em uma linguagem como C ++ ou D que executa seus modelos em tempo de compilação. Como o C # JIT é super preguiçoso, ele só cria esse material no último momento possível. Portanto,
fonte
Redcode 94 (Guerra Principal)
MOV 0, 1
Copia a instrução no endereço zero para o endereço um. Como no Core War todos os endereços são relativos ao endereço atual do PC e modulam o tamanho do núcleo, esse é um loop infinito em uma instrução sem salto.
Este programa (guerreiro) é chamado " Imp " e foi publicado pela primeira vez por AK Dewdney.
fonte
SPL 0, 0; MOV 1, -2
fato.Dardo
Eu acho que essa seria a maneira clássica de fazer recursão sem nenhuma função recursiva real. Nenhuma função abaixo se refere a si mesma pelo nome, direta ou indiretamente.
(Experimente em dartpad.dartlang.org )
fonte
JS
Não é muito original, mas pequeno. 20 caracteres.
fonte
,1
e ele ainda funciona, #setInterval
não é uma afirmação; é apenas uma função. É usado dentro de uma declaração de expressão e, se não podemos usar declarações de expressão, simplesmente não sei mais.Sinais em C
O comportamento deste programa é obviamente muito indefinido, mas hoje, no meu computador, ele continua imprimindo "Olá, mundo!".
fonte
Emacs Lisp
Este é um ótimo momento para mostrar o design poderoso do Lisp, onde "código é dados e dados são código". É verdade que esses exemplos são muito ineficientes e nunca devem ser usados em um contexto real.
As macros geram código que é uma versão desenrolada do suposto loop e esse código gerado é o que é avaliado em tempo de execução.
repeat-it: permite repetir N vezes
teste de repetição:
repita com índice:
Essa macro é semelhante,
repeat-it
mas na verdade funciona exatamente como a macro comum de loopdo-times
, permitindo especificar um símbolo que será vinculado ao índice do loop. Ele usa um símbolo de tempo de expansão para garantir que a variável de índice seja definida corretamente no início de cada loop, independentemente de você modificar ou não seu valor durante o corpo do loop.teste de repetição com índice:
Este teste mostra que:
O corpo avalia N vezes
a variável de índice é sempre definida corretamente no início de cada iteração
alterar o valor de um símbolo chamado "fallback" não interfere no índice
fonte
Cálculo lambda não tipado
fonte
Haskell, 24 caracteres
ou de forma condensada, com 24 caracteres
(embora o texto seja alterado, isso continuará em loop - isso imprimirá duas aspas e uma nova linha infinitamente)
explicação: print "abc" é basicamente uma ação de E / S que apenas imprime "abc".
repeat é uma função que recebe um valor x e retorna uma lista infinita composta apenas por x.
sequence_ é uma função que pega uma lista de ações de E / S e retorna uma ação de E / S que executa todas as ações sequencialmente.
portanto, basicamente, este programa cria uma lista infinita de comandos "abc" de impressão e os executa repetidamente. sem loops ou recursão.
fonte
repeat
que seriaa programming language statement which allows code to be repeatedly executed
.fix(print"">>)
, isso também não envolve funções de repetição nomeadas explicitamente.ASM (x86 + E / S para Linux)
Não importa o quanto suas linguagens insignificantes de alto nível terão dificuldade, ainda será apenas a manipulação de ponteiros de instruções ocultas. No final, será algum tipo de "goto" (jmp), a menos que você esteja entediado o suficiente para desenrolar o loop no tempo de execução.
Você pode testar o código no Ideone
Você também pode conferir uma versão mais refinada dessa ideia em código DOS da Matteo Italia .
Começa com uma cadeia de 0..9 e a substitui por A..J, sem saltos diretos usados (digamos que não houve "goto"), nem recorrência.
O código provavelmente poderia ser menor com algum abuso de cálculo de endereço, mas trabalhar no compilador on-line é incômodo, portanto, deixarei como está.
Parte principal:
Código inteiro
fonte
Pré-processador C
Uma pequena "técnica" que eu inventei durante um desafio de ofuscação. Não há recursão de função, mas há ... recursão de arquivo?
noloop.c:
Eu escrevi / testei isso usando o gcc. Obviamente, seu compilador precisa oferecer suporte à
__INCLUDE_LEVEL__
macro (ou alternativamente à__COUNTER__
macro com alguns ajustes) para que isso seja compilado. Deve ser bastante óbvio como isso funciona, mas, por diversão, execute o pré-processador sem compilar o código (use o-E
sinalizador com gcc).fonte
PHP
Aqui está um com PHP. Loops incluindo o mesmo arquivo até o contador atingir $ max:
O mesmo que um loop for:
fonte
header("Location: .?x=".$_GET['x']+1);
contado como recursão?Pitão
O código a seguir não contém nenhuma função recursiva (direta ou indireta), nenhuma primitiva de loop e não chama nenhuma função interna (exceto
print
):Imprime "Olá, mundo!" um determinado número de vezes.
Explicação: A função
z
implementa o combinador estrito de ponto fixo Z , que (embora não seja definido recursivamente) permite expressar qualquer algoritmo recursivo.fonte
g
muito indiretamente recursiva.g
chama isso deg
novo? É claro que o truque é a auto-aplicaçãog(g)
, mas não há recursão envolvida. Você realmente chamaria deg
recursiva indireta se não a visseg(g)
? Essa é a maneira padrão de como fazê-lo em linguagens que não permitem definições recursivas, como o cálculo lambda.g
como argumentox
e depois chamax(x)
.código de máquina z80
Em um ambiente em que você pode executar em todos os endereços e mapear a ROM em qualquer lugar, mapeie 64kb de ROM preenchidos com zeros para todo o espaço de endereço.
O que faz: nada. Repetidamente.
Como funciona: o processador começará a executar, o byte
00
é umanop
instrução, portanto, continuará, alcançará o endereço$ffff
, contornará$0000
e continuará executandonop
s até que você o redefina.Para torná-lo um pouco mais interessante, preencha a memória com algum outro valor (tenha cuidado para evitar instruções de controle de fluxo).
fonte
Perl-regex
demonstração
ou tente como:
O
(?!)
nunca combina. Portanto, o mecanismo regex tenta corresponder a cada posição de largura zero na sequência correspondente.O
(q x x x 10)
é o mesmo que(" " x 10)
- repita ospace
dez vezes.Editar: alterou os "caracteres" para zero posições de largura para ser mais preciso para melhor compreensão. Veja as respostas para esta pergunta sobre o stackoverflow .
fonte
T-SQL -12
fonte
GO
é realmente uma diretiva SSMS, e é por isso que você não pode colocá-la em objetos com script T-SQL, como um procedimento armazenado.C #
Imprime todos os números inteiros de uint.MaxValue para 0.
fonte
JS (no navegador)
Que tal agora?
Imprime a hora atual e recarrega a página.
fonte
[Exception... "The operation is insecure." code: "18" nsresult: "0x80530012 (SecurityError)" location: "<unknown>"]