Apakah loop sementara pada dasarnya merupakan rekursi?

Saya bertanya-tanya apakah loop sementara pada dasarnya merupakan rekursi?

Saya pikir itu karena loop sementara dapat dilihat sebagai fungsi yang memanggil dirinya sendiri pada akhirnya. Jika bukan rekursi, lalu apa bedanya?

Loop sangat tidak rekursi. Bahkan, mereka adalah contoh utama dari mekanisme yang berlawanan : iterasi .

Titik rekursi adalah bahwa satu elemen pemrosesan memanggil instance lain dari dirinya sendiri. Mesin kontrol loop hanya melompat kembali ke titik di mana ia dimulai.

Melompati kode dan memanggil blok kode lain adalah operasi yang berbeda. Misalnya, ketika Anda melompat ke awal loop, variabel kontrol loop masih memiliki nilai yang sama sebelum melompat. Tetapi jika Anda memanggil instance lain dari rutin Anda, maka instance baru memiliki salinan semua variabel yang baru dan tidak terkait . Secara efektif, satu variabel dapat memiliki satu nilai pada tingkat pemrosesan pertama dan nilai lainnya pada tingkat yang lebih rendah.

Kemampuan ini sangat penting untuk banyak algoritma rekursif untuk bekerja, dan inilah sebabnya Anda tidak dapat meniru rekursi melalui iterasi tanpa juga mengelola tumpukan frame yang disebut yang melacak semua nilai-nilai itu.

Mengatakan bahwa X secara intrinsik Y hanya masuk akal jika Anda memiliki beberapa sistem (formal) dalam pikiran bahwa Anda mengekspresikan X masuk. Jika Anda mendefinisikan semantik whiledalam hal kalkulus lambda, Anda mungkin menyebutkan rekursi *; jika Anda mendefinisikannya dalam hal mesin register, Anda mungkin tidak akan melakukannya.

Dalam kedua kasus tersebut, orang mungkin tidak akan mengerti Anda jika Anda memanggil fungsi rekursif hanya karena mengandung loop sementara.

* Meskipun mungkin hanya secara tidak langsung, misalnya jika Anda mendefinisikannya dari segi fold.

Ini tergantung pada sudut pandang Anda.

Jika Anda melihat teori komputabilitas , maka iterasi dan rekursi sama - sama ekspresif . Artinya, Anda dapat menulis fungsi yang menghitung sesuatu, dan tidak masalah apakah Anda melakukannya secara berulang atau berulang, Anda akan dapat memilih kedua pendekatan tersebut. Tidak ada yang dapat Anda hitung secara rekursif yang tidak dapat Anda hitung secara iteratif dan sebaliknya (walaupun cara kerja internal program mungkin berbeda).

Banyak bahasa pemrograman tidak memperlakukan rekursi dan iterasi sama, dan untuk alasan yang baik. Biasanya , rekursi berarti bahwa bahasa / kompiler menangani tumpukan panggilan, dan iterasi berarti Anda harus melakukan sendiri penanganan tumpukan.

Namun, ada bahasa - terutama bahasa fungsional - di mana hal-hal seperti loop (untuk, sementara) memang hanya gula sintaksis untuk rekursi dan diimplementasikan di belakang layar seperti itu. Ini sering diinginkan dalam bahasa fungsional, karena mereka biasanya tidak memiliki konsep perulangan sebaliknya, dan menambahkannya akan membuat kalkulus mereka lebih kompleks, untuk alasan praktis yang sedikit.

Jadi tidak, mereka pada dasarnya tidak sama . Mereka sama - sama ekspresif , yang berarti Anda tidak dapat menghitung sesuatu secara iteratif Anda tidak dapat menghitung secara rekursif dan sebaliknya, tetapi itu saja, dalam kasus umum (menurut tesis Church-Turing).

Perhatikan bahwa kita berbicara tentang program rekursif di sini. Ada bentuk rekursi lain, misalnya dalam struktur data (misalnya pohon).

Jika Anda melihatnya dari sudut pandang implementasi , maka rekursi dan iterasi hampir tidak sama. Rekursi menciptakan bingkai tumpukan baru untuk setiap panggilan. Setiap langkah rekursi adalah mandiri, mendapatkan argumen untuk perhitungan dari callee (sendiri).

Loop di sisi lain tidak membuat bingkai panggilan. Bagi mereka, konteksnya tidak dipertahankan pada setiap langkah. Untuk loop, program hanya melompat kembali ke awal loop sampai kondisi loop gagal.

Ini cukup penting untuk diketahui, karena dapat membuat perbedaan yang cukup radikal di dunia nyata. Untuk rekursi, seluruh konteks harus disimpan pada setiap panggilan. Untuk iterasi, Anda memiliki kontrol yang tepat tentang variabel apa yang ada dalam memori dan apa yang disimpan di mana.

Jika Anda melihatnya seperti itu, Anda dengan cepat melihat bahwa untuk sebagian besar bahasa, iterasi dan rekursi pada dasarnya berbeda dan memiliki sifat yang berbeda. Tergantung pada situasinya, beberapa properti lebih diinginkan daripada yang lain.

Rekursi dapat membuat program lebih sederhana dan lebih mudah untuk diuji dan dibuktikan . Mengubah rekursi menjadi iterasi biasanya membuat kode lebih kompleks, meningkatkan kemungkinan kegagalan. Di sisi lain, mengkonversi ke iterasi dan mengurangi jumlah frame stack panggilan dapat menghemat banyak memori yang dibutuhkan.

Perbedaannya adalah tumpukan implisit dan semantik.

Loop sementara yang "memanggil dirinya sendiri di akhir" tidak memiliki tumpukan untuk dirayapi kembali setelah selesai. Iterasi terakhir menentukan keadaan apa yang akan terjadi.

Namun rekursi tidak dapat dilakukan tanpa tumpukan implisit yang mengingat kondisi kerja yang dilakukan sebelumnya.

Memang benar bahwa Anda dapat memecahkan masalah rekursi dengan iterasi jika Anda memberikannya akses ke tumpukan secara eksplisit. Tetapi melakukannya dengan cara yang tidak sama.

Perbedaan semantik berkaitan dengan fakta bahwa melihat kode rekursif menyampaikan ide dengan cara yang sama sekali berbeda dari kode iteratif. Kode berulang melakukan beberapa langkah sekaligus. Ia menerima keadaan apa pun yang datang dari sebelumnya dan hanya berfungsi untuk menciptakan negara berikutnya.

Kode rekursif memecah masalah menjadi fraktal. Bagian kecil ini terlihat seperti bagian yang besar sehingga kita dapat melakukan sedikit saja dan sedikit saja dengan cara yang sama. Ini cara yang berbeda untuk memikirkan masalah. Ini sangat kuat dan perlu terbiasa. Banyak yang bisa dikatakan dalam beberapa baris. Anda tidak bisa mengeluarkannya dari loop sementara meskipun ia memiliki akses ke stack.

Itu semua bergantung pada penggunaan istilah itu secara intrinsik . Pada tingkat bahasa pemrograman, mereka secara sintaktis dan semantik berbeda, dan mereka memiliki kinerja dan penggunaan memori yang sangat berbeda. Tetapi jika Anda menggali cukup dalam ke teori mereka dapat didefinisikan dalam hal satu sama lain, dan karena itu "sama" dalam beberapa pengertian teoritis.

Pertanyaan sebenarnya adalah: Kapan masuk akal untuk membedakan antara iterasi (loop) dan rekursi, dan kapan berguna untuk menganggapnya sebagai hal yang sama? Jawabannya adalah bahwa ketika benar-benar pemrograman (yang bertentangan dengan penulisan bukti matematika) adalah penting untuk membedakan antara iterasi dan rekursi.

Rekursi menciptakan bingkai tumpukan baru, yaitu seperangkat variabel lokal baru untuk setiap panggilan. Ini memiliki overhead, dan memakan ruang pada stack, yang berarti bahwa rekursi yang cukup dalam dapat meluap stack yang menyebabkan program crash. Iterasi di sisi lain hanya memodifikasi variabel yang ada sehingga umumnya lebih cepat dan hanya memakan jumlah memori yang konstan. Jadi ini adalah perbedaan yang sangat penting bagi pengembang!

Dalam bahasa dengan rekursi ekor-panggilan (biasanya bahasa fungsional), kompiler mungkin dapat mengoptimalkan panggilan rekursif sedemikian rupa sehingga mereka hanya memakan jumlah memori yang konstan. Dalam bahasa-bahasa itu perbedaan penting bukanlah iterasi vs rekursi, melainkan versi non-ekor-rekursi-rekursi dan iterasi.

Intinya: Anda harus bisa membedakannya, kalau tidak program Anda akan macet.

whileloop adalah bentuk rekursi, lihat misalnya jawaban yang diterima untuk pertanyaan ini . Mereka sesuai dengan operator-μ dalam teori komputabilitas (lihat misalnya di sini ).

Semua variasi forloop yang iterate pada rentang angka, koleksi hingga, array, dan sebagainya, sesuai dengan rekursi primitif, lihat misalnya di sini dan di sini . Perhatikan bahwa forloop C, C ++, Java, dan sebagainya, sebenarnya adalah gula sintaksis untuk satu whileloop, dan karena itu tidak berhubungan dengan rekursi primitif. forLoop Pascal adalah contoh rekursi primitif.

Perbedaan penting adalah bahwa rekursi primitif selalu berakhir, sedangkan rekursi umum ( whileloop) mungkin tidak berakhir.

EDIT

Beberapa klarifikasi mengenai komentar dan jawaban lainnya. "Rekursi terjadi ketika sesuatu didefinisikan berdasarkan dirinya sendiri atau jenisnya." (lihat wikipedia ). Begitu,

Apakah loop sementara pada dasarnya merupakan rekursi?

Karena Anda dapat menentukan whileloop dalam hal itu sendiri

while p do c := if p then (c; while p do c))

maka, ya , satu whilelingkaran adalah bentuk rekursi. Fungsi rekursif adalah bentuk rekursi lain (contoh lain dari definisi rekursif). Daftar dan pohon adalah bentuk rekursi lainnya.

Pertanyaan lain yang secara implisit diasumsikan oleh banyak jawaban dan komentar adalah

Apakah sementara loop dan fungsi rekursif sama?

Jawaban untuk pertanyaan ini adalah tidak : whileLoop berhubungan dengan fungsi rekursif ekor, di mana variabel yang diakses oleh loop sesuai dengan argumen fungsi rekursif implisit, tetapi, seperti yang telah ditunjukkan orang lain, fungsi non-ekor-rekursif tidak dapat dimodelkan dengan whileloop tanpa menggunakan tumpukan tambahan.

Jadi, fakta bahwa " whileloop adalah bentuk rekursi" tidak bertentangan dengan fakta bahwa "beberapa fungsi rekursif tidak dapat diekspresikan oleh whileloop".

Sebuah panggilan ekor (atau ekor panggilan rekursif) adalah persis diimplementasikan sebagai "goto dengan argumen" (tanpa mendorong setiap tambahan bingkai panggilan pada panggilan stack ) dan dalam beberapa bahasa fungsional (Ocaml terutama) adalah cara yang biasa perulangan.

Jadi loop sementara (dalam bahasa yang memilikinya) dapat dilihat sebagai berakhir dengan panggilan ekor ke tubuhnya (atau tes kepalanya).

Demikian juga, panggilan rekursif biasa (non-tail-call) dapat disimulasikan dengan loop (menggunakan beberapa tumpukan).

Baca juga tentang kelanjutan dan gaya kelanjutan-kelanjutan .

Jadi "rekursi" dan "iterasi" sangat setara.

Memang benar bahwa rekursi dan loop-sementara yang tidak terikat sama dalam hal ekspresifitas komputasi. Artinya, setiap program yang ditulis secara rekursif dapat ditulis ulang menjadi program yang setara menggunakan loop sebagai gantinya, dan sebaliknya. Kedua pendekatan tersebut turing-complete , yang dapat digunakan untuk menghitung fungsi yang dapat dihitung.

Perbedaan mendasar dalam hal pemrograman adalah rekursi memungkinkan Anda untuk menggunakan data yang disimpan di tumpukan panggilan. Untuk mengilustrasikan ini, anggap Anda ingin mencetak elemen dari daftar yang terhubung sendiri menggunakan loop atau rekursi. Saya akan menggunakan C untuk kode contoh:

 typedef struct List List;
 struct List
 {
     List* next;
     int element;
 };

 void print_list_loop(List* l)
 {
     List* it = l;
     while(it != NULL)
     {
          printf("Element: %d\n", it->element);
          it = it->next;
     }
 }

 void print_list_rec(List* l)
 {
      if(l == NULL) return;
      printf("Element: %d\n", l->element);
      print_list_rec(l->next);
 }

Sederhana bukan? Sekarang mari kita buat sedikit modifikasi: Cetak daftar dalam urutan terbalik.

Untuk varian rekursif, ini adalah modifikasi yang hampir sepele untuk fungsi aslinya:

void print_list_reverse_rec(List* l)
{
    if (l == NULL) return;
    print_list_reverse_rec(l->next);
    printf("Element: %d\n", l->element);
}

Untuk fungsi loop, kami memiliki masalah. Daftar kami terhubung sendiri-sendiri dan dengan demikian hanya dapat dilalui ke depan. Tetapi karena kita mencetak secara terbalik, kita harus mulai mencetak elemen terakhir. Setelah kami mencapai elemen terakhir, kami tidak dapat kembali ke elemen kedua hingga terakhir.

Jadi kita harus melakukan banyak traversing ulang, atau kita harus membangun struktur data tambahan yang melacak elemen yang dikunjungi dan kemudian mencetak dengan efisien.

Mengapa kita tidak memiliki masalah dengan rekursi? Karena dalam rekursi kita sudah memiliki struktur data tambahan di tempat: Function call stack.

Karena rekursi memungkinkan kita untuk kembali ke permintaan sebelumnya dari panggilan rekursif, dengan semua variabel lokal dan keadaan untuk panggilan itu masih utuh, kita mendapatkan beberapa fleksibilitas yang akan membosankan untuk dimodelkan dalam kasus iteratif.

Loop adalah bentuk khusus dari rekursi untuk mencapai tugas tertentu (kebanyakan iterasi). Seseorang dapat mengimplementasikan loop dalam gaya rekursif dengan kinerja yang sama [1] dalam beberapa bahasa. dan dalam SICP [2], Anda dapat melihat bahwa loop digambarkan sebagai "gula sintaksis". Dalam sebagian besar bahasa pemrograman imperatif, untuk dan sementara blok menggunakan lingkup yang sama dengan fungsi induknya. Meskipun demikian, di sebagian besar bahasa pemrograman fungsional tidak ada atau tidak ada loop karena tidak ada kebutuhan untuk mereka.

Alasan bahasa imperatif memiliki untuk / sementara loop adalah karena mereka menangani negara dengan memutasikan mereka. Tetapi sebenarnya, jika Anda melihat dari perspektif yang berbeda, jika Anda menganggap blok sementara sebagai fungsi itu sendiri, mengambil parameter, memprosesnya, dan mengembalikan status baru - yang juga bisa menjadi panggilan fungsi yang sama dengan parameter yang berbeda - Anda dapat menganggap loop sebagai rekursi.

Dunia juga bisa didefinisikan sebagai bisa berubah atau tidak berubah. jika kita mendefinisikan dunia sebagai seperangkat aturan, dan memanggil fungsi pamungkas yang mengambil semua aturan, dan status saat ini sebagai parameter, dan mengembalikan negara baru sesuai dengan parameter ini yang memiliki fungsi yang sama (menghasilkan negara berikutnya di sama cara), kita juga bisa mengatakan itu adalah rekursi dan loop.

dalam contoh berikut, hidup adalah fungsi mengambil dua parameter "aturan" dan "negara", dan negara baru akan dibangun di centang waktu berikutnya.

life rules state = life rules new_state
    where new_state = construct_state_in_time rules state

[1]: optimisasi panggilan ekor adalah optimisasi umum dalam bahasa pemrograman fungsional untuk menggunakan tumpukan fungsi yang ada dalam panggilan rekursif alih-alih membuat yang baru.

[2]: Struktur dan Interpretasi Program Komputer, MIT. https://mitpress.mit.edu/books/structure-and-interpretation-computer-programs

Loop sementara berbeda dari rekursi.

Ketika suatu fungsi dipanggil, berikut ini terjadi:

1. Bingkai tumpukan ditambahkan ke tumpukan.

2. Penunjuk kode bergerak ke awal fungsi.

Ketika beberapa saat loop pada akhirnya terjadi sebagai berikut:

1. Suatu kondisi menanyakan apakah sesuatu itu benar.

2. Jika demikian, kode tersebut melompat ke suatu titik.

Secara umum, loop sementara mirip dengan pseudocode berikut:

 if (x)

 {

      Jump_to(y);

 }

Yang paling penting, rekursi dan loop memiliki representasi kode rakitan yang berbeda, dan representasi kode mesin. Ini berarti mereka tidak sama. Mereka mungkin memiliki hasil yang sama, tetapi kode mesin yang berbeda membuktikan bahwa mereka tidak 100% hal yang sama.

Hanya iterasi tidak cukup untuk secara umum setara dengan rekursi, tetapi iterasi dengan stack umumnya setara. Setiap fungsi rekursif dapat diprogram ulang sebagai loop berulang dengan stack, dan sebaliknya. Ini tidak berarti bahwa itu praktis, dan dalam situasi tertentu, satu atau bentuk lain mungkin memiliki manfaat yang jelas dibandingkan versi lainnya.

Saya tidak yakin mengapa ini kontroversial. Rekursi dan iterasi dengan stack adalah proses komputasi yang sama. Mereka adalah "fenomena" yang sama, bisa dikatakan.

Satu-satunya hal yang dapat saya pikirkan adalah bahwa ketika melihat ini sebagai "alat pemrograman", saya setuju bahwa Anda tidak harus menganggapnya sebagai hal yang sama. Mereka setara "secara matematis" atau "secara komputasi" (lagi iterasi dengan stack , bukan iterasi pada umumnya), tetapi itu tidak berarti Anda harus mendekati masalah dengan pemikiran bahwa salah satu akan melakukannya. Dari sudut pandang implementasi / penyelesaian masalah, beberapa masalah mungkin bekerja lebih baik dengan satu cara atau yang lain, dan pekerjaan Anda sebagai programmer adalah memutuskan dengan benar mana yang lebih cocok.

Untuk memperjelas, jawaban atas pertanyaan Apakah perulangan sementara secara intrinsik merupakan rekursi? adalah tidak pasti , atau setidaknya "tidak kecuali Anda memiliki tumpukan juga".