Rekursi atau saat loop

Saya membaca tentang beberapa praktik pengembangan wawancara, khususnya tentang pertanyaan teknis dan tes yang diajukan pada wawancara dan saya telah beberapa kali tersandung kata-kata dari genre "Ok Anda memecahkan masalah dengan loop sementara, sekarang Anda dapat melakukannya dengan rekursi ", atau" semua orang bisa menyelesaikan ini dengan 100 baris sementara loop, tetapi bisakah mereka melakukannya dalam fungsi rekursif 5 garis? " dll.

Pertanyaan saya adalah, apakah rekursi umumnya lebih baik daripada jika / sementara / untuk konstruksi?

Sejujurnya saya selalu berpikir bahwa rekursi tidak disukai, karena terbatas pada memori tumpukan yang jauh lebih kecil daripada tumpukan, juga melakukan sejumlah besar panggilan fungsi / metode yang tidak optimal dari sudut pandang kinerja, tapi saya mungkin salah ...

Rekursi secara intrinsik tidak lebih baik atau lebih buruk daripada loop - masing-masing memiliki kelebihan dan kekurangan, dan mereka bahkan tergantung pada bahasa pemrograman (dan implementasi).

Secara teknis, loop berulang sesuai dengan sistem komputer tipikal yang lebih baik pada tingkat perangkat keras: pada tingkat kode mesin, satu lingkaran hanyalah sebuah tes dan lompatan bersyarat, sedangkan rekursi (diimplementasikan secara naif) melibatkan mendorong bingkai tumpukan, melompat, kembali, dan muncul kembali dari tumpukan. OTOH, banyak kasus rekursi (terutama yang sepele setara dengan loop berulang) dapat ditulis sehingga stack push / pop dapat dihindari; ini dimungkinkan ketika pemanggilan fungsi rekursif adalah hal terakhir yang terjadi dalam fungsi body sebelum kembali, dan itu umumnya dikenal sebagai pengoptimalan panggilan ekor (atau pengoptimalan pengulangan ekor ). Fungsi rekursif yang dioptimalkan tail-call-dioptimalkan sebagian besar setara dengan loop berulang pada tingkat kode mesin.

Pertimbangan lain adalah bahwa loop berulang membutuhkan pembaruan keadaan destruktif, yang membuatnya tidak kompatibel dengan semantik bahasa murni (efek samping). Ini adalah alasan mengapa bahasa murni seperti Haskell tidak memiliki konstruksi loop sama sekali, dan banyak bahasa pemrograman fungsional lainnya tidak memiliki mereka sepenuhnya atau menghindarinya sebanyak mungkin.

Alasan mengapa pertanyaan-pertanyaan ini muncul begitu banyak dalam wawancara, adalah karena untuk menjawabnya, Anda memerlukan pemahaman menyeluruh tentang banyak konsep pemrograman vital - variabel, pemanggilan fungsi, cakupan, dan tentu saja loop dan rekursi -, dan Anda memiliki untuk membawa fleksibilitas mental ke meja yang memungkinkan Anda untuk mendekati masalah dari dua sudut yang sangat berbeda, dan bergerak di antara berbagai manifestasi dari konsep yang sama.

Pengalaman dan penelitian menunjukkan bahwa ada garis antara orang yang memiliki kemampuan untuk memahami variabel, petunjuk, dan rekursi, dan mereka yang tidak. Hampir semua hal lain dalam pemrograman, termasuk kerangka kerja, API, bahasa pemrograman, dan kasus tepi mereka, dapat diperoleh melalui pembelajaran dan pengalaman, tetapi jika Anda tidak dapat mengembangkan intuisi untuk ketiga konsep inti ini, Anda tidak layak menjadi seorang programmer. Menerjemahkan loop berulang sederhana ke versi rekursif adalah tentang cara tercepat yang mungkin untuk menyaring non-programmer - bahkan seorang programmer yang agak tidak berpengalaman biasanya dapat melakukannya dalam 15 menit, dan ini merupakan masalah agnostik bahasa yang sangat, sehingga kandidat dapat memilih bahasa pilihan mereka alih-alih tersandung keanehan.

Jika Anda mendapatkan pertanyaan seperti ini dalam sebuah wawancara, itu pertanda baik: itu artinya calon majikan mencari orang yang bisa memprogram, bukan orang yang hafal manual alat pemrograman.

Tergantung.

• Beberapa masalah sangat cocok untuk solusi rekursif misalnya quicksort
• Beberapa bahasa tidak benar-benar mendukung rekursi misalnya FORTRAN awal
• Beberapa bahasa menganggap rekursi sebagai sarana utama untuk pengulangan misalnya Haskell

Perlu juga dicatat bahwa dukungan untuk rekursi ekor membuat loop rekursif dan berulang berulang, yaitu, rekursi tidak selalu harus membuang tumpukan.

Juga, algoritma rekursif selalu dapat diimplementasikan secara iteratif dengan menggunakan stack eksplisit .

Akhirnya, saya perhatikan bahwa solusi lima baris mungkin selalu lebih baik daripada 100 baris satu (dengan asumsi mereka sebenarnya setara).

Tidak ada kesepakatan universal tentang definisi "lebih baik" dalam hal pemrograman, tetapi saya akan mengartikannya sebagai "lebih mudah untuk mempertahankan / membaca".

Rekursi memiliki kekuatan lebih ekspresif daripada konstruksi berulang berulang: Saya mengatakan ini karena loop sementara setara dengan fungsi rekursif ekor dan fungsi rekursif tidak perlu ekor rekursif. Konstruksi yang kuat biasanya merupakan hal yang buruk karena memungkinkan Anda melakukan hal-hal yang sulit dibaca. Namun, rekursi memberi Anda kemampuan untuk menulis loop tanpa menggunakan kemampuan berubah-ubah dan bagi saya, kemampuan berubah jauh lebih kuat daripada rekursi.

Jadi, dari daya ekspresif rendah hingga daya ekspresif tinggi, susunan looping disusun seperti ini:

• Ekor fungsi rekursif yang menggunakan data tidak berubah,
• Fungsi rekursif yang menggunakan data tidak berubah,
• Sementara loop yang menggunakan data yang bisa diubah,
• Ekor fungsi rekursif yang menggunakan data bisa berubah,
• Fungsi rekursif yang menggunakan data yang bisa diubah,

Idealnya, Anda akan menggunakan konstruksi paling ekspresif yang Anda bisa. Tentu saja, jika bahasa Anda tidak mendukung pengoptimalan panggilan ekor, maka itu juga dapat memengaruhi pilihan Anda untuk membuat perulangan.

Rekursi seringkali kurang jelas. Kurang jelas lebih sulit dipertahankan.

Jika Anda menulis for(i=0;i<ITER_LIMIT;i++){somefunction(i);}di arus utama, Anda membuatnya sangat jelas bahwa Anda sedang menulis loop. Jika Anda menulis, somefunction(ITER_LIMIT);Anda tidak benar-benar menjelaskan apa yang akan terjadi. Hanya melihat konten: somefunction(int x)panggilan itu somefunction(x-1)memberi tahu Anda bahwa itu sebenarnya sebuah loop menggunakan iterasi. Juga, Anda tidak dapat dengan mudah menempatkan kondisi pelarian dengan break;suatu tempat di tengah-tengah iterasi, Anda harus menambahkan kondisional yang akan dilewati semua jalan kembali, atau melemparkan pengecualian. (dan pengecualian lagi menambah kompleksitas ...)

Intinya, jika itu pilihan yang jelas antara iterasi dan rekursi, lakukan hal yang intuitif. Jika iterasi melakukan pekerjaan dengan mudah, menyimpan 2 baris jarang sepadan dengan sakit kepala yang mungkin terjadi dalam jangka panjang.

Tentu saja jika itu menghemat 98 baris, itu masalah yang sama sekali berbeda.

Ada beberapa situasi di mana rekursi sangat cocok, dan mereka tidak terlalu jarang. Traversal struktur pohon, jaringan multiply-linked, struktur yang dapat mengandung tipenya sendiri, array bergerigi multi-dimensi, pada dasarnya segala sesuatu yang bukan vektor langsung atau array dimensi tetap. Jika Anda melintasi jalur yang dikenal dan lurus, lakukan iterate. Jika Anda menyelam ke yang tidak diketahui, kambuh.

Pada dasarnya, jika somefunction(x-1)dipanggil dari dalam dirinya sendiri lebih dari sekali per level, lupakan iterasi.

... Menulis secara iteratif berfungsi untuk tugas-tugas yang paling baik dilakukan dengan rekursi mungkin tetapi tidak menyenangkan. Di mana pun Anda menggunakan int, Anda membutuhkan sesuatu seperti stack<int>. Saya melakukannya sekali, lebih sebagai latihan daripada untuk tujuan praktis. Saya dapat meyakinkan Anda begitu Anda menghadapi tugas seperti itu Anda tidak akan memiliki keraguan seperti yang Anda ungkapkan.

Seperti biasa, ini tidak dapat dijawab secara umum karena ada faktor-faktor tambahan, yang dalam praktiknya secara luas tidak sama antara kasus dan tidak sama satu sama lain dalam kasus penggunaan. Inilah beberapa tekanannya.

• Kode pendek dan elegan pada umumnya lebih baik daripada kode panjang dan rumit.
• Namun, poin terakhir agak batal jika basis pengembang Anda tidak terbiasa dengan rekursi dan tidak mau / tidak bisa belajar. Bahkan mungkin menjadi sedikit negatif daripada positif.
• Rekursi dapat berakibat buruk bagi efisiensi jika Anda akan membutuhkan panggilan yang bersarang dalam praktik dan Anda tidak dapat menggunakan rekursi ekor (atau lingkungan Anda tidak dapat mengoptimalkan rekursi ekor).
• Rekursi juga buruk dalam banyak kasus jika Anda tidak dapat melakukan cache hasil menengah dengan benar. Sebagai contoh, contoh umum menggunakan rekursi pohon untuk menghitung angka Fibonacci berkinerja sangat buruk jika Anda tidak melakukan cache. Jika Anda melakukan cache, itu sederhana, cepat, elegan, dan sekaligus luar biasa indah.
• Rekursi tidak berlaku untuk beberapa kasus, sama baiknya dengan iterasi pada kasus lain, dan mutlak diperlukan pada kasus lainnya. Memanjat melalui rantai panjang aturan bisnis biasanya tidak tertolong oleh rekursi sama sekali. Iterasi melalui aliran data dapat bermanfaat dilakukan dengan rekursi. Iterasi lebih dari struktur data dinamis multidimensi (misalnya labirin, pohon objek ...) hampir tidak mungkin tanpa rekursi, eksplisit atau implisit. Perhatikan bahwa dalam kasus-kasus ini, rekursi eksplisit jauh lebih baik daripada implisit - tidak ada yang lebih menyakitkan daripada membaca kode di mana seseorang menerapkan tumpukan ad-hoc, tidak lengkap, dan tidak stabil dalam bahasa hanya untuk menghindari kata-R yang menakutkan.

Rekursi adalah tentang mengulangi panggilan ke fungsi, loop adalah tentang pengulangan melompat ke tempat di memori.

Harus disebutkan juga tentang stack overflow - http://en.wikipedia.org/wiki/Stack_overflow

Itu sangat tergantung pada kenyamanan atau persyaratan:

Jika Anda menggunakan bahasa pemrograman Python , ia mendukung rekursi, tetapi secara default ada batas untuk kedalaman rekursi (1000). Jika melebihi batas, kami akan mendapatkan kesalahan atau pengecualian. Batas itu dapat diubah, tetapi jika kita melakukannya kita mungkin mengalami situasi abnormal dalam bahasa.

Pada saat ini (jumlah panggilan lebih dari kedalaman rekursi), kita perlu memilih konstruksi lingkaran. Maksud saya, jika ukuran stack tidak cukup, kita harus memilih konstruksi loop.

Gunakan pola desain strategi.

• Rekursi bersih
• Loop (bisa dibilang) efisien

Bergantung pada beban Anda (dan / atau kondisi lainnya), pilih satu.