Loop sem 'loop' [fechado]

85

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, foreachou 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.

CailinP
fonte
27
Para quem quer um truque fácil, não posso me incomodar em publicá-lo: P Basta fazer 2 funções, function Achamadas function Be function Bchamadas function Aenquanto 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 ^ ^.
Teun Pronk
2
"Mudou o concurso de popularidade para se concentrar na criatividade" Mudar a questão é trapaça!
CousinCocaine
4
A definição de "recursão" não é muito útil. Seria melhor não permitir funções recursivas , que são funções que se referem a si mesmas, direta ou indiretamente.
lrn
3
O que não está claro são as "definições" de construtor de loop e recursão. Nem são muito precisos. Exemplo: 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 que fé uma função recursiva (sendo mutuamente recursiva com g). É proibido?
lrn
3
@CailinP, o que eu estou " pendurado sobre " é que perguntas no site deve ser sobre o tema para o site: isso significa ter uma especificação clara, objectiva, que esta questão não.
Peter Taylor

Respostas:

258

Rubi

def method_missing(meth,*args)
  puts 'Banana'
  send(meth.next)
end

def also
  puts "Orange you glad I didn't say banana?"
end

ahem

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.

histocrata
fonte
4
Eventualmente, atinge "também", que é definido e, portanto, não está ausente.
Histocrat 9/07/2014
77
Isso é histérico.
Michael B
4
@barrycarter: No Ruby, String#nextque é chamado de method_missingfunçõ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-next
3Doubloons
2
@NickT é utilizável em classes como construtores XML, onde você pode criar qualquer tag apenas por b.my_tag. Também é usado em modelos ActiveRecord ou OpenStruct. Em 'Wat talk', ele diz que global method_missingé ruim, mas o escopo é impressionante.
Hauleth
2
Lembro-me de um comentário de idade em outro programa Ruby: "Eu gosto dele porque ele tem meth"
sagar vidya
82

Python - 16

ou qualquer outro idioma com avaliação.

exec"print 1;"*9
Vetorizado
fonte
Você pode descrever o que o seu programa faz?
CailinP
10
Ele pega uma string ( "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.
scragar
12
Yay para multiplicação de cordas!
Thane Brimhall
2
Também funciona em Ruby se alterar o execque eval ou o printque echo.
Ajedi32
80

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.

class P{
    static int x=0;
    ~P(){
        System.Console.WriteLine(++x);
        new P();
    }
    static void Main(){
        new P();
    }
}

(Nunca faça isso por favor).

No início, criamos uma nova instância da Pclasse, que quando o programa tenta sair chama o GC, que chama o finalizador, que cria uma nova instância da Pclasse, e quando tenta limpar, cria uma nova Pque 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 referenceparâmetros de tipo, pois normalmente o tempo de execução pode compartilhar o código desses métodos. Com um valueparâmetro de tipo, o tempo de execução é forçado a criar um novo método.

Michael B
fonte
20
Eu nem sabia que o C # tinha destruidores. +1 por me ensinar.
seequ
4
@TheRare, sim, mas eles são de natureza não determinística e nunca podem ser chamados durante a execução de um programa. Eles são implementados como uma substituição do método virtual e, Finalizepor vezes, são chamados finalizer. Em C # real, você deve usar o IDisposablepadrão.
Michael B
Parece que há um tempo limite que ocorre em algum momento. Eu não acho que é o GC que está interrompendo seu ciclo, mas o sistema operacional que decide que seu programa está demorando muito para terminar.
precisa saber é o seguinte
Eu acho que esse é realmente o tempo de execução que decide matar o programa, não necessariamente o sistema operacional. O thread do coletor de lixo chamado no final do programa recebe um limite de tempo fixo de ~ 2 segundos antes de ser morto.
Michael B
Com algumas pequenas modificações (não deixando o programa terminar, liberando o primeiro objeto P para o GC e chamando repetidamente GC.Collect), posso executá-lo indefinidamente.
precisa saber é o seguinte
53

Befunge

.

O bom e velho Befunge produz 0 (de uma pilha vazia) praticamente para sempre, à medida que as linhas se espalham.

Le Canard fou
fonte
1
Ha! Eu amo truques como este
CailinP
47

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 computador

eithed
fonte
5
Isso é muito mal, com certeza;)
CailinP
28
@CailinP Pretty eval, com certeza.
seequ
Acho que você está perdendo um fno final da sua segunda função. Deve estar }f()no final.
Chirag Bhatia - chirag64
2
Infelizmente, notei porque tentei. : P
Chirag Bhatia - chirag64
7
-1 - isso é apenas recursão.
user253751
39

montagem x86 / DOS

    org 100h

start:
    mov dx,data
    mov ah,9h
    int 21h
    push start
    ret

data:
    db "Hello World!",10,13,"$"

Eu disse que não houve recursão invertida da cauda ? Eu fiz? madame mim dragões roxos

Como funciona

A retinstrução, usada para retornar de uma função, na verdade exibe o endereço de retorno da pilha (que normalmente é colocada lá pelo correspondente call) e salta para ela. Aqui, em cada iteração, temos pusho endereço do ponto de entrada na pilha antes de retornar, gerando um loop infinito.

Matteo Italia
fonte
Fiquei me perguntando se isso era possível na montagem.
Ian D. Scott
2
Mexa com a pilha por sua conta e risco . Aqui estão os dragões ;-)
Digital Trauma
1
Eu estava indo para chamar codegolf.stackexchange.com/a/34295/11259 como um dup deste, mas vejo que é realmente a resposta anterior
Digital Trauma
@DigitalTrauma: sim, notei depois que publiquei minha entrada, mas fui anexada à foto de Madame Mim. :-) Felizmente, existem algumas diferenças (a dele é um pouco mais ofuscada e funciona no Linux de 32 bits, a minha é reproduzida diretamente no DOS e não tem outro salto), se ninguém tiver alguma objeção, eu deixaria isso aqui de qualquer maneira.
Matteo Italia
@MatteoItalia Não ofuscado, apenas péssimo;) (tho "add eax, 4" me confundiu também, eu não consegui encontrar a tabela de tamanho de código de código, então apenas adivinhei o tamanho). Eu fiz isso no compilador online enquanto meu projeto de trabalho estava sendo compilado, para que parecesse horrivelmente. Ótima idéia de usar "start:".
PTwr
37

Java

Direto do XKCD

União

É um jogo interminável de captura entre pai e filho!

O destino de CHILDé definido como PARENTe o destino de PARENTé o CHILD. Quando as PARENTchamadas AIM, ele lança a instância da BALLclasse e é capturado pela instrução catch. A instrução catch chama então PARENT.TARGET.AIMonde está o destino CHILD. A CHILDinstância faz o mesmo e "joga a bola de volta" para o pai.

Kirk Backus
fonte
3
Eu gosto daqueles quadrinhos!
Derek #
1
Seria melhor se a bola estivesse sendo lançada entre o pai e o filho. Como está, a bola é sempre jogada e apanhada pela mesma "pessoa".
Ajedi32
@ Ajedi32 Na verdade, parece que ele joga para frente e para trás; Pais TARGET é o filho, e o alvo do filho é pai. Objetivo é chamado de pai, que agonia a bola e tem o objetivo criança e jogar a bola, laço sugestão
Alex Coleman
12
@AlexColeman Esse código é análogo ao pai que joga a bola no ar, apanha-a e entrega-a à criança que faz o mesmo antes de devolver a bola ao pai e assim por diante.
Ajedi32
11
O comando TARGET.AIM(B);no método AIMé uma chamada recursiva. Portanto, isso viola a regra "funções não podem se chamar".
Theodore Norvell
31

Bash, 3 caracteres

yes

yes retornará repetidamente 'y' ao console

Editar: todos são incentivados a editar esta linha:

yes something | xargs someaction

(graças a Olivier Dulac)

PrimoCocaína
fonte
1
Por que isso continuará funcionando? não estou questionando, apenas tentando descobrir o porquê.
Teun Pronk
2
@TeunPronk 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.
scragar
1
Mais divertido seria usar yespara manter algum outro loop.
trlkly
3
@izkata: mas então você pode:: yes something | xargs someactionsem 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)
Olivier Dulac
4
@ Scragar você deveria ter respondido yes.
Davisales
28

C, 35 caracteres

main(int a,char**v){execv(v[0],v);}

O programa se executa. Não tenho certeza se isso é considerado recursão ou não.

kwokkie
fonte
4
recursão de cauda @mniip, então, se aplicada no nível do processo
Izkata
3
A recursão @ Izkata Tail ainda é recursiva, mas não é recursão. A recursão implica uma função (ou processo nesse caso) 'aguardando' por outra iteração de si mesma terminar. Nesse caso, execfaz com que o novo processo substitua o original, então não há pilha de chamadas que retornará ou excederá.
millinon
4
@millinon Em um idioma que suporta a otimização, a recursão final substitui a chamada anterior na pilha de chamadas, semelhante à maneira como execsubstitui o processo anterior. Também não transbordará.
Izkata
1
@millinon apenas para ser super pedante e prolongar a discussão, na linguagem de programação Scheme, essa otimização é um recurso de linguagem. É na especificação que se você fizer uma chamada de cauda-recursivo, o intérprete / compilador tem de reutilizar o último quadro de pilha. Isso ocorre porque o Scheme não possui estruturas de loop embutidas; portanto, a única maneira de implementar um loop no Scheme é fazer a recursão da cauda, ​​e seria meio ruim se você obtivesse estouros de pilha ao tentar fazer loop muitas vezes :)
Ord
2
Se você deseja pediatria, o Scheme não possui "otimização de chamada de cauda", possui "chamadas de cauda adequadas". Não é uma otimização, é um requisito básico do padrão de linguagem e não é permitido deixar de fornecê-lo; portanto, "otimização" (ou a sugestão de que tenha algo a ver com recursão) é um termo muito desencorajado.
Leushenko
28

C (com built-in GCC - também parece funcionar com clang)

  • Sem loops explícitos
  • Sem gotos explícitos
  • Sem recursão
  • Apenas uma boa bagunça antiquada com a pilha (crianças, não tente fazer isso em casa sem supervisão):
#include <stdio.h>

void *frameloop (void *ret_addr) {
    void **fp;
    void *my_ra = __builtin_return_address(0);

    if (ret_addr) {
        fp = __builtin_frame_address(0);
        if (*fp == my_ra) return (*fp = ret_addr);
        else fp++;
        if (*fp == my_ra) return (*fp = ret_addr);
        else fp++;
        if (*fp == my_ra) return (*fp = ret_addr);
        else fp++;
        if (*fp == my_ra) return (*fp = ret_addr);
        return NULL;
    } else {
        return (my_ra);
    }
}

int main (int argc, char **argv) {
    void *ret_addr;
    int i = 0;

    ret_addr = frameloop(NULL);
    printf("Hello World %d\n", i++);
    if (i < 10) {
        frameloop(ret_addr);
    }
}

Explicação:

  • main()primeiras chamadas frameloop(NULL). Nesse caso, use o __builtin_return_address()builtin para obter o endereço de retorno (in main()) ao qual frameloop()retornará. Retornamos este endereço.
  • printf() para mostrar que estamos dando laços
  • agora chamamos frameloop()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.
  • Em seguida, retornamos da 2ª frameloop()chamada. Mas como o endereço de retorno foi hackeado acima, acabamos retornando ao ponto em main()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:

$ CFLAGS=-g make frameloop
cc -g    frameloop.c   -o frameloop
$ ./frameloop 
Hello World 0
Hello World 1
Hello World 2
Hello World 3
Hello World 4
Hello World 5
Hello World 6
Hello World 7
Hello World 8
Hello World 9
$ 
Trauma Digital
fonte
2
legais! Eu me pergunto por que essas funções não fazem parte da especificação C? ;-D
Brian Minton
4
@BrianMinton Na verdade, algo semelhante deve ser possível com 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 ;-)
Digital Trauma
@BrianMinton Meu palpite é porque está nas especificações da CPU, o que torna a plataforma (hardware) dependente. E é bastante perigoso usar quando o stackframe é gerado automaticamente, não ficaria surpreso se o AV chorasse por esse código. Verifique isto ou isto para versões x86 asm.
PTwr
27

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 recursivaIO interna (usa apenas a saída e a ligação de), mas repete uma determinada ação indefinidamente:

data Strange a = C (Strange a -> a)

-- Extract a value out of 'Strange'
extract :: Strange a -> a
extract (x@(C x')) = x' x

-- The Y combinator, which allows to express arbitrary recursion
yc :: (a -> a) -> a
yc f =  let fxx = C (\x -> f (extract x))
        in extract fxx

main = yc (putStrLn "Hello world" >>)

A função extractnão chama nada, ycchama apenas extracte mainchama apenas yce putStrLne >>, 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 construir extract x, que expressa essencialmente a autoaplicação x xno 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:

data Strange a = C (Strange a -> a)

-- | Apply one term to another, removing the constructor.
(#) :: Strange a -> Strange a -> a
(C f) # x = f x
infixl 3 #

-- The Y combinator, which allows to express arbitrary recursion
yc :: (a -> a) -> a
yc f =  C (\x -> f (x # x)) # C (\x -> f (x # x))

main = yc (putStrLn "Hello world" >>)
Petr Pudlák
fonte
3
Estruturas de dados recursivas em vez de funções recursivas ... legais.
ApproachingDarknessFish
6
este está perto do meu coração, sendo alguém interessado em programação funcional total. Você acabou de mostrar como fazer o combinador Y com um tipo de dados negativamente recorrente. É por isso que os idiomas totais exigem que tipos recorrentes ocorram à direita da seta e por que as roseiras não são permitidas. Agradável! Eu fiz uma conta aqui apenas para fazer um voto positivo!
Jake
Você pode remover a letligação e definir yc f = extract $ C $ f.extract, já que a letligação pode ser um recurso de linguagem que permite recursão (o clássico let x = x in x). Isso também reduz alguns caracteres :)
Earth Engine
ou mesmoyc = extract . C . (.extract)
Earth Engine
@EarthEngine É verdade, eu só queria manter a estrutura mais próxima da definição original de Y.
Petr Pudlák
26

C ++

O seguinte gera uma contagem regressiva de 10 a "Decolar!" usando metaprogramação de modelo.

#include <iostream>

template<int N>
void countdown() {
    std::cout << "T minus " << N << std::endl;
    countdown<N-1>();
}

template<>
void countdown<0>() {
    std::cout << "Blast off!" << std::endl;
}

int main()
{
    countdown<10>();
    return 0;
}

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 seguida countdown<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 constexprpalavra - chave, como esta função fatorial. (Não é possível implementar o exemplo da contagem regressiva dessa maneira, pois as constexprfunções não podem ter efeitos colaterais, mas acho que pode ser possível no próximo C ++ 14.)

constexpr int factorial(int n)
{
    return n <= 1 ? 1 : (n * factorial(n-1));
}

Novamente, isto realmente se parece recursão, mas o compilador irá expandir para fora factorial(10)para 10*9*8*7*6*5*4*3*2*1, em seguida, provavelmente substituí-lo por um valor constante de 3628800, assim que o executável não irá conter qualquer looping ou código recursiva.

Nathaniel
fonte
4
O segundo deles é realmente uma recursão pura e simples, não uma metaprogramação. Primeiramente porque o compilador emitirá (no caso geral) um corpo de função regular para você usar com argumentos não constantes; e, em segundo lugar, porque, quando executa uma operação em tempo de compilação, não realiza nenhuma dessas coisas de "expansão" no estilo de modelo, executa uma avaliação no local padrão - a mesma que a do tempo de execução - para produzir 3628800diretamente sem um forma intermediária.
Leushenko
@Leushenko sim, eu sei. Mas, novamente, o exemplo de exemplo de modelo faz a mesma coisa - usa uma função recursiva em uma linguagem Turing-completa em tempo de compilação - a única diferença é que o constexpr one usa uma linguagem que se parece muito mais com C ++. Como em todas as respostas, este controla as regras, e estou sendo sincero. constexprfoi 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.
Nathaniel
1
+1: &countdown<N-1> != &countdown<N>.
Thomas Eding
21

Java

Vamos jogar com o carregador de classes Java e configurá-lo como seu próprio pai:

import java.lang.reflect.Field;

public class Loop {
    public static void main(String[] args) throws Exception {
        System.out.println("Let's loop");
        Field field = ClassLoader.class.getDeclaredField("parent");
        field.setAccessible(true);
        field.set(Loop.class.getClassLoader(), Loop.class.getClassLoader());

    }
}

Esse loop é realmente tão forte que você terá que usar um kill -9para pará-lo :-)

Ele usa 100,1% da CPU do meu Mac.

100,1% da CPU

Você pode tentar mover o System.outfinal da função principal para experimentar um comportamento engraçado alternativo.

Arnaud
fonte
ri muito. ficando java preso em si :)
masterX244
Adore o hack de carregamento recursivo da JVM.
Isiah Meadows
20

CSharp

Mais um e igualmente perverso ::

public class P{

    class A<B>{
        public static int C<T>(){
            System.Console.WriteLine(typeof(T));
            return C<A<T>>();
        }
    }
    public static void Main(){
        A<P>.C<int>();
    }
}

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,

Michael B
fonte
14

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.

amora
fonte
3
Diabretes marcham, preparam seus portões, preparam-nos ou serão esmagados.
10442 seequ
Pronto o seu SPL 0, 0; MOV 1, -2fato.
wberry
Bom, eu esperava que isso ainda não tivesse sido publicado. 1
mbomb007
14

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 )

// Strict fixpoint operator.
fix(f) => ((x)=>f(x(x))) ((x)=>(v)=>f(x(x))(v));
// Repeat action while it returns true.
void repeat(action) { fix((rep1) => (b) { if (b()) rep1(b); })(action); }

main() {
  int x = 0;
  repeat(() {  
    print(++x);
    return x < 10;
  });
}
lrn
fonte
6
O combinador Y?
Aditsu
5
Tecnicamente, acho que é o combinador Z porque é para uma linguagem estrita. O combinador Y requer uma linguagem lenta para evitar o desdobramento infinito. A única diferença é que a última parte é eta-expandida.
lrn
12

JS

Não é muito original, mas pequeno. 20 caracteres.

setInterval(alert,1)
xem
fonte
Na verdade, você pode remover ,1e ele ainda funciona, #
1166 Derek
@Derek 功夫 會 功夫 se eu fizer isso, eu só recebo um alerta no Firefox #
1111 xem
1
No chrome, funciona sem o último parâmetro. O código deve ser considerado válido se funcionar em pelo menos um ambiente.
Derek朕會功夫
3
@Derek 朕 會 功夫setIntervalnã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.
Keen
1
@Cory - Bem, eu acho que é válido então!
Derek朕會功夫
12

Sinais em C

#include <stdio.h>
#include <signal.h>

int main(void) {
    signal(SIGSEGV, main);
    *(int*)printf("Hello, world!\n") = 0;
    return 0;
}

O comportamento deste programa é obviamente muito indefinido, mas hoje, no meu computador, ele continua imprimindo "Olá, mundo!".

Thomas Padron-McCarthy
fonte
11

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

(defmacro repeat-it (n &rest body)
  "Evaluate BODY N number of times.
Returns the result of the last evaluation of the last expression in BODY."
  (declare (indent defun))
  (cons 'progn (make-list n (cons 'progn body))))

teste de repetição:

;; repeat-it test
(progn
  (setq foobar 1)

  (repeat-it 10
    (setq foobar (1+ foobar)))

  ;; assert that we incremented foobar n times
  (assert (= foobar 11)))

repita com índice:

Essa macro é semelhante, repeat-itmas na verdade funciona exatamente como a macro comum de loop do-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.

(defmacro repeat-it-with-index (var-and-n &rest body)
  "Evaluate BODY N number of times with VAR bound to successive integers from 0 inclusive to n exclusive..
VAR-AND-N should be in the form (VAR N).
Returns the result of the last evaluation of the last expression in BODY."
  (declare (indent defun))
  (let ((fallback-sym (make-symbol "fallback")))
    `(let ((,(first var-and-n) 0)
           (,fallback-sym 0))
       ,(cons 'progn
              (make-list (second var-and-n)
                         `(progn
                            (setq ,(first var-and-n) ,fallback-sym)
                            ,@body
                            (incf ,fallback-sym)))))))

teste de repetição com índice:

Este teste mostra que:

  1. O corpo avalia N vezes

  2. a variável de índice é sempre definida corretamente no início de cada iteração

  3. alterar o valor de um símbolo chamado "fallback" não interfere no índice

;; repeat-it-with-index test
(progn
  ;; first expected index is 0
  (setq expected-index 0)

  ;; start repeating
  (repeat-it-with-index (index 50)
    ;; change the value of a  'fallback' symbol
    (setq fallback (random 10000))
    ;; assert that index is set correctly, and that the changes to
    ;; fallback has no affect on its value
    (assert (= index expected-index))
    ;; change the value of index
    (setq index (+ 100 (random 1000)))
    ;; assert that it has changed
    (assert (not (= index expected-index)))
    ;; increment the expected value
    (incf expected-index))

  ;; assert that the final expected value is n
  (assert (= expected-index 50)))
Jordon Biondo
fonte
11

Cálculo lambda não tipado

λf.(λx.f (x x)) (λx.f (x x))
Arthur B
fonte
3
Não tenho certeza se isso conta como recursão ou não, e por ser a base teórica fundamental para isso ... +1 de qualquer maneira.
fofo
@fluffy Não é recursivo por si só, nenhuma das funções se autodenomina (principalmente porque as funções não são nomeadas).
haskeller orgulhoso
IMHO, o cálculo lambda é um modelo de computação e não é uma linguagem de programação (ou seja, sem um modelo de máquina concreto, não podemos considerar o cálculo lambda como um PL).
Ta Thanh Dinh
Você pode absolutamente construir uma máquina que interprete o cálculo lambda. E a sintaxe pode ser usada como uma linguagem de programação. Veja, por exemplo, github.com/MaiaVictor/caramel
Arthur B
10

Haskell, 24 caracteres

sequence_ (repeat (print "abc"))

ou de forma condensada, com 24 caracteres

sequence_$repeat$print"" 

(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.

orgulhoso haskeller
fonte
4
Eu ia postar basicamente a mesma resposta no Clojure, mas pensei repeatque seria a programming language statement which allows code to be repeatedly executed.
9444 Seequ
3
fix(print"">>), isso também não envolve funções de repetição nomeadas explicitamente.
Mniip
1
@ TheRare Eu não sei como está sendo encerrado, mas em Haskell, a repetição não é "uma declaração de linguagem de programação que permite que o código seja executado repetidamente" - é uma função que gera listas infinitas. é um loop assim como "int [] arr = {x, x, x};" é um loop.
haskeller orgulhoso
1
sim, mas algo deve ser implementado usando recursão, porque sem ela é basicamente impossível
haskeller orgulhoso
3
Na verdade, cada função existe neste código é definida usando recursão - mesmo print
haskeller orgulhoso
10

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:

mov dl, 'A' ; I refuse to explain this line!
mov ebx, msg ; output array (string)

call rawr   ; lets put address of "rawr" line on stack
rawr: pop eax ; and to variable with it! In same time we are breaking "ret"

add eax, 4 ; pop eax takes 4 bytes of memory, so for sake of stack lets skip it
mov [ebx], dl ; write letter
inc dl ; and proceed to next 
inc ebx
cmp dl, 'J' ; if we are done, simulate return/break by leaving this dangerous area
jg print

push eax ; and now lets abuse "ret" by making "call" by hand
ret

Código inteiro

section     .text
global      _start                              

_start:

;<core>
mov dl, 'A'
mov ebx, msg

call rawr
rawr: pop eax

add eax, 4
mov [ebx], dl
inc dl
inc ebx
cmp dl, 'J'
jg print

push eax
ret
;</core>

; just some Console.Write()
print:
    mov     edx,len
    mov     ecx,msg
    mov     ebx,1
    mov     eax,4
    int     0x80

    mov     eax,1
    xor     ebx, ebx
    int     0x80

section     .data

msg     db  '0123456789',0xa
len     equ $ - msg
PTwr
fonte
Eu chamaria isso de um dup de codegolf.stackexchange.com/a/34298/11259 , mas vejo que esta é a resposta anterior. +1
Trauma digital
@DigitalTrauma oh, vejo alguém fazer uma versão refinada da minha ideia - truque antigo, mas na era do código gerenciado, as pessoas tendem a esquecer como as coisas realmente funcionam. (Eu não gosto de golfe, muito frequentemente é reduzida a "olhar mãe eu posso fazer coisas acontecer pressionando uma tecla!")
PTwr
9

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:

#if __INCLUDE_LEVEL__ == 0
int main() 
{
    puts("There is no loop...");
#endif
#if __INCLUDE_LEVEL__ <= 16
    puts(".. but Im in ur loop!");
    #include "noloop.c"
#else
    return 0;
}
#endif

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 -Esinalizador com gcc).

AproximandoEscuridãoPeixe
fonte
8

PHP

Aqui está um com PHP. Loops incluindo o mesmo arquivo até o contador atingir $ max:

<?php
if (!isset($i))
    $i = 0;        // Initialize $i with 0
$max = 10;         // Target value

// Loop body here
echo "Iteration $i <br>\n";

$i++;               // Increase $i by one on every iteration

if ($i == $max)
    die('done');    // When $i reaches $max, end the script
include(__FILE__);  // Proceed with the loop
?>

O mesmo que um loop for:

<?php
for ($i = 0; $i < 10; $i++) {
    echo "Iteration $i <br>\n";
}
die('done');
?>
Pichan
fonte
Droga, isso também conta como recursão, não é?
9134 Pichan
Não pense que sim - a semelhança vem à mente do exemplo de @ Nathaniel: o pré-processador incluirá esses arquivos que serão avaliados simultaneamente.
eithed
@ Pichan, eu diria que é mais um desdobramento de loop, pois você termina com cópias de código na memória.
PTwr
Acabei de ver a pergunta hoje e criei um código quase idêntico. Tarde demais para mim!
TecBrat
É header("Location: .?x=".$_GET['x']+1);contado como recursão?
Charlie
8

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):

def z(f):
    g = lambda x: lambda w: f(lambda v: (x(x))(v), w)
    return g(g)

if __name__ == "__main__":
    def msg(rec, n):
        if (n > 0):
            print "Hello world!"
            rec(n - 1)
    z(msg)(7)

Imprime "Olá, mundo!" um determinado número de vezes.

Explicação: A função zimplementa o combinador estrito de ponto fixo Z , que (embora não seja definido recursivamente) permite expressar qualquer algoritmo recursivo.

Petr Pudlák
fonte
Eu chamaria gmuito indiretamente recursiva.
seequ
@TheRare Por quê? Qual é o seu argumento? Como gchama isso de gnovo? É claro que o truque é a auto-aplicação g(g), mas não há recursão envolvida. Você realmente chamaria de grecursiva indireta se não a visse g(g)? Essa é a maneira padrão de como fazê-lo em linguagens que não permitem definições recursivas, como o cálculo lambda.
Petr Pudlák
Você dá gcomo argumento xe depois chama x(x).
seequ
2
@TheRare Uma função (ou um conjunto de funções) não é recursiva ou não recursiva pela forma como é usada; isso é determinado apenas por sua definição.
Petr Pudlák
1
todas as respostas trapaceiam de uma maneira ou de outra: sempre há recursão ou um loop em algum lugar , se não na resposta, então no código a resposta invoca. Eu gosto do jeito que este engana.
Wayne Conrad
8

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é uma nopinstrução, portanto, continuará, alcançará o endereço $ffff, contornará $0000e 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).

harold
fonte
Você pode encher a memória com zeros e colocar um programa real em algum lugar.
see
Então você poderia colocar um programa de 64k, sem ramificações, e ele seria executado repetidamente?
22414 Bill Woodger
@BillWoodger você poderia, especialmente se você não tem interrupções na plataforma (ou nenhum ativado)
Harold
Tipo de :-) divertido
Bill Woodger
8

Perl-regex

(q x x x 10) =~ /(?{ print "hello\n" })(?!)/;

demonstração

ou tente como:

perl -e '(q x x x 10) =~ /(?{ print "hello\n" })(?!)/;'

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 .

jm666
fonte
6

T-SQL -12

print 1
GO 9

Na verdade, é mais uma peculiaridade do Sql Server Management Studio. GO é um separador de scripts e não faz parte da linguagem T-SQL. Se você especificar GO seguido de um número, ele executará o bloco várias vezes.

Michael B
fonte
1
Eu uso o T-SQL quase todos os dias e não fazia ideia de que você poderia fazer isso com o GO. 1
CailinP:
Tecnicamente, isso não é T-SQL. 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.
precisa saber é o seguinte
Sim, eu adicionei isso no meu comentário de spoiler. Eu imaginaria que usar sqlcmd seria muita trapaça.
22714 Michael Michael B
6

C #

Imprime todos os números inteiros de uint.MaxValue para 0.

   class Program
   {
      public static void Main()
      {
          uint max = uint.MaxValue;
          SuperWriteLine(ref max);
          Console.WriteLine(0);
      }

      static void SuperWriteLine(ref uint num)
      {
          if ((num & (1 << 31)) > 0) { WriteLine32(ref num); }
          if ((num & (1 << 30)) > 0) { WriteLine31(ref num); }
          if ((num & (1 << 29)) > 0) { WriteLine30(ref num); }
          if ((num & (1 << 28)) > 0) { WriteLine29(ref num); }
          if ((num & (1 << 27)) > 0) { WriteLine28(ref num); }
          if ((num & (1 << 26)) > 0) { WriteLine27(ref num); }
          if ((num & (1 << 25)) > 0) { WriteLine26(ref num); }
          if ((num & (1 << 24)) > 0) { WriteLine25(ref num); }
          if ((num & (1 << 23)) > 0) { WriteLine24(ref num); }
          if ((num & (1 << 22)) > 0) { WriteLine23(ref num); }
          if ((num & (1 << 21)) > 0) { WriteLine22(ref num); }
          if ((num & (1 << 20)) > 0) { WriteLine21(ref num); }
          if ((num & (1 << 19)) > 0) { WriteLine20(ref num); }
          if ((num & (1 << 18)) > 0) { WriteLine19(ref num); }
          if ((num & (1 << 17)) > 0) { WriteLine18(ref num); }
          if ((num & (1 << 16)) > 0) { WriteLine17(ref num); }
          if ((num & (1 << 15)) > 0) { WriteLine16(ref num); }
          if ((num & (1 << 14)) > 0) { WriteLine15(ref num); }
          if ((num & (1 << 13)) > 0) { WriteLine14(ref num); }
          if ((num & (1 << 12)) > 0) { WriteLine13(ref num); }
          if ((num & (1 << 11)) > 0) { WriteLine12(ref num); }
          if ((num & (1 << 10)) > 0) { WriteLine11(ref num); }
          if ((num & (1 << 9)) > 0) { WriteLine10(ref num); }
          if ((num & (1 << 8)) > 0) { WriteLine09(ref num); }
          if ((num & (1 << 7)) > 0) { WriteLine08(ref num); }
          if ((num & (1 << 6)) > 0) { WriteLine07(ref num); }
          if ((num & (1 << 5)) > 0) { WriteLine06(ref num); }
          if ((num & (1 << 4)) > 0) { WriteLine05(ref num); }
          if ((num & (1 << 3)) > 0) { WriteLine04(ref num); }
          if ((num & (1 << 2)) > 0) { WriteLine03(ref num); }
          if ((num & (1 <<  1)) > 0) { WriteLine02(ref num); }
          if ((num & (1 <<  0)) > 0) { WriteLine01(ref num); }
      }

      private static void WriteLine32(ref uint num) { WriteLine31(ref num); WriteLine31(ref num); }
      private static void WriteLine31(ref uint num) { WriteLine30(ref num); WriteLine30(ref num); }
      private static void WriteLine30(ref uint num) { WriteLine29(ref num); WriteLine29(ref num); }
      private static void WriteLine29(ref uint num) { WriteLine28(ref num); WriteLine28(ref num); }
      private static void WriteLine28(ref uint num) { WriteLine27(ref num); WriteLine27(ref num); }
      private static void WriteLine27(ref uint num) { WriteLine26(ref num); WriteLine26(ref num); }
      private static void WriteLine26(ref uint num) { WriteLine25(ref num); WriteLine25(ref num); }
      private static void WriteLine25(ref uint num) { WriteLine24(ref num); WriteLine24(ref num); }
      private static void WriteLine24(ref uint num) { WriteLine23(ref num); WriteLine23(ref num); }
      private static void WriteLine23(ref uint num) { WriteLine22(ref num); WriteLine22(ref num); }
      private static void WriteLine22(ref uint num) { WriteLine21(ref num); WriteLine21(ref num); }
      private static void WriteLine21(ref uint num) { WriteLine20(ref num); WriteLine20(ref num); }
      private static void WriteLine20(ref uint num) { WriteLine19(ref num); WriteLine19(ref num); }
      private static void WriteLine19(ref uint num) { WriteLine18(ref num); WriteLine18(ref num); }
      private static void WriteLine18(ref uint num) { WriteLine17(ref num); WriteLine17(ref num); }
      private static void WriteLine17(ref uint num) { WriteLine16(ref num); WriteLine16(ref num); }
      private static void WriteLine16(ref uint num) { WriteLine15(ref num); WriteLine15(ref num); }
      private static void WriteLine15(ref uint num) { WriteLine14(ref num); WriteLine14(ref num); }
      private static void WriteLine14(ref uint num) { WriteLine13(ref num); WriteLine13(ref num); }
      private static void WriteLine13(ref uint num) { WriteLine12(ref num); WriteLine12(ref num); }
      private static void WriteLine12(ref uint num) { WriteLine11(ref num); WriteLine11(ref num); }
      private static void WriteLine11(ref uint num) { WriteLine10(ref num); WriteLine10(ref num); }
      private static void WriteLine10(ref uint num) { WriteLine09(ref num); WriteLine09(ref num); }
      private static void WriteLine09(ref uint num) { WriteLine08(ref num); WriteLine08(ref num); }
      private static void WriteLine08(ref uint num) { WriteLine07(ref num); WriteLine07(ref num); }
      private static void WriteLine07(ref uint num) { WriteLine06(ref num); WriteLine06(ref num); }
      private static void WriteLine06(ref uint num) { WriteLine05(ref num); WriteLine05(ref num); }
      private static void WriteLine05(ref uint num) { WriteLine04(ref num); WriteLine04(ref num); }
      private static void WriteLine04(ref uint num) { WriteLine03(ref num); WriteLine03(ref num); }
      private static void WriteLine03(ref uint num) { WriteLine02(ref num); WriteLine02(ref num); }
      private static void WriteLine02(ref uint num) { WriteLine01(ref num); WriteLine01(ref num); }
      private static void WriteLine01(ref uint num) { Console.WriteLine(num--); }
   }
LVBen
fonte
1
Realmente não sei se isso conta. Você está chamando explicitamente os horários WriteLine01 Int.MaxValue. Ele explodiu por trás de uma enorme quantidade de pilha de chamadas.
Michael B
Como isso não conta? Não há loop nem recursão.
Lvben
1
Além disso, a pilha de chamadas não chega nem perto de ser massiva, a menos que você considere um número elevado de 32 ligações.
precisa saber é o seguinte
1
Por que apenas 32 vezes em vez de 4294967296 vezes?
Lvben
4
@ ja72 Se estou trabalhando em um projeto de código aberto no qual não posso usar loops ou recursão, vou contribuir totalmente com código como este!
Lvben
6

JS (no navegador)

Que tal agora?

document.write(new Date());
location = location;

Imprime a hora atual e recarrega a página.

Pichan
fonte
Oh, dispara. Acabei de postar uma resposta com o mesmo conceito básico. Eu estava digitalizando a página em busca de "JavaScript" ou qualquer coisa que mostrasse tags HTML. Suponho que posso deixar minha resposta, apenas porque lida com a caixa de canto em que o local contém um "#". Enfim, +1.
Keen
No Firefox 30:[Exception... "The operation is insecure." code: "18" nsresult: "0x80530012 (SecurityError)" location: "<unknown>"]
Alex Reynolds
@AlexReynolds Huh, estranho. Mina funciona muito bem em FF 30.
Pichan
Eu apenas copiei e colei no seu código como ele foi escrito. Isso não funciona. Talvez você tenha algumas preferências especiais de segurança habilitadas para fazer isso funcionar?
Alex Reynolds
@AlexReynolds Não, nunca alterou nenhuma configuração de segurança. E também funciona no Chrome.
Pichan