Recursion
| English | Bahasa Indonesia |
|---|---|
| Recursion/rɪˈkɜːʃn/ | Recursion |
| base case/beɪs keɪs/ | kasus dasar |
| recursive case/rɪˈkɜːsɪv keɪs/ | kasus rekursif |
| unwind/ʌnˈwaɪnd/ | membuka kembali |
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?
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) membongkar dari kasus dasar ke atas
fact(0) mengembalikan 1 (kasus dasar); setiap induk mengalikannya: 1, 1, 2, 6.
Metode rekursif adalah satu yang...
Rekursion = sebuah metode yang memanggil dirinya sendiri.
Kasus dasar adalah...
Kasus dasar menghentikan rekursi.
Rekursi tanpa kasus dasar yang dapat dicapai menyebabkan...
Ia melakukan rekursi terus-menerus hingga tumpukan penuh (overflow).
Kasus rekursif harus memanggil dirinya sendiri pada...
Setiap panggilan harus mengecil menuju kasus dasar.
Jika factorial(0)=1 dan factorial(n)=n*factorial(n-1), berapakah factorial(3)?
3 * 2 * 1 * 1 = 6.
Setiap panggilan rekursif menyimpan salinan parameternya sendiri hingga ia mengembalikan.
Panggilan menumpuk secara independen, lalu membongkar.