Recursion
Diperkenalkan
15:32
Pencarian & Pengurutan
Buku telepon dengan satu juta nama. Jika Anda memeriksanya satu per satu, Anda mungkin melakukan satu juta perbandingan. Namun Anda sudah tahu triknya: buka di tengah…
Narasi bahasa Inggris · takarir bahasa Inggris dan 中文 yang dapat dipilih
In this lesson
| English | Makna |
|---|---|
| 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/ | tumpukan pemanggilan |
| stack frame/stæk freɪm/ | bingkai tumpukan |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | kelebihan tumpukan |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | pememoisan |
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.
Every recursive algorithm must have a base case because:
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
The base case is the condition that ends the chain of calls; without it the recursion runs forever.
Recursion is a natural fit for self-similar problems (trees, divide-and-conquer), but each call adds a stack frame — so without a base case it overflows the stack.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
A simple counting loop is cleaner for plain iteration; recursion shines when the problem contains smaller copies of itself.
What must a recursive routine have to terminate? Select semua that apply.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
A base case alone is not enough: if the input never shrinks, the base case is never reached and frames pile up until the stack overflows.
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 unwinds from the leaves up
Step through fib(4) in the order the calls actually finish: the leaves (base cases) resolve first, then each parent combines its children. Notice fib(2) is computed twice — that repeated work is why naive recursion is slow.
What does Factorial(4) return?
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
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.
Put the events of evaluating Factorial(4) in order.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds.
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.
Match each recursion term to what it means.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
A recursion needs a base case to stop and a recursive case to shrink the problem; each call adds a stack frame.
A stack frame for a function call holds:
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Each frame stores that call's parameters, locals and where to resume — so calls don't trample each other.
Each call in progress keeps its parameters and locals in its own ____ on the call stack.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made.
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.
A recursive routine crashes with a stack overflow. Which explanation is correct?
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely.
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 mudah 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