Recursion
Diperkenalkan
13:31
Koleksi Data
Ambil satu foto di ponsel Anda. Bagi komputer, itu bukanlah gambar sama sekali — itu adalah grid angka, satu untuk setiap piksel, sekitar dua belas juta darinya. Sekarang cobalah…
Narasi bahasa Inggris · takarir bahasa Inggris dan 中文 yang dapat dipilih
In this lesson
| English | Makna |
|---|---|
| Recursion/rɪˈkɜːʃn/ | rekursi |
| base case/beɪs keɪs/ | kasus dasar |
| recursive case/rɪˈkɜːsɪv keɪs/ | kasus rekursif |
| unwind/ʌnˈwaɪnd/ | unwinding |
Metode yang memanggil dirinya sendiri
- Resursi adalah ketika sebuah metode memanggil dirinya sendiri untuk menyelesaikan versi masalah yang lebih kecil.
- Setiap resursi membutuhkan dua bagian: kasus dasar dan kasus rekursif.
- Kasus dasar menghentikan resursi — input kecil yang metode jawab langsung.
- Kasus rekursif memanggil metode lagi pada input yang lebih kecil.
Kasus dasar
- Tanpa kasus dasar, sebuah metode memanggil dirinya sendiri selamanya — sebuah
StackOverflowError. - Kasus dasar menangani input terkecil tanpa panggilan lain.
- Contoh:
factorial(0)mengembalikan1langsung — tidak ada panggilan lagi. - Selalu periksa: apakah setiap jalur akhirnya mencapai kasus dasar?

Merge sort memanggil dirinya sendiri pada setiap setengah bagian, lalu menggabungkan setengah yang sudah terurut
Kasus rekursif
- Kasus rekursif melakukan sedikit pekerjaan, lalu memanggil dirinya sendiri pada input yang lebih kecil.
factorial(n)mengembalikann * factorial(n - 1)— input mengecil satu setiap panggilannya.- Setiap panggilan menunggu panggilan yang lebih kecil kembali sebelum selesai.
- Panggilan menumpuk, mencapai kasus dasar, lalu kembali ke atas.
Bagaimana panggilan menumpuk
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)mengembalikan1; kemudian stack kembali:1, 1, 2, 6.- Setiap panggilan menyimpan salinan parameternya sendiri hingga kembali.
- Melacak resursi berarti mengikuti panggilan turun, lalu pengembalian naik.
Setiap rekursi memerlukan kasus dasar yang menghentikannya — dan setiap pemanggilan rekursif harus bergerak MENJUJI kasus dasar tersebut (input yang lebih kecil). Melewatkan kasus dasar, atau memanggil input yang sama atau lebih besar, maka metode akan merekursi selamanya hingga terjadi StackOverflowError. Telusuri dengan mengikuti pemanggilan turun ke kasus dasar, kemudian pengembalian naik kembali.
sum(n) = 1 + 2 + … + n oleh resursi:
- Kasus dasar:
if (n == 0) return 0; - Kasus rekursif:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
Resursi adalah sebuah metode memanggil dirinya sendiri pada input yang lebih kecil. Membutuhkan kasus dasar (berhenti langsung, tidak ada panggilan lagi) dan kasus rekursif (melakukan sedikit pekerjaan, lalu berresursi pada input yang lebih kecil). Panggilan menumpuk turun ke kasus dasar, lalu kembali naik. Melewatkan kasus dasar dan Anda akan mendapatkan StackOverflowError.
factorial(3) unwinds from the base case up
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6.
A recursive method is one that...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Recursion = a method calling itself.
The base case is...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
The base case stops the recursion.
A recursion with no reachable base case causes...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
It recurses forever until the stack overflows.
The recursive case must call itself on...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Each call must shrink toward the base case.
If factorial(0)=1 and factorial(n)=n*factorial(n-1), what is factorial(3)?
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Calls stack independently, then unwind.