Bahasa pemrograman imperatif apa yang tidak mendukung rekursi?

21

Setahu saya, semua bahasa pemrograman imperatif modern mendukung rekursi dalam arti bahwa suatu prosedur dapat memanggil dirinya sendiri. Ini tidak selalu terjadi, tetapi saya tidak dapat menemukan fakta sulit dengan pencarian Google cepat. Jadi pertanyaan saya adalah:

Bahasa mana yang tidak mendukung rekursi sejak awal dan kapan dukungan itu ditambahkan?

programming-languages recursion fredoverflow
sumber

Jawaban:

21

Saya tidak yakin COBOL melakukannya (tentu saja tidak pada satu waktu), tetapi saya tidak bisa membayangkan siapa pun yang peduli.

Fortran sudah sejak Fortran 90, tetapi mengharuskan Anda menggunakan recursivekata kunci untuk memberi tahu bahwa subrutin bersifat rekursif.

PL / Saya hampir sama - rekursi didukung, tetapi Anda harus secara eksplisit mengatakannya prosedur apa yang bersifat rekursif.

Saya ragu ada lebih banyak dari itu. Saat Anda melakukannya, melarang rekursi sebagian besar adalah sesuatu yang dilakukan IBM dalam desain bahasa mereka, karena alasan sederhana bahwa mainframe IBM (360/370/3090 / ...) tidak mendukung tumpukan perangkat keras. Ketika sebagian besar bahasa berasal dari IBM, mereka kebanyakan melarang rekursi. Sekarang mereka semua berasal dari tempat lain, rekursi selalu diperbolehkan (meskipun saya harus menambahkan bahwa beberapa mesin lain, terutama Cray 1 asli, tidak memiliki dukungan perangkat keras untuk tumpukan juga).

Jerry Coffin
sumber
Kontrol Data komputer pada periode tersebut tidak mendukung rekursi (panggilan subrutin dilakukan dengan instruksi yang mengubah kode untuk memasukkan lompatan ke instruksi panggilan + 1). Ketika Wirth mengembangkan Pascal pada 6600, ia mungkin harus menemukan cara baru untuk memanggil subrutin.
David Thornley
@ David: ya - dan bukan kebetulan, mereka juga dirancang oleh Seymour Cray. Saya pernah melihat kompiler Pascal 6000, tetapi tidak ingat pernah melihat apa yang dilakukannya untuk menghasilkan (mensimulasikan?) Stack frame.
Jerry Coffin
notably the original cray 1Jadi, Anda tidak perlu rekursi untuk mengkloning dinosaurus? Saya kira itu terserah kita monyet untuk berayun melalui pepohonan.
normanthesquid
2
bahkan CAML (dan OCAML, F #) memerlukan fungsi rekursif yang ditandai secara eksplisit.
jk.
1
@ Panzercrisis: Saya tidak yakin apakah IBM terlibat dalam x86, tetapi mainframe mereka saat ini melacak langsung kembali ke IBM 360, yang muncul di pasaran pada tahun 1964, sehingga desain dasar mendahului x86 oleh beberapa dekade atau lebih.
Jerry Coffin
16

Wikipedia mengatakan:

Bahasa awal seperti Fortran pada awalnya tidak mendukung rekursi karena variabel dialokasikan secara statis, serta lokasi untuk alamat pengirim.

http://en.wikipedia.org/wiki/Subroutine#Local_variables.2C_recursion_and_re-entrancy

FORTRAN 77 tidak memungkinkan rekursi, Fortran 90 tidak, (rutin rekursif harus secara eksplisit dinyatakan demikian).

Sebagian besar kompiler FORTRAN 77 memungkinkan rekursi, beberapa (misalnya DEC) memerlukan penggunaan opsi kompiler (lihat bab opsi kompiler). GNU G77, yang sepenuhnya sesuai dengan standar Fortran 77, tidak memungkinkan rekursi sama sekali.

http://www.ibiblio.org/pub/languages/fortran/ch1-12.html

Robert Harvey
sumber
iirc ada setidaknya satu kompiler FORTRAN 77 yang, sementara secara teknis mendukung rekursi, jumlah total frame tumpukan yang Anda miliki adalah rekursi kecil sehingga tidak dapat digunakan secara efektif untuk banyak masalah
jk.
6

Bahasa pemrograman OpenCL tidak mendukung rekursi. (lihat bagian 6.8 dari Spesifikasi OpenCL )

Motivasi saat ini untuk itu adalah a) kurangnya ruang untuk tumpukan yang dalam b) keinginan untuk mengetahui, secara statis, total alokasi yang diperlukan untuk mengoptimalkan kinerja di hadapan set register besar dan in-lining yang luas.

Ini mungkin berlaku untuk bahasa pemrograman GPU lainnya, misalnya bahasa shader.

grrussel
sumber
2

Beberapa c compiler untuk mikrokontroler kecil tidak mendukung rekursi, mungkin karena mereka memiliki ukuran stack yang sangat terbatas.

Jeanne Pindar
sumber
Beberapa dari mikrokontroler tersebut (mis. Keluarga PIC16) hanya memiliki stack panggilan perangkat keras (tidak dapat diakses dengan instruksi) dan tidak memiliki bentuk stack lain, sehingga fungsi tidak dapat memiliki variabel lokal saat menggunakan rekursi (karena tumpukan data jelas diperlukan untuk itu ...) Referensi: en.wikipedia.org/wiki/PIC_microcontroller#Stacks
Ale
1

BASIC, pada zaman bilangan garis, cenderung memiliki dukungan rekursi yang buruk. Banyak (semua?) DASAR waktu itu mendukung panggilan gosub bersarang, tetapi tidak mendukung cara mudah melewati parameter atau mengembalikan nilai dengan cara yang membuatnya berguna untuk melakukan panggilan sendiri.

Banyak komputer awal memiliki masalah dengan rekursi, karena mereka menggunakan instruksi panggilan yang menulis alamat kembali ke awal rutin yang disebut (PDP8, keluarga mesin IAS, mungkin lebih banyak arsitektur yang saya tidak terbiasa dengan), biasanya dengan cara seperti itu adalah kode mesin untuk "Lompat ke instruksi setelah yang memanggil rutin".

Vatine
sumber
1

Itu tergantung pada apa yang Anda maksud dengan " dukungan ". Untuk mendukung rekursi, Anda perlu tumpukan tempat instantiate variabel lokal di setiap masuk kembali.

Bahkan jika bahasa tidak memiliki konsep variabel lokal, jika memiliki konsep "subrutin" dan memiliki cara untuk mengelola pengindeksan antara variabel identik (alias array), Anda dapat menambah / mengurangi indeks global pada setiap masuk / keluar dari suatu fungsi dan akses melalui itu anggota dari satu atau lebih array.

Saya tidak tahu apakah ini bisa disebut "dukungan". Faktanya adalah bahwa saya menulis fungsi rekursif dengan ZX-Spectrum BASIC, seperti yang saya lakukan di Fortran77 seperti pada COBOL ... selalu dengan trik itu.

Emilio Garavaglia
sumber
1

Bahasa assembly tidak secara langsung mendukung rekursi - Anda harus "melakukannya sendiri", biasanya dengan mendorong parameter ke tumpukan mesin.

mikera
sumber
2
Ini mendukung rekursi sejauh mendukung panggilan metode. Biasanya ada CALLinstruksi, yang secara otomatis mendorong IP ke stack sebelum melompat ke subrutin, dan RETinstruksi yang muncul alamat pengirim ke IP. Tidak ada alasan Anda tidak bisa CALLmemasukkan titik masuk Anda sendiri.
Blorgbeard
@ Blorgbeard - benar-benar benar, walaupun saya berpendapat bahwa ini tidak cukup untuk dihitung sebagai "mendukung rekursi" dalam pengertian yang umum dipahami karena tidak menangani parameter yang diperlukan untuk panggilan rekursif.
mikera
1
Yah, panggilan rekursif tidak secara teknis membutuhkan parameter, kan? void f() { f(); }bersifat rekursif.
Blorgbeard
Secara teknis, tidak. Tetapi bisa kode satu kasus sepele tidak IMHO berarti bahwa Anda harus menggambarkan perakitan sebagai "rekursi pendukung". Penggunaan rekursi yang paling praktis membutuhkan parameter.
mikera
Saya kira Anda bisa mengatakan itu. Tetapi dalam kasus itu, perakitan juga tidak mendukung loop (Anda harus secara manual CMP dan JNZ). Saya kira itu masalah apa yang Anda sebut "mendukung".
Blorgbeard