Pytanie podobne do tego zostało zadane kilka lat temu , ale to jest jeszcze trudniejsze.
Wyzwanie jest proste. Napisz program (w wybranym języku), który wielokrotnie wykonuje kod bez użycia jakichkolwiek struktur powtarzania takich jak while
, for
, do while
, foreach
lub goto
( Więc dla was wszystkich nitpickers, nie można użyć pętli ). Jednak rekursja jest niedozwolona, w funkcji wywołującej sens (patrz definicja poniżej) . To uczyniłoby to wyzwanie zdecydowanie zbyt łatwym.
Nie ma ograniczeń co do tego, co należy wykonać w pętli, ale opublikuj wyjaśnienie z odpowiedzią , aby inni mogli dokładnie zrozumieć, co jest wdrażane.
Dla tych, którzy mogą się rozłączyć z definicjami, definicja pętli dla tego pytania jest następująca:
A programming language statement which allows code to be repeatedly executed.
A definicja rekurencji dla tego pytania będzie twoją standardową definicją funkcji rekurencyjnej:
A function that calls itself.
Zwycięzcą zostanie odpowiedź, która uzyska najwięcej głosów poparcia 16 lipca o godzinie 10 czasu wschodniego. Powodzenia!
AKTUALIZACJA:
Aby uspokoić wciąż wyrażane zamieszanie, może to pomóc:
Zasady jak podano powyżej:
- Nie używaj pętli ani goto
- Funkcje nie mogą się nazywać
- Rób co chcesz w „pętli”
Jeśli chcesz coś zaimplementować, a reguły wyraźnie tego nie zabraniają, śmiało i zrób to. Wiele odpowiedzi już zagięło zasady.
function A
połączeniafunction B
ifunction B
wywołania,function A
podczas gdy jedna z funkcji coś wykona. Ponieważ funkcja nie nazywa się sama, powinna być poprawna na podstawie kryteriów ^. ^rep(f){f();f();}
- jest to instrukcja (deklaracja funkcji jest instrukcją w niektórych językach), która pozwala na wielokrotne wykonywanie kodu. Czy to niedozwolone? Pytasz o kod do implementacji pętli. Jeśli ten kod jest składniowo instrukcją, właśnie go zabroniłeś. Inny przykład:f(b) { b(); g(b); }; g(b) { f(b); }
. Powiedziałbym, żef
jest funkcją rekurencyjną (poprzez wzajemną rekurencjęg
). Czy to niedozwolone?Odpowiedzi:
Rubin
Próbny
Odchrząkuje, wydrukuje „Banan” 3070 razy, a także „Orange, cieszę się, że nie powiedziałem banana?”.
Wykorzystuje to niedorzeczną funkcję definiowania metody Ruby dokładnie w czasie, aby zdefiniować każdą metodę, która leży alfabetycznie między słowami „ahem” i „również” („ahem”, „ahen”, „aheo”, „ahep”, „aheq”, „aher”, „ahes”, „ahet”, „aheu”, „ahev” ...), aby najpierw wydrukować banan, a następnie wywołać następny na liście.
źródło
String#next
który jest wywoływany wmethod_missing
funkcjach mniej więcej takich jak dodawanie 1 do liczby, z tym wyjątkiem, że działa ze wszystkimi znakami alfanumerycznymi (i innymi niż alnum, jeśli są to jedyne znaki w ciągu). Zobacz ruby-doc.org/core-2.1.2/String.html#method-i-nextb.my_tag
. Jest również używany w modelach ActiveRecord lubOpenStruct
. W „Wat talk” mówi, że globalnośćmethod_missing
jest zła, ale zakres jest niesamowity.Python - 16
lub w dowolnym innym języku z eval.
źródło
"print 1;"
), powiela go 9 razy (*9
), a następnie wykonuje wynikowy string (exec
). Powtarzanie fragmentu kodu bez zapętlania.exec
sięeval
lubprint
doecho
.CSharp
Rozszerzyłem kod w bardziej czytelny sposób, ponieważ nie jest to już kod do golfa i dodałem licznik przyrostowy, aby ludzie mogli zobaczyć, że ten program coś robi.
(Nigdy tego nie rób proszę).
Na początku tworzymy nową instancję
P
klasy, która gdy program próbuje wyjść, wywołuje GC, który wywołuje finalizator, który tworzy nową instancjęP
klasy, która, gdy próbuje wyczyścić, tworzy nową,P
która wywołuje finalizator. .Program w końcu umiera.
Edycja: Niewytłumaczalnie działa to tylko około 45 tysięcy razy przed śmiercią. Nie do końca wiem, jak GC wymyślił moją trudną nieskończoną pętlę, ale tak się stało. Krótko mówiąc, wydaje się, że nie udało się tego rozgryźć, a wątek został zabity po około 2 sekundach wykonania: https://stackoverflow.com/questions/24662454/how-does-a-garbage-collector-avoid-an -infinite-loop-here
Edycja2: Jeśli uważasz, że jest to trochę zbyt podobne do rekurencji, rozważ moje inne rozwiązanie: https://codegolf.stackexchange.com/a/33268/23300
Wykorzystuje reifikację metod ogólnych, dzięki czemu w czasie wykonywania stale generuje nowe metody, a każda z metod nazywa się metodą świeżo wybitą. Unikam również używania
reference
parametrów typu, ponieważ zwykle środowisko wykonawcze może współdzielić kod dla tych metod. W przypadkuvalue
parametru typu środowisko wykonawcze jest zmuszane do utworzenia nowej metody.źródło
Finalize
więc czasami są wywoływanefinalizer
. W prawdziwym języku C # należy użyćIDisposable
wzorca.Befunge
Dobre stare Befunge generuje 0 (z pustego stosu) prawie na zawsze, gdy linie się zawijają.
źródło
JS
(f=function(){ console.log('hi!'); eval("("+f+")()") })()
Funkcja zabawy!
Funkcja, która tworzy inną funkcję z tym samym ciałem co ona sama, a następnie uruchamia ją.
Wyświetli się hi na końcu, gdy limit stosu zostanie osiągnięty i cała rzecz się zawali.
Oświadczenie: nie będziesz mógł nic zrobić w przeglądarce, dopóki nie zostanie osiągnięty limit stosu.
I jeszcze jedno, więcej zła :function f(){ var tab = window.open(); tab.f = f; tab.f()}()
Tworzy funkcję, która otwiera okno, następnie tworzy funkcję w tym oknie, która jest kopią funkcji, a następnie uruchamia ją.
Oświadczenie: jeśli zezwolisz na otwieranie wyskakujących okienek, jedynym sposobem na zakończenie tego będzie ponowne uruchomienie komputeraźródło
f
ci końca drugiej funkcji. Powinno być}f()
na końcu.Montaż x86 / DOS
Jak to działa
źródło
Jawa
Prosto z XKCD
To niekończąca się gra polegająca na złapaniu rodzica i dziecka!
Cel
CHILD
jest ustawiony na,PARENT
a celemPARENT
jestCHILD
. PodczasPARENT
wywołańAIM
wyrzuca instancjęBALL
klasy i zostaje przechwycona przez instrukcję catch. Instrukcja catch wywołuje następniePARENT.TARGET.AIM
miejsce doceloweCHILD
.CHILD
Instancja robi to samo i „wyrzuca piłkę z powrotem” do rodzica.źródło
TARGET.AIM(B);
w metodzieAIM
jest wywołaniem rekurencyjnym. To narusza zasadę „funkcje nie mogą się nazywać”.Bash, 3 znaki
tak wielokrotnie zwraca „y” na konsoli
Edycja: zachęcamy wszystkich do edycji tego wiersza:
(dzięki Olivier Dulac)
źródło
yes
to polecenie bash, które wypisuje słowo tak, dopóki nie zostanie zabite lub strumień zostanie zamknięty. Jeśli pisze na ekranie, nigdy się nie zatrzyma, dopóki go nie zabijesz. Jest to jednak trochę oszustwo, ponieważ jest to polecenie, które zasadniczo składa się z pętli nad printf.yes
innej pętli.yes something | xargs someaction
:: bez rekurencji (możesz nawet dodać -n 1 do xargs, aby mieć tylko 1 „coś” w wierszu itp.). Korzystanie z xargs otwiera drogę do bardziej złożonych zachowań (nawet tych, które w ogóle nie mają nic wspólnego z wynikiem tak)yes
.C, 35 znaków
Program wykonuje się sam. Nie jestem pewien, czy uważa się to za rekurencję, czy nie.
źródło
exec
powoduje , że nowy proces zastępuje oryginalny, więc nie ma stosu wywołań, który ostatecznie zwróci lub przepełni.exec
poprzedni proces. To też się nie przepełni.C (z wbudowanymi GCC - wydaje się również działać z clang)
Wyjaśnienie:
main()
pierwsze połączeniaframeloop(NULL)
. W takim przypadku użyj__builtin_return_address()
wbudowanego, aby uzyskać adres zwrotny (inmain()
),frameloop()
który powróci. Zwracamy ten adres.printf()
aby pokazać, że się zapętlamyframeloop()
z adresem zwrotnym dla poprzedniego połączenia. Przeglądamy stos pod kątem bieżącego adresu zwrotnego, a gdy go znajdujemy, zastępujemy poprzedni adres zwrotny.frameloop()
połączenia. Ale ponieważ adres zwrotny został zhakowany powyżej, w końcu wracamy do punktu, wmain()
którym pierwsze połączenie powinno wrócić. W ten sposób powstaje pętla.Wyszukiwanie adresu zwrotnego na stosie byłoby oczywiście czystsze jako pętla, ale rozwinąłem kilka iteracji, aby nie zapętlać.
Wynik:
źródło
setjmp()
/longjmp()
. Nie są one w standardzie c, ale znajdują się w standardowej bibliotece . Czułem jednak, że dzisiaj muszę ręcznie ustawić stos ;-)Haskell
Poniższy kod nie zawiera funkcji rekurencyjnej (nawet pośrednio), nie ma prymitywnego zapętlenia i nie wywołuje żadnej wbudowanej funkcji rekurencyjnej (wykorzystuje tylko
IO
dane wyjściowe i powiązanie), ale jednak nieskończenie powtarza dane działanie:Funkcja
extract
niczego nie nazwać,yc
zwraca tylkoextract
imain
zwraca tylkoyc
iputStrLn
a>>
, które nie są rekurencyjne.Objaśnienie: Trik polega na rekurencyjnym typie danych
Strange
. Jest to rekurencyjny typ danych, który sam się zużywa, co, jak pokazano w przykładzie, umożliwia dowolne powtarzanie. Po pierwsze, możemy skonstruowaćextract x
, co zasadniczo wyrażax x
samozastosowanie w niepisanym rachunku lambda. Pozwala to skonstruować kombinator Y zdefiniowany jakoλf.(λx.f(xx))(λx.f(xx))
.Aktualizacja: Jak sugeruję, zamieszczam wariant, który jest bliższy definicji Y w rachunku typu lambda bez typu:
źródło
let
powiązanie i zdefiniowaćyc f = extract $ C $ f.extract
, ponieważlet
prawdopodobnie jest to funkcja języka, która umożliwia rekurencję (klasycznalet x = x in x
). Zmniejsza to również niektóre znaki :)yc = extract . C . (.extract)
Y
.C ++
Poniżej przedstawiono wyniki odliczania od 10 do „Blast off!” za pomocą metaprogramowania szablonu.
Może to wyglądać jak klasyczny przykład rekurencji, ale tak naprawdę nie jest to, przynajmniej technicznie, zależne od twojej definicji. Kompilator wygeneruje dziesięć różnych funkcji.
countdown<10>
wypisuje „T minus 10”, a następnie wywołujecountdown<9>
i tak dalej docountdown<0>
, co wypisuje „Blast off!” a następnie wraca. Rekurencja ma miejsce podczas kompilowania kodu, ale plik wykonywalny nie zawiera żadnych struktur zapętlonych.W C ++ 11 można osiągnąć podobne efekty za pomocą
constexpr
słowa kluczowego, takiego jak ta funkcja silnia. (Nie można zaimplementować przykładu odliczania w ten sposób, ponieważconstexpr
funkcje nie mogą mieć skutków ubocznych, ale myślę, że może to być możliwe w nadchodzącym C ++ 14).Znowu to naprawdę wygląda rekursji, ale kompilator będzie rozwijać się
factorial(10)
w10*9*8*7*6*5*4*3*2*1
, a następnie prawdopodobnie wymienić go na stałej wartości3628800
, tak wykonywalny nie będzie zawierać żadnych zapętlenie lub kod rekurencyjnej.źródło
3628800
bezpośrednio bez forma pośrednia.constexpr
został specjalnie zaprojektowany, aby (niektóre aspekty) metaprogramowania szablonów stały się przestarzałe, więc zdecydowanie warto wspomnieć w poście na ten temat.&countdown<N-1> != &countdown<N>
.Jawa
Zagrajmy z modułem ładującym klasy Java i ustawmy go jako własny element nadrzędny:
Ta pętla jest tak silna, że musisz użyć a,
kill -9
aby ją zatrzymać :-)Zużywa 100,1% procesora mojego komputera Mac.
Możesz spróbować przesunąć
System.out
na końcu głównej funkcji, aby wypróbować alternatywne zabawne zachowanie.źródło
CSharp
Jeszcze jeden i równie zły:
To nie jest rekurencja ... to jest korekta szablonów kodu. Chociaż wydaje się, że wywołujemy tę samą metodę, środowisko wykonawcze stale tworzy nowe metody. Używamy parametru typu int, ponieważ faktycznie zmusza go to do utworzenia całego nowego typu, a każda instancja metody musi łączyć nową metodę. Nie można tutaj udostępniać kodu. W końcu zabijamy stos wywołań, ponieważ nieskończenie czeka na zwrot int, który obiecaliśmy, ale nigdy nie dostarczyliśmy. W podobny sposób piszemy napisany przez nas typ, aby był interesujący. Zasadniczo każde C, które nazywamy, jest całkowicie nową metodą, która ma tylko to samo ciało. Nie jest to tak naprawdę możliwe w języku takim jak C ++ lub D, który wykonuje swoje szablony w czasie kompilacji. Ponieważ C # JIT jest bardzo leniwy, tworzy to tylko w ostatniej możliwej chwili. A zatem,
źródło
Redcode 94 (Core War)
MOV 0, 1
Kopiuje instrukcję pod adres zero, aby adresować jeden. Ponieważ w Core War wszystkie adresy są względne w stosunku do bieżącego adresu PC i wielkości rdzenia modulo, jest to nieskończona pętla w jednej instrukcji bez skoku.
Ten program (wojownik) nosi nazwę „ Imp ” i został po raz pierwszy opublikowany przez AK Dewdney.
źródło
SPL 0, 0; MOV 1, -2
naprawdę.Strzałka
Myślę, że byłby to klasyczny sposób wykonywania rekurencji bez żadnej faktycznej funkcji rekurencyjnej. Żadna z poniższych funkcji nie odnosi się do siebie z nazwy, bezpośrednio lub pośrednio.
(Wypróbuj na dartpad.dartlang.org )
źródło
JS
Niezbyt oryginalny, ale mały. 20 znaków.
źródło
,1
i nadal będziesetInterval
nie jest jednak stwierdzeniem; to tylko funkcja. Jest używany wewnątrz wyrażenia, a jeśli nie możemy użyć wyrażeń, to po prostu już tego nie wiem.Sygnały w C
Zachowanie tego programu jest oczywiście bardzo nieokreślone, ale dziś na moim komputerze wciąż wypisuje „Witaj, świecie!”.
źródło
Emacs Lisp
To świetny czas, aby pochwalić się potężnym projektem Lisp, w którym „kod to dane, a dane to kod”. To prawda, że przykłady te są bardzo nieefektywne i nigdy nie należy ich używać w prawdziwym kontekście.
Makra generują kod, który jest rozwiniętą wersją domniemanej pętli, a wygenerowany kod jest oceniany w czasie wykonywania.
repeat-it: pozwala zapętlić N razy
test powtórzeń:
repeat-it-with-index:
To makro jest podobne,
repeat-it
ale w rzeczywistości działa tak jak zwykłe makro zapętlonedo-times
, pozwala określić symbol, który będzie powiązany z indeksem pętli. Używa symbolu czasu rozszerzania, aby upewnić się, że zmienna indeksu jest ustawiona poprawnie na początku każdej pętli, niezależnie od tego, czy zmodyfikujesz jej wartość podczas treści pętli.test powtórzeń z indeksem:
Ten test pokazuje, że:
Ciało ocenia N razy
zmienna indeksu jest zawsze ustawiana poprawnie na początku każdej iteracji
zmiana wartości symbolu o nazwie „awaryjne” nie zadziała z indeksem
źródło
Rachunek lambda bez typu
źródło
Haskell, 24 znaki
lub w formie skróconej, z 24 znakami
(chociaż tekst został zmieniony, nadal będzie się zapętlał - spowoduje to nieskończone wydrukowanie dwóch cudzysłowów i nowego wiersza)
wyjaśnienie: print „abc” jest w zasadzie działaniem we / wy, które po prostu wypisuje „abc”.
repeat jest funkcją, która przyjmuje wartość x i zwraca nieskończoną listę składającą się tylko z x.
sekwencja_ jest funkcją, która pobiera listę akcji we / wy i zwraca akcję we / wy, która wykonuje wszystkie akcje sekwencyjnie.
więc w zasadzie ten program tworzy nieskończoną listę poleceń drukowania „abc” i wielokrotnie je wykonuje. bez pętli i rekurencji.
źródło
repeat
, że tak będziea programming language statement which allows code to be repeatedly executed
.fix(print"">>)
, nie obejmuje to również wyraźnie nazwanych funkcji powtarzania.ASM (x86 + I / O dla Linux)
Nie ma znaczenia, jak bardzo zmagają się twoje słabe języki wysokiego poziomu, nadal będzie to po prostu ukryta manipulacja wskaźnikiem instrukcji. W końcu będzie to rodzaj „goto” (jmp), chyba że będziesz się nudzić, aby rozwinąć pętlę w czasie wykonywania.
Możesz przetestować kod w Ideone
Możesz także sprawdzić bardziej wyrafinowaną wersję tego pomysłu w kodzie Matteo Italia DOS .
Zaczyna się od ciągu 0..9 i zastępuje go A..J, nie stosuje się bezpośrednich skoków (powiedzmy, że nie wydarzyło się „goto”), nie ma też nawrotu.
Kod prawdopodobnie może być mniejszy z pewnym nadużyciem przy obliczaniu adresu, ale praca na kompilatorze online jest uciążliwa, więc zostawię go takim, jaki jest.
Część główna:
Cały kod
źródło
Preprocesor C.
Trochę „techniki”, którą wymyśliłem podczas próby zaciemnienia. Nie ma rekurencji funkcji, ale jest ... rekurencja pliku?
noloop.c:
Napisałem / przetestowałem to za pomocą gcc. Oczywiście twój kompilator musi obsługiwać
__INCLUDE_LEVEL__
makro (lub alternatywnie__COUNTER__
makro z pewnymi poprawkami), aby to skompilować. Powinno być dość oczywiste, jak to działa, ale dla zabawy uruchom preprocesor bez kompilacji kodu (użyj-E
flagi z gcc).źródło
PHP
Oto jeden z PHP. Pętle zawierają ten sam plik, dopóki licznik nie osiągnie $ max:
To samo co dla pętli for:
źródło
header("Location: .?x=".$_GET['x']+1);
liczony jako rekurencja?Pyton
Poniższy kod nie zawiera funkcji rekurencyjnej (bezpośredniej lub pośredniej), nie zawiera operacji podstawowej zapętlającej się i nie wywołuje żadnej wbudowanej funkcji (oprócz
print
):Drukuje „Witaj świecie!” określoną liczbę razy.
Objaśnienie: Funkcja
z
implementuje ścisły Z -punktowy kombinator , który (choć nie zdefiniowany rekurencyjnie) pozwala wyrazić dowolny algorytm rekurencyjny.źródło
g
bardzo pośrednio rekurencyjnym.g
połączenie tog
ponownie? Oczywiście, sztuczka polega na samodzielnym nałożeniug(g)
, ale nie wiąże się to z rekurencją. Czy rzeczywiście nazwałbyśg
pośrednio rekurencyjnym, jeśli jeszcze tego nie widziałeśg(g)
? Jest to standardowy sposób, jak to zrobić w językach, które nie dopuszczają definicji rekurencyjnych, takich jak rachunek lambda.g
jako argument,x
a następnie dzwoniszx(x)
.kod maszynowy z80
W środowisku, w którym można wykonać pod każdym adresem i mapować pamięć ROM wszędzie, mapuj 64 KB pamięci ROM wypełnionej zerami do całej przestrzeni adresowej.
Co robi: nic. Wielokrotnie.
Jak to działa: procesor rozpocznie wykonywanie, bajt
00
jestnop
instrukcją, więc po prostu będzie kontynuował, dotarł do adresu$ffff
, zawinął się$0000
i kontynuował wykonywanie,nop
dopóki go nie zresetujesz.Aby uczynić to nieco bardziej interesującym, wypełnij pamięć inną wartością (uważaj, aby uniknąć instrukcji sterowania przepływem).
źródło
Perl-regex
próbny
lub wypróbuj jako:
(?!)
Nigdy nie pasuje. Dlatego silnik wyrażeń regularnych próbuje dopasować każdą pozycję zerowej szerokości w dopasowanym ciągu.To
(q x x x 10)
samo co(" " x 10)
- powtórzspace
dziesięć razy.Edycja: zmieniono „znaki” na pozycje o zerowej szerokości, aby były bardziej precyzyjne dla lepszego zrozumienia. Zobacz odpowiedzi na to pytanie dotyczące przepływu stosu .
źródło
T-SQL -12
źródło
GO
jest w rzeczywistości dyrektywą SSMS, dlatego nie można umieścić jej w obiektach skryptowych T-SQL, takich jak np. procedura składowana.DO#
Wyświetla wszystkie liczby całkowite z uint.MaxValue do 0.
źródło
JS (w przeglądarce)
Co powiesz na to?
Drukuje bieżącą godzinę i ładuje stronę ponownie.
źródło
[Exception... "The operation is insecure." code: "18" nsresult: "0x80530012 (SecurityError)" location: "<unknown>"]