Saya telah menggunakan rekursi cukup banyak pada pemrograman saya selama bertahun-tahun untuk menyelesaikan masalah sederhana, tetapi saya sepenuhnya sadar bahwa kadang-kadang Anda membutuhkan iterasi karena masalah memori / kecepatan.
Jadi, suatu saat di masa lalu saya pergi untuk mencoba dan menemukan apakah ada "pola" atau cara buku teks untuk mengubah pendekatan rekursi umum untuk iterasi dan tidak menemukan apa pun. Atau setidaknya tidak ada yang saya ingat akan membantu.
- Apakah ada aturan umum?
- Apakah ada "pola"?
recursion
computer-science
theory
iteration
Gustavo Carreno
sumber
sumber
Jawaban:
Biasanya, saya mengganti algoritma rekursif dengan algoritma berulang dengan mendorong parameter yang biasanya dilewatkan ke fungsi rekursif ke tumpukan. Bahkan, Anda mengganti tumpukan program dengan salah satu dari Anda sendiri.
Catatan: jika Anda memiliki lebih dari satu panggilan rekursif di dalam dan Anda ingin mempertahankan urutan panggilan, Anda harus menambahkannya dalam urutan terbalik ke tumpukan:
harus diganti oleh
Sunting: Artikel Stacks and Elimination Recursion (atau Article Backup link ) menjelaskan lebih detail tentang hal ini.
sumber
(node)->()
dengan di(node)->[actions]
mana tindakan() -> [actions]
. Kemudian di bagian luar, Anda cukup memunculkan tindakan / kelanjutan dari tumpukan, menerapkan / menjalankannya, mendorong tindakan yang dikembalikan pada tumpukan secara terbalik agar dan ulangi. Kontingensi / kompleks traversal, Anda hanya menangkap apa yang akan menjadi variabel stack lokal dalam pointer yang dihitung referensi yang Anda tutup di thunks Anda, kemudian thunks selanjutnya dapat bergantung pada hasil sub-traversal sebelumnya dll.new
kita dapat membuat objek di heap, bukan stack. Tidak seperti stack, heap tidak memiliki batasan memori. Lihat gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.htmlSungguh, cara paling umum untuk melakukannya adalah dengan menyimpan tumpukan Anda sendiri. Inilah fungsi quicksort rekursif dalam C:
Inilah cara kami membuatnya berulang dengan menyimpan tumpukan kami sendiri:
Jelas, contoh ini tidak memeriksa batas-batas tumpukan ... dan Anda benar-benar dapat menentukan ukuran tumpukan berdasarkan kasus terburuk yang diberikan nilai kiri dan kanan. Tetapi Anda mendapatkan idenya.
sumber
O(N) = O(R*L)
, di manaL
jumlah kompleksitas "untuk layer r", misalnya dalam hal ini Anda memilikiO(N)
pekerjaan di setiap langkah melakukan partisi, kedalaman rekursif adalahO(R)
, yaitu kasus terburukO(N)
, kasus rata-rata diO(logN)
sini.Tampaknya tidak ada yang membahas di mana fungsi rekursif menyebut dirinya lebih dari satu kali dalam tubuh, dan menangani kembali ke titik tertentu dalam rekursi (yaitu tidak primitif-rekursif). Dikatakan bahwa setiap rekursi dapat diubah menjadi iterasi , sehingga tampaknya ini harus dimungkinkan.
Saya baru saja datang dengan contoh C # tentang bagaimana melakukan ini. Misalkan Anda memiliki fungsi rekursif berikut, yang bertindak seperti traversal postorder, dan AbcTreeNode adalah pohon 3-ary dengan pointer a, b, c.
Solusi berulang:
sumber
Berusaha keras untuk membuat panggilan rekursif Tail Recursion (rekursi di mana pernyataan terakhir adalah panggilan rekursif). Setelah Anda memilikinya, mengonversinya menjadi iterasi umumnya cukup mudah.
sumber
Nah, secara umum, rekursi dapat ditiru sebagai iterasi dengan hanya menggunakan variabel penyimpanan. Perhatikan bahwa rekursi dan iterasi umumnya setara; yang satu hampir selalu dapat dikonversi ke yang lain. Fungsi rekursif ekor sangat mudah dikonversi menjadi fungsi berulang. Buat saja variabel akumulator menjadi variabel lokal, dan lakukan iterasi alih-alih berulang. Berikut adalah contoh dalam C ++ (C kalau bukan karena penggunaan argumen default):
Mengenal saya, saya mungkin membuat kesalahan dalam kode, tetapi idenya ada di sana.
sumber
Bahkan menggunakan stack tidak akan mengubah algoritma rekursif menjadi iteratif. Rekursi normal adalah rekursi berbasis fungsi dan jika kita menggunakan stack maka itu menjadi rekursi berbasis stack. Tapi ini masih rekursi.
Untuk algoritma rekursif, kompleksitas ruang adalah O (N) dan kompleksitas waktu adalah O (N). Untuk algoritma iteratif, kompleksitas ruang adalah O (1) dan kompleksitas waktu adalah O (N).
Tetapi jika kita menggunakan tumpukan hal dalam hal kompleksitas tetap sama. Saya pikir hanya rekursi ekor yang dapat dikonversi menjadi iterasi.
sumber
copy = new int[size]; for(int i=0; i<size; ++i) copy[i] = source[i];
ruang memori dan kompleksitas waktu, keduanya O (N) berdasarkan pada ukuran data, tetapi itu jelas suatu algoritma iteratif.The tumpukan dan rekursi penghapusan pasal menangkap ide eksternalisasi stack frame di heap, tetapi tidak memberikan langsung dan berulang cara untuk mengkonversi. Di bawah ini adalah satu.
Saat mengonversi ke kode iteratif, orang harus sadar bahwa panggilan rekursif dapat terjadi dari blok kode yang sewenang-wenang. Ini bukan hanya parameter, tetapi juga titik untuk kembali ke logika yang masih harus dieksekusi dan keadaan variabel yang berpartisipasi dalam persyaratan berikutnya, yang penting. Di bawah ini adalah cara yang sangat sederhana untuk mengonversi ke kode berulang dengan sedikit perubahan.
Pertimbangkan kode rekursif ini:
Kode berulang:
Perhatikan bagaimana struktur kode masih tetap benar dengan logika rekursif dan modifikasi minimal, sehingga jumlah bug lebih sedikit. Sebagai perbandingan, saya telah menandai perubahan dengan ++ dan -. Sebagian besar blok yang dimasukkan baru kecuali v.push_back, umum untuk setiap logika iteratif yang dikonversi
+++++++++++++++++++++++++
------------------------
+++++++++++++++++++++++++
-------------------------
+++++++++++++++++++++++++
-------------------------
+++++++++++++++++++++++++
-------------------------
sumber
stackitem
objek dialokasikan dengan nilai sampahra
. Semuanya masih berfungsi dalam kasus yang paling mirip, tetapi jikara
kebetulan 1 atau 2 Anda akan mendapatkan perilaku yang salah. Solusinya adalah menginisialisasira
ke 0.stackitem
tidak boleh didorong tanpa menginisialisasi. Tapi ya, menginisialisasi ke 0 akan menangkap kesalahan.v.pop_back()
pernyataan?Cari di Google untuk "Gaya kelanjutan lulus." Ada prosedur umum untuk mengubah ke gaya rekursif ekor; ada juga prosedur umum untuk mengubah fungsi rekursif ekor menjadi loop.
sumber
Hanya menghabiskan waktu ... Fungsi rekursif
dapat dikonversi menjadi
sumber
Secara umum teknik untuk menghindari stack overflow adalah untuk fungsi rekursif disebut teknik trampolin yang banyak diadopsi oleh Java devs.
Namun, untuk C # ada metode pembantu kecil di sini yang mengubah fungsi rekursif Anda menjadi berulang tanpa perlu mengubah logika atau membuat kode tidak bisa dipahami. C # adalah bahasa yang sangat bagus sehingga hal-hal yang luar biasa dimungkinkan dengannya.
Ia bekerja dengan membungkus bagian-bagian metode dengan metode helper. Misalnya fungsi rekursif berikut:
Berubah menjadi:
sumber
Memikirkan hal-hal yang sebenarnya membutuhkan tumpukan:
Jika kita menganggap pola rekursi sebagai:
Misalnya, Menara klasik Hanoi
Ini dapat diterjemahkan ke dalam loop yang bekerja pada stack eksplisit, dengan menyatakannya kembali sebagai:
Untuk Menara Hanoi ini menjadi:
Ada banyak fleksibilitas di sini mengenai bagaimana Anda mendefinisikan tumpukan Anda. Anda dapat membuat tumpukan Anda daftar
Command
objek yang melakukan hal-hal canggih. Atau Anda dapat pergi ke arah yang berlawanan dan membuatnya menjadi daftar jenis yang lebih sederhana (misalnya "tugas" mungkin 4 elemen pada tumpukanint
, bukan satu elemen pada tumpukanTask
).Semua ini berarti bahwa memori untuk tumpukan berada di tumpukan daripada di tumpukan eksekusi Java, tetapi ini bisa berguna karena Anda memiliki kontrol lebih besar atas tumpukan itu.
sumber
Satu pola yang harus dicari adalah panggilan rekursi di akhir fungsi (disebut ekor-rekursi). Ini dapat dengan mudah diganti dengan sementara. Misalnya, fungsi foo:
diakhiri dengan panggilan ke foo. Ini bisa diganti dengan:
yang menghilangkan panggilan rekursif kedua.
sumber
Sebuah pertanyaan yang telah ditutup sebagai duplikat dari yang satu ini memiliki struktur data yang sangat spesifik:
Node memiliki struktur berikut:
Fungsi penghapusan rekursif tampak seperti:
Secara umum, tidak selalu mungkin untuk menghindari tumpukan untuk fungsi rekursif yang memanggil dirinya sendiri lebih dari satu kali (atau bahkan sekali). Namun, untuk struktur khusus ini, dimungkinkan. Idenya adalah untuk meratakan semua node menjadi satu daftar. Ini dilakukan dengan meletakkan node saat ini
child
di akhir daftar baris atas.Teknik ini dapat diterapkan pada setiap struktur data tertaut yang dapat direduksi menjadi DAG dengan pemesanan topologi deterministik. Node anak saat ini disusun ulang sehingga anak terakhir mengadopsi semua anak lainnya. Kemudian node saat ini dapat dihapus dan traversal kemudian dapat beralih ke anak yang tersisa.
sumber
Rekursi tidak lain adalah proses memanggil satu fungsi dari yang lain hanya proses ini dilakukan dengan memanggil fungsi dengan sendirinya. Seperti yang kita ketahui ketika satu fungsi memanggil fungsi lainnya, fungsi pertama menyimpan statusnya (variabelnya) dan kemudian meneruskan kontrol ke fungsi yang dipanggil. Fungsi yang dipanggil dapat dipanggil dengan menggunakan nama variabel yang sama ex fun1 (a) dapat memanggil fun2 (a). Ketika kita melakukan panggilan rekursif, tidak ada hal baru yang terjadi. Satu fungsi memanggil dirinya sendiri dengan melewatkan tipe yang sama dan mirip dalam variabel nama (tetapi jelas nilai yang disimpan dalam variabel berbeda, hanya namanya tetap sama.) Untuk dirinya sendiri. Tetapi sebelum setiap panggilan fungsi menyimpan statusnya dan proses penyimpanan ini berlanjut. SAVING DILAKUKAN DENGAN STACK.
SEKARANG STACK DATANG KE MAIN.
Jadi jika Anda menulis program berulang dan menyimpan status di tumpukan setiap kali dan kemudian mengeluarkan nilai dari tumpukan saat diperlukan, Anda telah berhasil mengubah program rekursif menjadi program berulang!
Buktinya sederhana dan analitis.
Dalam rekursi komputer menyimpan stack dan dalam versi iteratif Anda harus mengelola stack secara manual.
Pikirkan, cukup konversikan program rekursif pencarian pertama (pada grafik) menjadi program berulang dfs.
Semua yang terbaik!
sumber
Contoh sederhana dan lengkap lainnya dari mengubah fungsi rekursif menjadi iteratif menggunakan stack.
sumber
Deskripsi kasar tentang bagaimana suatu sistem mengambil fungsi rekursif dan menjalankannya menggunakan tumpukan:
Ini dimaksudkan untuk menunjukkan ide tanpa detail. Pertimbangkan fungsi ini yang akan mencetak titik-titik pada grafik:
Misalnya grafik: A-> B A-> C show (A) akan mencetak B, A, C
Panggilan fungsi berarti menyimpan status lokal dan titik kelanjutan agar Anda dapat kembali, dan kemudian melompat fungsi yang ingin Anda panggil.
Misalnya, misalkan acara (A) mulai berjalan. Panggilan fungsi pada baris 3. show (B) berarti - Tambahkan item ke tumpukan yang berarti "Anda harus melanjutkan di baris 2 dengan simpul status variabel lokal = A" - Goto line 0 dengan node = B.
Untuk mengeksekusi kode, sistem menjalankan instruksi. Ketika panggilan fungsi ditemui, sistem mendorong informasi yang diperlukan untuk kembali ke tempat sebelumnya, menjalankan kode fungsi, dan ketika fungsi selesai, muncul informasi tentang ke mana ia harus pergi untuk melanjutkan.
sumber
Tautan ini memberikan beberapa penjelasan dan mengusulkan gagasan untuk menjaga "lokasi" agar dapat sampai ke tempat yang tepat di antara beberapa panggilan rekursif:
Namun, semua contoh ini menggambarkan skenario di mana panggilan rekursif dibuat dalam jumlah tetap . Hal-hal menjadi lebih rumit ketika Anda memiliki sesuatu seperti:
sumber
Ada cara umum untuk mengkonversi traversal rekursif ke iterator dengan menggunakan iterator malas yang menggabungkan beberapa pemasok iterator (ekspresi lambda yang mengembalikan iterator). Lihat Konversal Rekursif Traversal ke Iterator saya .
sumber
Contoh saya ada di Clojure, tetapi harus cukup mudah diterjemahkan ke bahasa apa pun.
Diberikan fungsi ini
StackOverflow
untuk nilai besar n:kita dapat mendefinisikan versi yang menggunakan tumpukannya sendiri dengan cara berikut:
di mana
return
didefinisikan sebagai:Ini berfungsi untuk fungsi yang lebih kompleks juga, misalnya fungsi ackermann :
dapat diubah menjadi:
sumber