Algoritmika · Pelajaran 6 dari 10
Rekursi dan relasi rekurens
10 menit baca · BelajarCode
Relasi rekurens adalah rumus yang mendefinisikan suatu nilai dari nilai-nilai sebelumnya. Contoh terkenal adalah Fibonacci: F(n) = F(n - 1) + F(n - 2).
Contoh: menaiki tangga
Kamu menaiki tangga dengan n anak tangga. Setiap langkah, kamu naik 1 atau 2 anak tangga. Ada berapa cara berbeda untuk sampai di puncak?
Pikirkan langkah terakhir: kamu tiba di puncak dari anak tangga n - 1 (dengan langkah 1) atau dari n - 2 (dengan langkah 2). Jadi:
- cara(n) = cara(n - 1) + cara(n - 2)
- cara(1) = 1, cara(2) = 2
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| cara(n) | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
Memoisasi: jangan hitung dua kali
Rekursi langsung untuk rumus ini sangat lambat, karena nilai yang sama dihitung berulang-ulang. Solusinya memoisasi: simpan hasil yang sudah dihitung.
1from functools import lru_cache23@lru_cache(maxsize=None)4def cara(n):5 if n <= 2:6 return n7 return cara(n - 1) + cara(n - 2)89print(cara(10))10print(cara(50))89 20365011074
Tanda @lru_cache di atas fungsi otomatis menyimpan hasil setiap panggilan. Tanpa memoisasi, cara(50) butuh miliaran panggilan. Dengan memoisasi, cukup sekitar 50.
Cara lain: dari bawah ke atas
Rekurens juga bisa dihitung dengan perulangan biasa, mulai dari nilai terkecil:
1def cara_iteratif(n):2 if n <= 2:3 return n4 a, b = 1, 25 for _ in range(3, n + 1):6 a, b = b, a + b7 return b89print(cara_iteratif(10), cara_iteratif(50))89 20365011074
Banyak soal, satu pola
Menyusun ubin 2 × 1 untuk menutupi papan 2 × n ternyata punya rekurens yang sama: ubin terakhir diletakkan tegak (sisa papan 2 × (n - 1)) atau dua ubin mendatar (sisa 2 × (n - 2)). Melatih diri menemukan "langkah terakhir" seperti ini adalah kunci soal rekurens.
Cek pemahaman
Rekurens f(n) = 2 × f(n - 1) dengan f(1) = 3. Berapa f(5)?
Latihan
Menara Hanoi
Pada teka-teki Menara Hanoi, banyak langkah minimum untuk memindahkan n cakram memenuhi f(n) = 2 × f(n - 1) + 1 dengan f(1) = 1. Hitung f(10) dengan rekursi, lalu tebak rumus langsungnya.
Pembahasan
1def hanoi(n):2 if n == 1:3 return 14 return 2 * hanoi(n - 1) + 156print([hanoi(n) for n in range(1, 11)])[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]
Polanya satu kurangnya dari pangkat dua: f(n) = 2 pangkat n dikurangi 1. Jadi f(10) = 1024 - 1 = 1023.
Alasannya: untuk memindahkan n cakram, pindahkan dulu n - 1 cakram ke tiang bantu, pindahkan cakram terbesar, lalu pindahkan lagi n - 1 cakram ke atasnya.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.