Sebuah pertanyaan yang mirip dengan ini telah diajukan beberapa tahun yang lalu , tetapi yang ini lebih rumit.
Tantangannya sederhana. Menulis sebuah program (dalam bahasa pilihan Anda) yang berulang kali mengeksekusi kode tanpa menggunakan struktur pengulangan seperti while
, for
, do while
, foreach
atau goto
( Jadi untuk semua nitpickers Anda, Anda tidak dapat menggunakan loop ). Namun, rekursi tidak diperbolehkan, dalam fungsi yang menamakan dirinya sendiri (lihat definisi di bawah) . Itu akan membuat tantangan ini terlalu mudah.
Tidak ada batasan pada apa yang perlu dieksekusi dalam loop, tetapi posting penjelasan dengan jawaban Anda sehingga orang lain dapat memahami dengan tepat apa yang sedang dilaksanakan.
Bagi mereka yang mungkin terpaku pada definisi, definisi loop untuk pertanyaan ini adalah:
A programming language statement which allows code to be repeatedly executed.
Dan definisi rekursi untuk pertanyaan ini akan menjadi definisi fungsi rekursif standar Anda:
A function that calls itself.
Pemenang akan menjadi jawaban yang paling banyak mendapat dukungan pada 16 Juli pukul 10 pagi waktu bagian timur. Semoga berhasil!
MEMPERBARUI:
Untuk menenangkan kebingungan yang masih diungkapkan ini dapat membantu:
Aturan sebagaimana dinyatakan di atas:
- Jangan gunakan loop atau goto
- Fungsi tidak bisa menyebut diri mereka sendiri
- Lakukan apa pun yang Anda inginkan di 'lingkaran'
Jika Anda ingin menerapkan sesuatu dan aturannya tidak secara eksplisit melarangnya, silakan dan lakukan. Banyak jawaban sudah melanggar aturan.
function A
panggilanfunction B
danfunction B
panggilanfunction A
sementara 1 fungsi melakukan sesuatu. Karena fungsi tersebut tidak menyebut dirinya sendiri, fungsi tersebut harus valid berdasarkan kriteria ^. ^rep(f){f();f();}
- ini adalah pernyataan (pernyataan fungsi adalah pernyataan dalam beberapa bahasa) yang memungkinkan mengeksekusi kode berulang kali. Apakah itu dilarang. Anda meminta kode untuk mengimplementasikan loop. Jika kode itu secara sintaksis merupakan pernyataan, Anda baru saja menolaknya. Contoh lain:f(b) { b(); g(b); }; g(b) { f(b); }
. Saya akan mengatakanf
adalah fungsi rekursif (dengan menjadi saling rekursif dengang
). Apakah itu dilarang?Jawaban:
Rubi
Demo
Bersihkan tenggorokannya, mencetak "Pisang" 3070 kali, dan juga menempatkan "Oranye, kau senang aku tidak mengatakan pisang?".
Ini menggunakan fungsi definisi metode just-in-time yang konyol dari Ruby untuk mendefinisikan setiap metode yang secara alfabetis terletak antara kata 'ahem' dan 'juga' ("ahem", "ahen", "aheo", "ahep", "ahep", "aheq", "aher", "ahes", "ahet", "aheu", "ahev" ...) untuk pertama-tama mencetak Pisang dan kemudian memanggil yang berikutnya dalam daftar.
sumber
String#next
yang disebut dalammethod_missing
fungsi kurang lebih seperti menambahkan 1 ke nomor kecuali ia bekerja dengan semua karakter alfanumerik (dan non-alnums jika mereka adalah satu-satunya karakter dalam string). Lihat ruby-doc.org/core-2.1.2/String.html#method-i-nextb.my_tag
. Ini juga digunakan dalam model ActiveRecord atauOpenStruct
. Dalam 'Wat talk' dia mengatakan bahwa globalmethod_missing
itu buruk, tetapi cakupannya luar biasa.Python - 16
atau bahasa lain dengan eval.
sumber
"print 1;"
), duplikatnya 9 kali (*9
), kemudian jalankan string yang dihasilkan (exec
). Mengulang sepotong kode tanpa benar-benar berulang sama sekali.exec
keeval
atau yangprint
keecho
.CSharp
Saya telah memperluas kode menjadi cara yang lebih mudah dibaca karena ini bukan lagi kode golf dan menambahkan penghitung kenaikan sehingga orang dapat benar-benar melihat bahwa program ini melakukan sesuatu.
(Jangan pernah melakukan ini).
Pada awal kita membuat instance baru dari
P
kelas, yang ketika program mencoba untuk keluar memanggil GC yang memanggil finalizer yang membuat instance baruP
kelas, yang ketika mencoba untuk membersihkan menciptakan baruP
yang memanggil finalizer .. .Program akhirnya mati.
Sunting: Secara misterius ini hanya berjalan sekitar 45 ribu kali sebelum mati. Saya tidak tahu bagaimana GC menemukan loop tak terbatas saya yang rumit tapi ternyata berhasil. Singkatnya sepertinya tidak mengetahuinya dan utas baru saja terbunuh setelah sekitar 2 detik eksekusi: https://stackoverflow.com/questions/24662454/how-does-a-garbage-collector-avoid-an -infinite-loop-sini
Sunting2: Jika Anda pikir ini agak terlalu mirip rekursi pertimbangkan solusi saya yang lain: https://codegolf.stackexchange.com/a/33268/23300
Ini menggunakan reifikasi metode generik sehingga pada saat runtime itu terus-menerus menghasilkan metode baru dan masing-masing metode dalam istilah panggilan metode yang baru dicetak. Saya juga menghindari menggunakan
reference
parameter tipe, karena biasanya runtime dapat membagikan kode untuk metode tersebut. Denganvalue
parameter tipe, runtime dipaksa untuk membuat metode baru.sumber
Finalize
sehingga mereka kadang-kadang dipanggilfinalizer
. Dalam C # nyata, Anda harus menggunakanIDisposable
pola.Dibalik
Befunge tua yang baik menghasilkan 0 (dari tumpukan kosong) cukup lama, karena garis membungkus.
sumber
JS
(f=function(){ console.log('hi!'); eval("("+f+")()") })()
Berfungsi menyenangkan!
Fungsi yang membuat fungsi lain dengan tubuh yang sama dengan dirinya sendiri dan kemudian menjalankannya.
Ini akan menampilkan hi di akhir ketika batas stack tercapai dan semuanya runtuh.
Penafian: Anda tidak akan dapat melakukan apa pun di browser Anda sampai batas tumpukan tercapai.
Dan satu lagi, lebih jahat :function f(){ var tab = window.open(); tab.f = f; tab.f()}()
Itu menciptakan fungsi yang membuka jendela, lalu menciptakan fungsi di dalam jendela itu yang merupakan salinan dari fungsi, dan kemudian menjalankannya.
Penafian: jika Anda mengizinkan popup dibuka, satu-satunya cara untuk menyelesaikannya adalah dengan memulai ulang komputer Andasumber
f
di akhir fungsi kedua Anda. Itu harus}f()
pada akhirnya.x86 assembly / DOS
Bagaimana itu bekerja
sumber
Jawa
Langsung dari XKCD
Ini adalah permainan tangkapan tanpa akhir antara orangtua dan anak!
Target
CHILD
diatur kePARENT
dan targetPARENT
adalahCHILD
. KetikaPARENT
panggilanAIM
, itu melempar instance dariBALL
kelas dan itu ditangkap oleh pernyataan tangkapan. Pernyataan tangkapan kemudian memanggil diPARENT.TARGET.AIM
mana targetnya adalahCHILD
. MesinCHILD
virtual melakukan hal yang sama dan "melempar bola kembali" ke induk.sumber
TARGET.AIM(B);
dalam metodeAIM
adalah panggilan rekursif. Jadi ini melanggar aturan "fungsi tidak bisa menyebut diri mereka".Bash, 3 karakter
ya akan berulang kali mengembalikan 'y' ke konsol
Sunting: Semua orang didorong untuk mengedit baris ini:
(terima kasih kepada Olivier Dulac)
sumber
yes
adalah perintah bash yang mencetak kata ya hingga terbunuh atau aliran menjadi tertutup. Jika itu menulis ke layar itu tidak akan pernah berhenti sampai Anda membunuhnya Ini agak curang, karena itu adalah perintah yang pada dasarnya terdiri dari loop over printf.yes
untuk membuat loop lainnya tetap berjalan.yes something | xargs someaction
tanpa rekursi (Anda bahkan dapat menambahkan -n 1 ke xargs hanya memiliki 1 "sesuatu" per baris, dll). Menggunakan xargs membuka jalan bagi perilaku yang lebih kompleks (bahkan mereka yang tidak memiliki hubungan sama sekali dengan output ya)yes
.C, 35 karakter
Program mengeksekusi sendiri. Saya tidak yakin apakah ini dianggap rekursi atau tidak.
sumber
exec
menyebabkan proses baru untuk menggantikan yang asli, sehingga tidak ada tumpukan panggilan yang pada akhirnya akan kembali atau meluap.exec
menggantikan proses sebelumnya. Itu juga tidak akan meluap.C (dengan GCC bawaan - juga tampaknya bekerja dengan dentang)
Penjelasan:
main()
panggilan pertamaframeloop(NULL)
. Dalam hal ini gunakan__builtin_return_address()
builtin untuk mendapatkan alamat pengirimmain()
yangframeloop()
akan kembali ke. Kami mengembalikan alamat ini.printf()
untuk menunjukkan kita mengulangframeloop()
dengan alamat pengirim untuk panggilan sebelumnya. Kami melihat melalui tumpukan untuk alamat pengirim saat ini, dan ketika kami menemukannya, kami mengganti alamat pengirim sebelumnya.frameloop()
panggilan ke-2 . Tetapi karena alamat pengirim diretas di atas, kami akhirnya kembali ke titik dimain()
mana panggilan pertama harus kembali. Jadi kita berakhir dalam satu lingkaran.Pencarian untuk alamat pengirim di stack tentu saja akan lebih bersih sebagai sebuah loop, tapi saya membuka beberapa iterasi demi tidak mengulangi apa pun.
Keluaran:
sumber
setjmp()
/longjmp()
. Ini tidak dalam standar c, tetapi berada di perpustakaan standar . Aku merasa seperti menipiskan tumpukan secara manual hari ini ;-)Haskell
Kode berikut ini tidak mengandung fungsi rekursif (bahkan secara tidak langsung), tidak ada pengulangan primitif dan tidak memanggil fungsi rekursif
IO
bawaan (hanya menggunakan keluaran dan pengikatan), namun kode ini mengulangi tindakan yang diberikan secara pasti:Fungsi
extract
tidak memanggil apa pun,yc
panggilan adilextract
danmain
panggilan adilyc
danputStrLn
dan>>
, yang tidak berulang.Penjelasan: Caranya adalah pada tipe data rekursif
Strange
. Ini adalah tipe data rekursif yang mengkonsumsi sendiri, yang, seperti yang ditunjukkan dalam contoh, memungkinkan pengulangan sewenang-wenang. Pertama, kita dapat membangunextract x
, yang pada dasarnya mengekspresikan penerapan dirix x
dalam kalkulus lambda yang tidak diketik. Dan ini memungkinkan untuk membangun kombinator Y yang didefinisikan sebagaiλf.(λx.f(xx))(λx.f(xx))
.Pembaruan: Seperti yang disarankan, saya memposting varian yang lebih dekat dengan definisi Y dalam kalkulus lambda yang tidak diketik:
sumber
let
pengikatan dan mendefinisikanyc f = extract $ C $ f.extract
, karenalet
pengikatan bisa dibilang fitur bahasa yang memungkinkan rekursi (klasiklet x = x in x
). Ini juga mengurangi beberapa karakter :)yc = extract . C . (.extract)
Y
.C ++
Berikut ini menampilkan hitungan mundur dari 10 ke "Blast off!" menggunakan metaprogramming template.
Ini mungkin terlihat seperti contoh klasik rekursi, tetapi sebenarnya tidak, setidaknya secara teknis, tergantung pada definisi Anda. Kompiler akan menghasilkan sepuluh fungsi berbeda .
countdown<10>
mencetak "T minus 10" dan kemudian memanggilcountdown<9>
, dan seterusnya kecountdown<0>
, yang mencetak "Lepaskan!" dan kemudian kembali. Rekursi terjadi ketika Anda mengkompilasi kode, tetapi executable tidak mengandung struktur pengulangan.Dalam C ++ 11 orang dapat mencapai efek yang sama menggunakan
constexpr
kata kunci, seperti fungsi faktorial ini. (Ini tidak mungkin untuk menerapkan contoh hitung mundur dengan cara ini, karenaconstexpr
fungsi tidak dapat memiliki efek samping, tapi saya pikir itu mungkin terjadi di C ++ 14 mendatang.)Sekali lagi ini benar-benar tampak seperti rekursi, tetapi kompiler akan berkembang
factorial(10)
menjadi10*9*8*7*6*5*4*3*2*1
, dan kemudian mungkin menggantinya dengan nilai konstan3628800
, sehingga executable tidak akan berisi kode perulangan atau rekursif.sumber
3628800
langsung tanpa bentuk peralihan.constexpr
secara khusus dirancang untuk membuat (beberapa aspek) metaprogramming template menjadi usang, jadi sepertinya layak disebutkan dalam posting pada subjek.&countdown<N-1> != &countdown<N>
.Jawa
Mari bermain dengan pemuat kelas Java dan atur sebagai induknya sendiri:
Loop ini sebenarnya sangat kuat sehingga Anda harus menggunakan
kill -9
untuk menghentikannya :-)Ini menggunakan 100,1% dari CPU Mac saya.
Anda dapat mencoba untuk memindahkan
System.out
di akhir fungsi utama untuk bereksperimen perilaku lucu alternatif.sumber
CSharp
Satu lagi yang sama jahatnya ::
Ini bukan rekursi ... ini adalah reifikasi templat kode. Meskipun tampaknya kami memanggil metode yang sama, runtime terus-menerus membuat metode baru. Kami menggunakan tipe parameter int, karena ini benar-benar memaksanya untuk membuat seluruh tipe baru dan setiap instance dari metode harus membuang metode baru. Tidak dapat memberi kode berbagi di sini. Akhirnya, kami membunuh tumpukan panggilan karena menunggu kembalinya int yang kami janjikan tetapi tidak pernah dikirimkan. Dengan cara yang sama, kami terus menulis jenis yang kami buat agar tetap menarik. Pada dasarnya setiap C yang kita panggil adalah metode baru yang benar-benar baru yang hanya memiliki tubuh yang sama. Ini tidak benar-benar mungkin dalam bahasa seperti C ++ atau D yang melakukan templat mereka pada waktu kompilasi. Karena, C # JIT sangat malas, itu hanya menciptakan hal-hal ini pada saat-saat terakhir. Jadi,
sumber
Redcode 94 (Perang Inti)
MOV 0, 1
Salinan instruksi di alamat nol ke alamat satu. Karena dalam Core War semua alamat relatif terhadap alamat PC saat ini dan memodul ukuran inti, ini adalah loop tak terbatas dalam satu instruksi, non-lompat.
Program ini (prajurit) disebut " Imp " dan pertama kali diterbitkan oleh AK Dewdney.
sumber
SPL 0, 0; MOV 1, -2
memang.Anak panah
Saya kira ini akan menjadi cara klasik untuk melakukan rekursi tanpa fungsi rekursif yang sebenarnya. Tidak ada fungsi di bawah ini mengacu pada namanya sendiri, secara langsung atau tidak langsung.
(Cobalah di dartpad.dartlang.org )
sumber
JS
Tidak sangat asli tetapi kecil. 20 karakter.
sumber
,1
dan itu masih akan berfungsi,setInterval
bukan merupakan pernyataan; itu hanya sebuah fungsi. Ini digunakan di dalam pernyataan ekspresi, dan jika kita tidak bisa menggunakan pernyataan ekspresi, maka saya bahkan tidak tahu lagi.Sinyal dalam C
Perilaku program ini jelas sangat tidak terdefinisi, tetapi hari ini, di komputer saya, ia terus mencetak "Halo, dunia!".
sumber
Emacs Lisp
Ini adalah waktu yang tepat untuk memamerkan desain Lisp yang kuat di mana "kode adalah data dan data adalah kode". Memang, contoh-contoh ini sangat tidak efisien dan ini tidak boleh digunakan dalam konteks nyata.
Makro menghasilkan kode yang merupakan versi tidak terbaca dari loop yang seharusnya dan kode yang dihasilkan adalah apa yang dievaluasi saat runtime.
repeat-it: memungkinkan Anda untuk mengulang N kali
tes pengulangan:
ulangi dengan indeks:
Makro ini seperti
repeat-it
tetapi sebenarnya berfungsi seperti makro perulangan umum,do-times
ini memungkinkan Anda menentukan simbol yang akan terikat pada indeks lingkaran. Ini menggunakan simbol waktu ekspansi untuk memastikan bahwa variabel indeks diatur dengan benar di awal setiap loop terlepas dari apakah Anda memodifikasi nilainya selama tubuh loop.tes pengulangan-dengan-indeks:
Tes ini menunjukkan bahwa:
Tubuh mengevaluasi N kali
variabel indeks selalu diatur dengan benar di awal setiap iterasi
mengubah nilai simbol bernama "fallback" tidak akan mengacaukan indeks
sumber
Kalkulus lambda yang tidak diketik
sumber
Haskell, 24 karakter
atau dalam bentuk kental, dengan 24 karakter
(walaupun teksnya diubah, ini masih akan berulang - ini akan mencetak dua tanda kutip dan baris baru tanpa batas)
PENJELASAN: mencetak "abc" pada dasarnya adalah tindakan i / o yang hanya mencetak "abc".
repeat adalah fungsi yang mengambil nilai x dan mengembalikan daftar tak terbatas yang hanya terbuat dari x.
sequence_ adalah fungsi yang mengambil daftar tindakan i / o dan mengembalikan tindakan i / o yang melakukan semua tindakan secara berurutan.
jadi, pada dasarnya, program ini membuat daftar perintah "abc" cetak yang tak terbatas, dan berulang kali mengeksekusinya. tanpa loop atau rekursi.
sumber
repeat
akana programming language statement which allows code to be repeatedly executed
.fix(print"">>)
, ini juga tidak melibatkan fungsi pengulangan yang secara eksplisit disebut.ASM (x86 + I / O untuk Linux)
Tidak peduli berapa banyak bahasa tingkat rendah Anda akan berjuang, itu masih akan menjadi manipulasi pointer instruksi tersembunyi. Pada akhirnya itu akan menjadi semacam "goto" (jmp), kecuali jika Anda cukup bosan untuk membuka gulungan di runtime.
Anda dapat menguji kode pada Ideone
Anda juga dapat melihat versi yang lebih baik dari ide ini dalam kode DOS Matteo Italia .
Itu dimulai dengan string 0..9 dan menggantinya dengan A..J, tidak ada lompatan langsung yang digunakan (jadi katakanlah tidak ada "goto" terjadi), tidak ada pengulangan juga.
Kode mungkin bisa lebih kecil dengan beberapa penyalahgunaan perhitungan alamat, tetapi mengerjakan kompiler online itu menyusahkan jadi saya akan membiarkannya apa adanya.
Bagian inti:
Seluruh kode
sumber
C Preprocessor
Sedikit "teknik" yang saya buat selama tantangan kebingungan. Tidak ada rekursi fungsi, tetapi ada ... rekursi file?
noloop.c:
Saya menulis / menguji ini menggunakan gcc. Jelas kompiler Anda perlu mendukung
__INCLUDE_LEVEL__
makro (atau alternatifnya__COUNTER__
makro dengan beberapa penyesuaian) agar dapat dikompilasi. Seharusnya cukup jelas bagaimana ini bekerja, tetapi untuk bersenang-senang, jalankan preprocessor tanpa mengkompilasi kode (gunakan-E
bendera dengan gcc).sumber
PHP
Inilah satu dengan PHP. Loop dengan memasukkan file yang sama hingga penghitung mencapai $ maks:
Sama seperti for-loop:
sumber
header("Location: .?x=".$_GET['x']+1);
dihitung sebagai rekursi?Python
Kode berikut tidak mengandung fungsi rekursif (langsung atau tidak langsung), tidak ada perulangan primitif dan tidak memanggil fungsi bawaan apa pun (kecuali
print
):Cetakan "Halo dunia!" beberapa kali.
Penjelasan: Fungsi
z
mengimplementasikan combinator titik tetap Z yang ketat , yang (walaupun tidak didefinisikan secara rekursif) memungkinkan untuk mengekspresikan algoritma rekursif apa pun.sumber
g
sangat tidak langsung bersifat rekursif.g
disebut panggilan itug
lagi? Tentu saja triknya adalah aplikasi dirig(g)
, tetapi tidak ada rekursi yang terlibat. Apakah Anda memang menyebutg
secara tidak langsung rekursif jika Anda belum melihatg(g)
? Ini adalah cara standar bagaimana melakukannya dalam bahasa yang tidak memungkinkan definisi rekursif, seperti kalkulus lambda.g
sebagai argumenx
dan kemudian meneleponx(x)
.kode mesin z80
Dalam lingkungan di mana Anda dapat mengeksekusi di setiap alamat dan memetakan ROM di mana-mana, peta 64kb ROM diisi dengan nol ke seluruh ruang alamat.
Apa yang dilakukannya: tidak ada. Berkali-kali.
Cara kerjanya: prosesor akan mulai mengeksekusi, byte
00
adalahnop
instruksi, jadi itu hanya akan melanjutkan, mencapai alamat$ffff
, membungkus sekitar$0000
, dan terus mengeksekusinop
sampai Anda meresetnya.Untuk membuatnya sedikit lebih menarik, isi memori dengan nilai lain (hati-hati untuk menghindari instruksi aliran kontrol).
sumber
Perl-regex
demo
atau coba sebagai:
Yang
(?!)
tidak pernah cocok. Jadi mesin regex mencoba untuk mencocokkan setiap posisi lebar nol dalam string yang cocok.Yang
(q x x x 10)
sama(" " x 10)
- ulangispace
sepuluh kali.Sunting: mengubah "karakter" ke posisi nol lebar menjadi lebih tepat agar lebih mudah dipahami. Lihat jawaban untuk pertanyaan stackoverflow ini .
sumber
T-SQL -12
sumber
GO
sebenarnya adalah arahan SSMS, itulah sebabnya Anda tidak bisa memasukkannya ke objek skrip T-SQL, seperti misalnya prosedur tersimpan.C #
Mencetak semua bilangan bulat dari uint.MaxValue ke 0.
sumber
JS (di browser)
Bagaimana dengan ini?
Mencetak waktu saat ini dan memuat kembali halaman.
sumber
[Exception... "The operation is insecure." code: "18" nsresult: "0x80530012 (SecurityError)" location: "<unknown>"]