Bisakah semua fungsi rekursif dikodekan dengan iterasi? [Tutup]

Apa keuntungan dari rekursi?

Beberapa bahasa pemrograman dapat mengoptimalkan rekursi ekor, tetapi, secara umum, rekursi memakan lebih banyak sumber daya daripada loop biasa.

Apakah mungkin untuk memiliki versi berulang dari beberapa fungsi rekursif?

Ya, Anda bisa mengkode fungsi rekursif sebagai iterasi. Ini pada dasarnya mengharuskan Anda untuk mempertahankan informasi secara manual yang jika tidak akan dijaga oleh metode kode panggilan yang dihasilkan oleh kompiler.

Dengan kata lain, Anda memerlukan tumpukan di mana setiap entri adalah struktur yang berisi parameter yang dikirimkan dan semua variabel lokal. Anda selalu bekerja pada entri paling atas di tumpukan. Jika Anda perlu menelepon diri sendiri, buat entri baru dan letakkan di atas tumpukan. Setelah selesai ambil entri paling atas dari tumpukan yang mengekspos yang di bawah ini, dan gunakan entri yang sebelumnya paling atas untuk mengekstrak nilai kembali dan perbarui entri paling atas yang baru.

Saya sarankan Anda mempelajari buku kompiler untuk melihat bagaimana ini biasanya diimplementasikan dalam kode mesin.

Rekursi seringkali merupakan cara yang lebih alami dalam memandang berbagai hal daripada iterasi. Sebagai contoh, pertimbangkan inorder traversal dari pohon biner: inorder(left); process(); inorder(right);jauh lebih sederhana daripada mempertahankan stack secara eksplisit.

Selama Anda tidak terlalu dalam (meniup tumpukan), perbedaan dalam penggunaan sumber daya biasanya sepele. Jangan khawatir tentang hal itu secara umum. Kode sederhana biasanya lebih baik daripada kode yang dioptimalkan dengan tangan, meskipun ada pengecualian. Kanan biasanya lebih baik daripada cepat.

Algoritma rekursif apa pun dapat dinyatakan sebagai algoritme berulang, tetapi Anda mungkin perlu menyimpan tumpukan eksplisit (sesuai dengan tumpukan panggilan yang ditangani secara implisit). Lagi pula, jika Anda mengompilasi fungsi rekursif, Anda mendapatkan sesuatu yang bergantung pada memanipulasi tumpukan dan perulangan melalui fungsi, dan itu berulang.

Fungsi tail-recursive dapat dengan mudah diterjemahkan ke dalam loop, dan tidak perlu tumpukan, tapi itu kasus khusus.

Apa keuntungan dari rekursi?

Cobalah memecahkan masalah Menara Hanoi secara berulang. Setelah Anda menyerah, lihatlah solusi iteratif dan bandingkan dengan solusi rekursif. Yang mana yang lebih sederhana?

Apakah mungkin untuk memiliki versi berulang dari beberapa fungsi rekursif?

Ya, pada prinsipnya. Namun untuk banyak masalah, termasuk tugas yang sangat umum, seperti melintasi pohon, solusi rekursif jauh lebih sederhana dan lebih elegan daripada yang berulang.

Apa keuntungan dari rekursi?

Kesederhanaan. Tanpa optimasi tail-call tentu saja membutuhkan lebih banyak sumber daya (stack), tetapi bagaimana Anda menerapkan, katakanlah, deltreedi Jawa tanpa rekursi? Twist adalah yang delete()dapat menghapus direktori hanya jika mereka kosong; ini dia dengan rekursi:

deltree(File fileOrDirectory) {
    if (fileOrDirectory.isDirectory()) {
        for (File subFileOrDirectory : fileOrDirectory.listFiles()) {
            deltree(subFileOrDirectory);
        }
    }
    fileOrDirectory.delete();
}

Saya percaya bahwa rekursi adalah salah satu alat yang harus dimiliki oleh seorang programmer . Dengan rekursi Anda dapat "memikirkan" algoritme Anda dan menyelesaikannya persis seperti yang Anda pikirkan. Tapi, saya harus memperingatkan Anda, semua orang berbicara tentang betapa cantiknya rekursi dan seberapa banyak kesederhanaan yang dibawa ke kode, mengenai hal itu saya punya beberapa hal untuk dikatakan:

1. Pertama-tama, memikirkan "cara rekursif" suatu algoritma tidaklah mudah. Membangun fungsi seperti faktorial (n!) Atau sesuatu seperti Menara Hanoi hanyalah puncak gunung es, dan mencapai dasar membutuhkan waktu yang lama.
2. Jangan berpikir bahwa rekursi membawa kesederhanaan hanya ke dalam kode Anda, kadang-kadang, cara iteratif jelek dan berantakan, tetapi hemat biaya (lihat solusi rekursif dari masalah Fibonacci)

Mempertimbangkan hal-hal itu, pelajari rekursi! itu lucu, rumit dan itu akan menghancurkan otak Anda !, tetapi Anda akan mendapati diri Anda menyukainya.

Semoga berhasil!