Recursion
| English | Bahasa Indonesia |
|---|---|
| recursive/rɪˈkɜːsɪv/ | rekursif |
| base case/beɪs keɪs/ | kasus dasar |
| recursive case/rɪˈkɜːsɪv keɪs/ | kasus rekursif |
| call stack/kɔːl stæk/ | call stack |
| stack frame/stæk freɪm/ | frame tumpukan pemanggilan |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | stack overflow |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | memoization |
Definisi yang mengandung dirinya sendiri
- Bagaimana Anda mendefinisikan apa itu leluhur? Orang tua Anda adalah leluhur. Leluhur dari orang tua Anda juga merupakan leluhur. Dua kalimat ini mendefinisikan rantai tak terbatas, dan kalimat kedua menggunakan kata yang sedang ia definisikan.
- Itu bukan argumen melingkar, karena kalimat pertama memberikan batas di mana rantai berhenti. Tanpanya, definisi akan terus terurai selamanya.
- Program dapat ditulis dengan cara yang sama, dan untuk masalah berbentuk seperti rantai itu, solusi rekursif jauh lebih pendek daripada loop.
- Pelajaran ini adalah kasus dasar dan kasus rekursif, bagaimana pemanggilan rekursif ditelusuri, dan apa yang dilakukan tumpukan pemanggilan di bawahnya.
Dua kasus
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
- Kasus dasar adalah versi masalah yang cukup kecil untuk dijawab langsung, tanpa pemanggilan lanjutan. Ini yang menghentikan rekursi.
- Kasus rekursif memanggil fungsi lagi dengan masukan yang lebih kecil, bergerak menuju kasus dasar.
- Keduanya diperlukan. Rekursi tanpa kasus dasar tidak pernah berhenti; satu yang masukannya tidak mengecil tidak pernah mencapai kasus dasar.
Setiap algoritma rekursif harus memiliki kasus dasar karena:
Kasus dasar adalah kondisi yang mengakhiri rantai pemanggilan; tanpa hal itu rekursi berjalan selamanya.
Rekursi cocok alami untuk masalah self-similar (pohon, bagi-dan-menaklukkan), tetapi setiap pemanggilan menambahkan frame stack — sehingga tanpa kasus dasar tumpukan akan penuh (overflow).
Loop penghitungan sederhana lebih rapi untuk iterasi biasa; rekursi bersinar ketika masalah mengandung salinan dirinya yang lebih kecil.
Apa yang harus dimiliki rutinitas rekursif agar dapat berhenti? Pilih semua yang berlaku.
Kasus dasar saja tidak cukup: jika input tidak pernah mengecil, kasus dasar tidak pernah tercapai dan frame menumpuk hingga tumpukan penuh.
Contoh kerja: menelusuri rekursi
- Telusuri
Factorial(4). - Menggulung ke atas:
Factorial(4)membutuhkan4 * Factorial(3), yang membutuhkan3 * Factorial(2), yang membutuhkan2 * Factorial(1). Belum ada perkalian yang terjadi; setiap pemanggilan sedang menunggu. - Kasus dasar:
Factorial(1)mengembalikan nilai 1 tanpa memanggil apa pun. - Menggulung ke bawah:
2 * 1 = 2dikembalikan, lalu3 * 2 = 6, kemudian4 * 6 = 24. - Tunjukkan kedua arah. Penelusuran yang hanya turun, atau hanya kembali, kehilangan separuh nilai skor.
Recursion terbuka dari daun ke atas
Langkah melalui fib(4) sesuai urutan pemanggilan selesai: daun (kasus dasar) diselesaikan dulu, lalu setiap induk menggabungkan anak-anaknya. Perhatikan bahwa fib(2) dihitung dua kali — pekerjaan berulang inilah yang membuat rekursi naif lambat.
Berapa nilai yang dikembalikan Factorial(4)?
4 × 3 × 2 × 1 = 24.
Apa yang dilakukan mesin
- Setiap pemanggilan memerlukan salinan sendiri dari parameternya dan variabel lokalnya, karena
Factorial(3)danFactorial(2)adalah pemanggilan berbeda dengan nilainyang berbeda. - Salinan-salinan itu berada di bingkai tumpukan pada tumpukan pemanggilan: satu bingkai per pemanggilan yang sedang berlangsung, menyimpan parameter, variabel lokal, dan alamat kembalinya.
- Bingkai didorong masuk pada setiap pemanggilan dan dilepas keluar saat kembali. Itulah sebabnya nilai-nilai kembali secara terbalik dari urutan pemanggilannya: tumpukan pemanggilan adalah tumpukan, persis ADT dari topik 10.
Susun peristiwa evaluasi Factorial(4) secara berurutan.
Tidak ada yang dikalikan saat turun; setiap pemanggilan menunggu. Perkalian semua terjadi saat tumpukan dibuka kembali.
Apa yang salah
- Tidak ada kasus dasar, atau kasus dasar yang tidak pernah dicapai: rekursi tidak pernah berhenti, bingkak menumpuk, dan tumpukan pemanggilan kehabisan memori. Itu adalah kelebihan tumpukan (stack overflow).
- Rekursi mendalam: bahkan rekursi yang benar dengan tingkat sejuta memerlukan seribu bingkai, sehingga dapat menghabiskan memori di mana loop tidak akan menggunakannya.
- Pekerjaan berulang: Fibonacci rekursif naif menghitung ulang nilai yang sama berkali-kali secara eksponensial. Perbaiki dengan loop, atau dengan memoisasi, menyimpan setiap hasil saat pertama kali dihitung.
Pasangkan setiap istilah rekursi dengan maknanya.
Rekursi memerlukan kasus dasar untuk berhenti dan kasus rekursif untuk mengecilkan masalah; setiap pemanggilan menambahkan frame stack.
Frame stack untuk pemanggilan fungsi menyimpan:
Setiap frame menyimpan parameter, variabel lokal, dan lokasi kelanjutan pemanggilan tersebut—sehingga pemanggilan tidak saling menimpa.
Setiap pemanggilan yang sedang berjalan menyimpan parameternya dan variabel lokalnya dalam ____ sendiri pada tumpukan pemanggilan.
Ditekan saat pemanggilan, dilepas saat pengembalian. Itulah sebabnya nilai kembali dengan urutan terbalik dari urutan pemanggilan dilakukan.
Rekursi atau iterasi
- Rekursi cocok untuk masalah self-similar, di mana masalah mengandung salinan dirinya yang lebih kecil: traversal pohon, bagi dan taklukkan seperti pencarian biner dan merge sort, serta rantai leluhur di atas.
- Iterasi cocok untuk segalanya lainnya, dan menggunakan tidak ada memori tambahan untuk pengulangan.
- Segala sesuatu yang rekursif dapat ditulis secara iteratif dan sebaliknya juga benar. Pilihannya adalah mana yang menyatakan masalah dengan jelas, dibandingkan dengan memori yang dibebankan tumpukan.
Rutin rekursif mengalami kegagalan akibat tumpukan penuh (stack overflow). Penjelasan mana yang benar?
Tumpukan penuh berkaitan dengan frame, bukan aritmatika. Angka yang terlalu besar untuk registrernya adalah kelebihan aritmatika, hal yang sama sekali berbeda.
Contoh kerja: nyatakan risikonya
- Seorang siswa menulis rutinitas rekursif dan program itu crash dengan kelebihan tumpukan. Berikan dua kemungkinan penyebabnya.
- Tidak ada kasus dasar, atau kasus dasar tidak pernah bisa dicapai karena masukan tidak menjadi lebih kecil pada setiap pemanggilan, sehingga pemanggilan berlanjut selamanya dan bingkak menumpuk.
- Rekursinya benar tetapi terlalu dalam: setiap pemanggilan yang sangat banyak menyimpan bingkai stack-nya sendiri, dan tumpukan pemanggilan kehabisan memori sebelum kasus dasar dicapai.
- Kedua penyebab berkaitan dengan bingkak yang menumpuk. Jelaskan apa yang menumpuk dan mengapa tidak pernah berhenti.
⟦⟧ Nilai yang sering terlewat
- Rekursi memerlukan keduanya: kasus dasar dan masukan yang menjadi lebih kecil. Menyebutkan hanya kasus dasar adalah separuh kondisi.
- Dalam penelusuran, tunjukkan pemanggilan menggulung ke atas dan nilai menggulung ke bawah. Kedua arah membawa nilai skor.
- Setiap pemanggilan memiliki parameternya sendiri dan variabel lokalnya, dalam bingkai tumpukan sendiri. Itulah sebabnya rekursi memakan memori yang tidak dimiliki oleh iterasi.
- Kelebihan tumpukan (stack overflow) adalah kehabisan memori tumpukan karena terlalu banyak bingkak, bukan kelebihan aritmatika.
Anda telah memahaminya
- rutinitas rekursif memerlukan kasus dasar yang diselesaikan langsung dan kasus rekursif yang memanggil dirinya sendiri dengan masukan yang lebih kecil
- telusuri dalam kedua arah: pemanggilan menggulung ke atas menuju kasus dasar, lalu nilai menggulung ke bawah kembali
- setiap pemanggilan memiliki bingkai tumpukan sendiri pada tumpukan pemanggilan, didorong masuk saat dipanggil dan dilepas saat kembali, yang menyebabkan rekursi memakan memori
- risiko: tidak adanya kasus dasar yang dapat dijangkau menyebabkan rekursi tak hingga dan tumpukan meluber, rekursi dalam menghabiskan memori, dan pekerjaan berulang memerlukan perulangan atau memoisasi